堆的排序

排序算法是一种非常有用的算法,有很广泛的应用场景,排序算法也有很多种,之前给大家介绍过冒泡排序,冒泡排序是一种非常经典的排序算法,但是由于其效率不高,时间复杂度为o(n^2); 在面对海量数据时他的使用就收到了限制(太弱鸡了),因此我们今天给大家介绍一种新的更加高效的排序算法----堆排序.其时间复杂度为n(log2)n ,比起冒泡排序来,效率更高.

堆排序本质上是堆的应用,首先,通过堆的调整算法将数组调整为堆,其次利用删除堆顶元素的思想,每次将堆顶元素和堆尾元素交换,然后在通过堆的调整算法重新使其成为堆.,然后再交换 再调整,交换是为了将最大元素或者最小元素选出来,调整是为了生成第二大或第二小的元素.如此 交换 —调整----交换调整,直至元素满足排序结果****

注意事项: 如果要升序 应该要建大堆 ,降序则建小堆 具体代码和注解入下(代码以升序为例)

#include<stdlib.h> #include<stdio.h> // 交换函数 // 输入 两个变量的地址 // 处理:函数功能 swap(int *x, int *y){ int tmp = *x; *x = *y; *y = tmp; } //堆排序思路: // 1 建堆 大堆(升序) 小堆(降序) 以大堆为例 // 2 排序 利用删除堆顶元素的思想(先交换,再调整) //堆的调整 // 输入: 一个数组 (数组大小,数组元素) 调整的起始点 // 处理: 函数实现的功能 //输出: 一个满足堆性质的堆 void HeapAdjust(int *array, int size, int parent){ int child = parent * 2 + 1; while (child < size){ // 先找到左右孩子中较大的那个 if (child + 1 < size && array[child + 1] > array[child]){ child += 1; } //找到那个较大的孩子之后,将其与双亲进行比较 // 如果大于其双亲则将两者进行交换 if (array[child] > array[parent]){ swap(&array[child], &array[parent]); //交换完成以后,让parent继续往下走,继续调整 parent = child; child = parent * 2 + 1; } else{ return; } } } //堆的排序 void HeapSort(int *array, int size){ // 1建堆(大堆); // root 为堆中第一个非叶子节点 int root = ((size - 2) >> 1); for (; root >= 0; --root){ HeapAdjust(array, size, root); } // 2 排序 int end = size - 1; while (end){ swap(&array[0], &array[end]); HeapAdjust(array, end, 0); end--; } } // 测试 void testheap(){ int array[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; HeapSort(array, sizeof(array) / sizeof(array[0])); for (int i = 0; i < 10; ++i){ printf("%d \n", array[i]); } } int main(){ testheap(); system("pause"); return 0; }