至尊骨"/>
算法给小码农堆排序至尊骨
文章目录
- 堆排序
- 升序
- 一种非常正常的想法 空间复杂度O(N)
- 堆升序函数HeapSort
- 堆排序测试函数
- 建堆(向上向下为建堆)
- 向上调整(建大堆)
- 交换排序&&再向上调整
- 堆排序代码
- 堆排序测试
- 向下调整
- 排升序 构建小堆
- 排升序 构建大堆
- 堆排序
- 测试堆排序
- 降序
- 向上调整 (建小堆)
- 向下调整(建小堆)
- 建堆的时间复杂度
堆排序
升序
一种非常正常的想法 空间复杂度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)
更多推荐
算法给小码农堆排序至尊骨
发布评论