堆排序在C＃中大大小的数组排序 [英] Heap Sort in C# sorting with large sized arrays
问题描述
我有一个小问题，我的堆排序实现。基本上，我实现它，它本质上与具有6个或更少的元件阵列的工作原理。但由于某些原因，任何超过6个元素大，排序是马车。
例如：
{排序} 10,64,7,99,32,18给出了这样的：7,10,18,32,64,99
{排序} 10,64,7,99,32,18,2,48给出了这样的：2,7,10,32， 18 的，48， 64,99
下面我的实现。作为数组的大小变大，排序变为在某种意义上更加扰，并给出一个不正确的输出。我该如何解决这个问题？
类节目
{
静态无效的主要（字串[] args）
{
INT [] =改编{10，64，7，99，32，18};
堆排序HS =新堆排序（）;
hs.PerformHeapSort（ARR）;
到Console.ReadLine（）;
}
}
类堆排序
{
私人诠释HEAPSIZE; 私人无效BuildHeap（INT [] ARR）
{
HEAPSIZE = arr.Length-1;
对于（INT I = HEAPSIZE / 2; I＆GT; = 0;我 - ）
{
Heapify（ARR，I）;
}
} 私人无效掉期（INT []编曲，诠释的x，int y）对//函数来交换元素
{
INT TEMP = ARR [X];
ARR [X] = ARR [Y];
ARR [Y] =温度;
}
私人无效Heapify（INT []改编，INT指数）
{
INT左= 2 *指数;
INT右= 2 *指数+ 1;
诠释最大; 如果（左＆LT; = HEAPSIZE和放大器;＆安培;常用3 [左]＆GT;常用3 [指数]）
{
最大=左;
}
其他
{
最大=指数;
}
如果（右LT = HEAPSIZE和放大器;＆安培;常用3 [右]＆GT;常用3 [大]）
{
最大=权利;
}
其他
{
最大=指数;
} 如果（最大！=指数）
{
掉期（ARR，指数，最大）;
Heapify（ARR，最大）;
}
}
公共无效PerformHeapSort（INT [] ARR）
{
BuildHeap（ARR）;
的for（int i = arr.Length-1; I＆GT; = 0;我 - ）
{
掉期（ARR，0，I）;
heapSize--;
Heapify（ARR，0）;
}
DisplayArray（ARR）;
}
私人无效DisplayArray（INT [] ARR）
{
的for（int i = 0; I＆LT; arr.Length;我++）
{Console.Write（[{0}]，编曲[I]）; }
}
}
错误包含函数 Heapify 。
该函数的正确版本：
私人无效Heapify（INT []改编，INT指数）
{
INT左= 2 *指数+ 1;
INT右= 2 *指数+ 2;
诠释最大=指数;
如果（左＆LT; = HEAPSIZE和放大器;＆安培;常用3 [左]＆GT;常用3 [指数]）
{
最大=左;
} 如果（右LT = HEAPSIZE和放大器;＆安培;常用3 [右]＆GT;常用3 [大]）
{
最大=权利;
} 如果（最大！=指数）
{
掉期（ARR，指数，最大）;
Heapify（ARR，最大）;
}
}
I have a small problem with my heap sort implementation. Basically, I implemented it, and it essentially works with arrays that have 6 or less elements. But for some reason, anything larger than 6 elements, and the sorting is buggy.
For example:
Sorting {10,64,7,99,32,18} gives this: 7,10,18,32,64,99
Sorting {10,64,7,99,32,18,2,48} gives this: 2,7,10,32,18,48,64,99
My implementation below. As the size of the array gets larger, the sorting becomes more scrambled in a sense and gives an incorrect output. How can I fix this?
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]); }
}
}
Errors contains in function Heapify.
The corrected version of the function:
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);
}
}
这篇关于堆排序在C＃中大大小的数组排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
