堆排序算法

2019-11-06 06:59:37

字体：大中小

来源：转载

供稿：网友

堆排序是一个非常出色的算法，在时间复杂度是O(nlog(n))，在空间上是就地排序。

堆，又叫二叉堆，被是视为完全二叉树。堆可以分为两种，最大堆和最小堆，最大堆的意思是，每一个节点（除根节点以外）的值一定小于或等于它的父节点的值。最小堆的意思是，每个节点（除根节点外）的值一定小于或等于他的父节点的值。最大堆中的最大值一定位于它的根节点，而最小堆的最小值也一定位于它的根节点。

我们是通过一个数组来存储一个堆的。下面的三个函数用来获取一个节点的父节点、左子节点和右子节点的位置

static int GetParentIndex(int i){ return (i - 1) / 2;}static int GetLeftIndex(int i){ return i * 2 + 1;}static int GetRightIndex(int i){ return (i + 1) * 2;}

HeapSize是堆的逻辑长度，小于等于数组的长度。

堆排序由下面三个子过程组成

MaxHeapify(int[] array, int i)，它的作用是保持堆的性质，运行完该函数后，以i节点为根的子树将成为一个堆，满足堆的性质BuildMaxHeap(int[] array)，创建一个最大堆。运行完该函数后，array数组将成为一个逻辑堆。HeapSort(int[] array)，堆排序函数。运行完该函数后，array数组将被由小到大排序完毕

先来看看MaxHeapify函数

static void MaxHeapify(int[] array, int i){ int leftIndex = GetLeftIndex(i); int rightIndex = GetRightIndex(i); int largest = 0; if (leftIndex < HeapSize && array[leftIndex] > array[i]) largest = leftIndex; else largest = i; if (rightIndex < HeapSize && array[rightIndex] > array[largest]) { largest = rightIndex; } if (largest != i) { int temp = array[i]; array[i] = array[largest]; array[largest] = temp; MaxHeapify(array, largest); }}

函数的大意是：比较i节点、它的左孩子节点和右孩子节点的数值，将最大值所在的位置赋值给largest，然后如果largest!=i，则交换i和largest位置的值，即将这三个之中的最大值留在根节点，并递归调用MaxHeapify(array, largest)直到以i为根的子树成为一个最大堆。

下面是BuildMaxHeap函数

static int HeapSize = 0;static void BuildMaxHeap(int[] array){ HeapSize = array.Length; int index = array.Length / 2; for (int i = 0; i < index; i++) { MaxHeapify(array, i); }}

这个过程会一步一步地将较大的值往父节点上移动，直到形成一个最大堆。

下面是最后的HeapSort的代码

static void HeapSort(int[] array){ BuildMaxHeap(array); for (int i = array.Length - 1; i >= 0; i--) { int temp = array[i]; array[i] = array[0]; array[0] = temp; HeapSize--; MaxHeapify(array, 0); }}

首先，它会调用HeapSort来创建一个最大堆。最大堆中最大的元素一定在根节点，所以，每次循环都把根节点中的元素和当前循环变量所对应的值交换，并将堆的逻辑长度减一，再通过MaxHeapify(array, 0)来将现有的元素组织成一个最大堆。最后排序完成。

下面是Main函数中来调用HeapSort

static void Main(string[] args){ int[] array = { 7, 2, 101, 5, 21, 6, 1 }; HeapSort(array);}

下面是完成的代码

class PRogram{ static int HeapSize = 0; static void Main(string[] args) { int[] array = { 7, 2, 101, 5, 21, 6, 1 }; HeapSort(array); PrintArray(array); } static void HeapSort(int[] array) { BuildMaxHeap(array); for (int i = array.Length - 1; i >= 0; i--) { int temp = array[i]; array[i] = array[0]; array[0] = temp; HeapSize--; MaxHeapify(array, 0); PrintArray(array); } } static void BuildMaxHeap(int[] array) { HeapSize = array.Length; int index = array.Length / 2; for (int i = 0; i < index; i++) { MaxHeapify(array, i); } } static void MaxHeapify(int[] array, int i) { int leftIndex = GetLeftIndex(i); int rightIndex = GetRightIndex(i); int largest = 0; if (leftIndex < HeapSize && array[leftIndex] > array[i]) largest = leftIndex; else largest = i; if (rightIndex < HeapSize && array[rightIndex] > array[largest]) { largest = rightIndex; } if (largest != i) { int temp = array[i]; array[i] = array[largest]; array[largest] = temp; MaxHeapify(array, largest); } } static int GetParentIndex(int i) { return (i - 1) / 2; } static int GetLeftIndex(int i) { return i * 2 + 1; } static int GetRightIndex(int i) { return (i + 1) * 2; } static void PrintArray(int[] array) { for (int i = 0; i < array.Length; i++) { Console.Write(array[i].ToString() + ", "); } Console.WriteLine(); }}

上一篇：jupyter notebook闪退解决方案

下一篇：#include <windows.h> 为什么不能放在 #include <tlhelp32.h> 后面