首页 > 代码库 > 基于比较的算法之五：堆排序

基于比较的算法之五：堆排序

2024-07-02 01:32:30   227人阅读

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：
父节点i的左子节点在位置 (2*i+1);
父节点i的右子节点在位置 (2*i+2);
子节点i的父节点在位置 floor((i-1)/2);

在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作：
最大堆调整（maxHeapify）：将堆的末端子节点作调整，使得子节点永远小于父节点

创建最大堆（buildMaxHeap）：将堆所有数据重新排序

堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

现在给出C#实现的堆排序：

 1  public class HeapSort<T> : ISort<T> where T : IComparable<T>
 2     {
 3         public void Sort(T[] array, int startIndex, int endIndex)
 4         {
 5             //Heapify the array
 6             buildMaxHeap(array, startIndex, endIndex);
 7             //Sort from endIndex to (startIndex-1), 
 8             //when i=startIndex, then only one node left,then no any requirement to heapify it.
 9             for (int i = endIndex; i > startIndex; i--)
10             {
11                 //swap array[i] and array[startIndex]
12                 T tmpT = array[i];
13                 array[i] = array[startIndex];
14                 array[startIndex] = tmpT;
15                 maxHeapify(array, startIndex, i - 1, startIndex);
16             }
17         }
18         private void buildMaxHeap(T[] array, int startIndex, int endIndex)
19         {
20             //Leaf node is from (endIndex-startIndex+1)/2+1+startIndex to endIndex
21             // //O(n*Log(n))
22             for (int i = (endIndex - startIndex + 1) / 2 + startIndex; i >= startIndex; i--)
23             {
24                 //O(Log(n))
25                 maxHeapify(array, startIndex, endIndex, i);
26             }
27         }
28 
29         //insert a new root node for two child maxHeap.
30         private void maxHeapify(T[] array, int startIndex, int endIndex, int newRootIndex)
31         {
32 
33             //int L = (newRootIndex - startIndex) * 2 + 1 + startIndex;
34             int L = (newRootIndex - startIndex + 1) * 2 + startIndex - 1;//The array base is from 0.
35             int R = L + 1;
36             int tmpLargestIndex = newRootIndex;
37             if (L <= endIndex && array[L].CompareTo(array[tmpLargestIndex]) > 0)
38             {
39                 tmpLargestIndex = L;
40             }
41             if (R <= endIndex && array[R].CompareTo(array[tmpLargestIndex]) > 0)
42             {
43                 tmpLargestIndex = R;
44             }
45             if (tmpLargestIndex != newRootIndex)
46             {
47                 //swap array[tmpLargestIndex] and array[newRootIndex]
48                 T tmpT = array[tmpLargestIndex];
49                 array[tmpLargestIndex] = array[newRootIndex];
50                 array[newRootIndex] = tmpT;
51                 //MaxHeapify the child branch, the newRootIndex= tmpLargestIndex
52                 maxHeapify(array, startIndex, endIndex, tmpLargestIndex);
53             }
54         }
55     }

作者：Andy Zeng

欢迎任何形式的转载，但请务必注明出处。

http://www.cnblogs.com/andyzeng/p/3699195.html


联系
我们