#yyds干货盘点#算法给小码农堆排序至尊骨 _盘点

白日放歌须纵酒，青春作伴好还乡。这篇文章主要讲述#yyds干货盘点#算法给小码农堆排序至尊骨相关的知识，希望能为你提供帮助。
堆排序升序一种非常正常的想法空间复杂度O(N)
堆升序函数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");

建堆（向上向下为建堆）
向上调整(建大堆)【#yyds干货盘点#算法给小码农堆排序至尊骨】==上面做法一点毛病都没有，但是有要求了，空间复杂度为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");

降序向上调整（建小堆）