堆排序C＃排序與大型陣列

我有我的堆排序實施小問題。基本上，我實現了它，它基本上適用於具有6個或更少元素的數組。但由於某種原因，任何大於6個元素的東西，排序都是錯誤的。堆排序C＃排序與大型陣列

例如：

排序{10,64,7,99,32,18}給出了這樣的：7,10,18,32,64,99

排序{10,64,7 ，99,32,18,2,48}給出了這樣的：2,7,10,32，下面，48,64,99

我的實現。隨着數組的大小變大，在某種意義上排序變得更加混亂，並給出錯誤的輸出。我怎樣才能解決這個問題？

class Program 
{ 
    static void Main(string[] args) 
    { 
     int[] arr = { 10, 64, 7, 99, 32, 18}; 
     HeapSort hs = new HeapSort(); 
     hs.PerformHeapSort(arr); 
     Console.ReadLine(); 
    } 
} 
class HeapSort 
{ 
    private int heapSize; 

    private void BuildHeap(int[] arr) 
    { 
     heapSize = arr.Length-1; 
     for (int i = heapSize/2; i >= 0; i--) 
     { 
      Heapify(arr, i); 
     } 
    } 

    private void Swap(int[] arr, int x, int y)//function to swap elements 
    { 
     int temp = arr[x]; 
     arr[x] = arr[y]; 
     arr[y] = temp; 
    } 
    private void Heapify(int[] arr, int index) 
    { 
     int left = 2 * index; 
     int right = 2 * index + 1; 
     int largest; 

     if (left <= heapSize && arr[left] > arr[index]) 
     { 
      largest = left; 
     } 
     else 
     { 
      largest = index; 
     } 
     if (right <= heapSize && arr[right] > arr[largest]) 
     { 
      largest = right; 
     } 
     else 
     { 
      largest = index; 
     } 

     if (largest != index) 
     { 
      Swap(arr, index, largest); 
      Heapify(arr, largest); 
     } 
    } 
    public void PerformHeapSort(int[] arr) 
    { 
     BuildHeap(arr); 
     for (int i = arr.Length-1; i >= 0; i--) 
     { 
      Swap(arr, 0, i); 
      heapSize--; 
      Heapify(arr, 0); 
     } 
     DisplayArray(arr); 
    } 
    private void DisplayArray(int[] arr) 
    { 
     for (int i = 0; i < arr.Length; i++) 
     { Console.Write("[{0}]", arr[i]); } 
    } 
}

來源

2014-11-25 Karim O.

必須有在您的實施中出現錯誤。嘗試使用您的調試器並發現問題。 – user743414 2014-11-25 11:07:54

錯誤包含在函數Heapify中。功能的修正版本：

 private void Heapify(int[] arr, int index) 
     { 
      int left = 2 * index + 1; 
      int right = 2 * index + 2; 
      int largest = index; 
      if (left <= heapSize && arr[left] > arr[index]) 
      { 
       largest = left; 
      } 

      if (right <= heapSize && arr[right] > arr[largest]) 
      { 
       largest = right; 
      } 

      if (largest != index) 
      { 
       Swap(arr, index, largest); 
       Heapify(arr, largest); 
      } 
     }

來源

2014-11-25 13:17:59

是的！這解決了問題。謝謝。 – 2014-11-25 18:18:19

-3

的方法錯了實現 - Heapify（INT []改編，INT指數）

，你可以像下面：

public static void Heapify(int[] arr, int index) 
    { 
     int left = (index + 1) * 2 - 1; 
     int right = (index + 1) * 2; 
     int largest = 0; 
     if (left < heapSize && arr[left] > arr[index]) 
     { 
      largest = left; 
     } 
     else { 
      largest = index; 
     } 

     if (right < heapSize && arr[right] > arr[largest]) 
     { 
      largest = right; 
     } 

     if (largest != index) 
     { 
      Swap(arr, index, largest); 
      Heapify(arr, largest); 
     } 

    }

來源

2015-05-03 11:00:36 Gurupreet

堆排序C＃排序與大型陣列

回答

相關問題