堆排序
升序
一种非常正常的想法 空间复杂度O(N)
把数组中的元素全都push到小堆中，然后再取堆顶元素重新给数组，就可以达到升序的效果了
堆升序函数HeapSort
//升序 void HeapSort(HPDataType* a,int n) { HP hp; HeapInit(&hp); int i = 0; //建立一个小堆 for (i = 0; i < n; i++) { HeapPush(&hp, a[i]); } //然后把堆顶的元素重新放到数组里面 for (i = 0; i < n; i++) { a[i] = HeapTop(&hp); //用完pop掉 HeapPop(&hp); } HeapDestroy(&hp); }
堆排序测试函数
void testHeapSort() { int a[] = { 40,2,0,12,5,454,2323 }; //堆排序 HeapSort(a, sizeof(a) / sizeof(a[0])); int i = 0; for (i = 0; i < sizeof(a) / sizeof(a[0]); i++) { //把数组里面的元素取出来 printf("%d ",a[i]); } printf("\n"); }
建堆（向上向下为建堆）
向上调整(建大堆)
上面做法一点毛病都没有，但是有要求了，空间复杂度为O(1) 也就是我们不可以在用Heap了
（这里的插入不是真正的插入，因为这些数据原本就在里面，我们就是在调堆，类似插入）
看到上面打印的结果我们看到建的是小堆，但是不好的是最小的在下标为0的位置，再次找次小的，从下标为一的位置再构建，这是不行的，因为会破坏结构，所以我们要重头建大堆，然后收尾交换
//真正玩法 void HeapSort(HPDataType* a, int n) { assert(a && n>=0); //把数组a构建成堆 int i = 0; for (i = 0; i < n; i++) { AdjustUp(a,n,i); } }
交换排序&&再向上调整
堆排序代码
//真正玩法 void HeapSort(HPDataType* a, int n) { assert(a && n>=0); //把数组a构建成堆 int i = 0; //向上调整 for (i = 0; i < n; i++) { AdjustUp(a,i); } //根与最后一个数交换并每次都找到次大的数 int tail = n - 1; while (tail) { Swap(&a[0], &a[tail]);//根与最后一个数交换 tail--; for (i = 0; i <= tail; i++) { AdjustUp(a, i); } } }
堆排序测试
void testHeapSort() { int a[] = { 40,2,50,12,5,454,2323,}; //堆排序 HeapSort(a, sizeof(a) / sizeof(a[0])); int i = 0; for (i = 0; i < sizeof(a) / sizeof(a[0]); i++) { //把数组里面的元素取出来 printf("%d ",a[i]); } printf("\n"); }
向下调整
排升序 构建小堆
排升序 构建大堆
有种就是这样玩的
堆排序
//真正玩法 void HeapSort(HPDataType* a, int n) { assert(a && n>=0); //把数组a构建成堆 int i = 0; 向上调整 //for (i = 0; i < n; i++) //{ // AdjustUp(a,n,i); //} //向下调整 for (i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } //根与最后一个数交换并每次都找到次大的数 int tail = n - 1; for (i = tail; i > 0; i--) { Swap(&a[0],&a[i]);//根与最后一个数交换 AdjustDown(a, i, 0);//向下调整每次都找到次大的数 } }
测试堆排序
void testHeapSort() { int a[] = { 40,2,50,12,5,454,232,30,3,10 }; //堆排序 HeapSort(a, sizeof(a) / sizeof(a[0])); int i = 0; for (i = 0; i < sizeof(a) / sizeof(a[0]); i++) { //把数组里面的元素取出来 printf("%d ",a[i]); } printf("\n"); }
降序
向上调整 （建小堆）
向下调整（建小堆）
建堆的时间复杂度
3.2.3 建堆时间复杂度因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
所以时间复杂度是O(n)
