using System; using System.Collections; namespace Sort { public class HeapSorter { public static int[] Sort(int[] sortArray) { BuildMaxHeap(sortArray); for (int i = (sortArray.Length - 1); i > 0; i--) { Swap(ref sortArray[0], ref sortArray[i]); // 将堆顶元素和无序区的末了一个元素交流 MaxHeapify(sortArray, 0, i); // 将新的无序区调解为堆,无序区在变小 } return sortArray; } /// <summary> /// 初始大根堆,自底向上地建堆 /// 完整二叉树的基础性子,最底层节点是 n/2,所以从 sortArray.Length / 2 最先 /// </summary> private static void BuildMaxHeap(int[] sortArray) { for (int i = (sortArray.Length / 2) - 1; i >= 0; i--) { MaxHeapify(sortArray,i, sortArray.Length); } } /// <summary> /// 将指定的节点调解为堆 /// </summary> /// <param name="i">须要调解的节点</param> /// <param name="heapSize">堆的大小,也指数组中无序区的长度</param> private static void MaxHeapify(int[] sortArray, int i, int heapSize) { int left = 2 * i + 1; // 左子节点 int right = 2 * i + 2; // 右子节点 int larger = i; // 暂时变量,存放大的节点值 // 比较左子节点 if (left < heapSize && sortArray[left] > sortArray[larger]) { larger = left; } // 比较右子节点 if (right < heapSize && sortArray[right] > sortArray[larger]) { larger = right; } // 若有子节点大于本身就交流,使大的元素上移。 if (i != larger) { Swap(ref sortArray[i], ref sortArray[larger]); MaxHeapify(sortArray, larger, heapSize); } } //数组内元素交换 private static void Swap(ref int a, ref int b) { int t; t = a; a = b; b = t; } } }
堆排序的头脑:
应用大顶堆(小顶堆)堆顶纪录的是最大关键字(最小关键字)这一特征,使得每次从无序中挑选最大纪录(最小纪录)变得简朴。
其基础头脑为(大顶堆):
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无序区;
2)将堆顶元素R[1]与末了一个元素R[n]交流,此时获得新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3)因为交流后新的堆顶R[1]能够违背堆的性子,因而须要对当前无序区(R1,R2,......Rn-1)调解为新堆,然后再次将R[1]与无序区末了一个元素交流,获得新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不停反复此历程直到有序区的元素个数为n-1,则全部排序历程完成。
操纵历程以下:
1)初始化堆:将R[1..n]组织为堆;
2)将当前无序区的堆顶元素R[1]同该区间的末了一个纪录交流,然后将新的无序区调解为新的堆。
因而关于堆排序,最主要的两个操纵就是组织初始堆和调解堆,实在组织初始堆事实上也是调解堆的历程,只不过组织初始堆是对一切的非叶节点都举行调解。
以上就是C# 堆排序的内容,更多相关内容请关注ki4网(www.ki4.cn)!