柚子快报邀请码778899分享：排序算法 算法 C++堆排序
第一步: 我们将待排序数组形象成一个堆结构，并将其调整为最大堆(堆结构:左孩子的下标是2*i+1，右孩子下标2*i+2) (最大堆的特点:在这个堆结构里，任何一个父节点的值都大于其子节点的值) t的值) 第二步: 将堆顶元素与待排序数组（假设待排序的数据数量为nums)最后一个元素进行交换，swap(a[0], a[nums-1]); 第三步: 待排序的数据量减少一个,即num--;将待排序数组重新调整成最大堆结构，重复第二步，循环n-1次，将所有数据排序完成。 初始化堆（讲数组调整成最大堆) 从最后一个父节点开始调整（即i= n/2-1) 下面演示将数组{20,30,90,40,70,110,60,10,100,50,80}转换为最大堆{110,100,90,40,80,20,60,10,30,50,70}的步骤。
注释代码
//交换函数
void adjustHeap(vector
int father = start;
int child = 2 * father + 1;//左孩子下标
while (child < end) {
//通过这个if条件比较完，child记录的就是较大那个孩子的下标
//同时还要判断child+1会不会越界
if (child + 1 < end && arr[child] < arr[child + 1]) {//若右孩子大于左孩子，则左孩子下标+1=右孩子下标
child++;
}
if (arr[child] > arr[father]) {//判断较大的孩子的值是否大于父节点的值，若大，则完成交换
swap(arr[child], arr[father]);
}
else//如果不大于父节点的值，则直接跳出循环，因为尽管以下还有数据，但都是已经交换好的了，因为本函数是从最后一个父节点开始遍历的
{
return;
}
//如果发生了交换则将当前孩子的下标作为父节点下标
father = child;
child = 2 * father + 1;
}
}
void heapSort(vector
int n = arr.size();
//从最后一个父节点开始向前调整
for (int i = n / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, n);
}
//完成从小到大的排列，每次首尾交换
//n个数会完成n-1次交换
while (n - 1) {
swap(arr[0], arr[n - 1]);
//从0开始一直排到最后一个数，0即根节点
adjustHeap(arr, 0, n - 1);
n--;
}
}
完整代码：与上面的大体一样，只是重敲一遍
#include
#include
using namespace std;
void adjustHeap(vector
int father = start;
int child = 2 * father + 1;
while (child < end) {
if (child + 1 < end&&arr[child + 1] > arr[child]) {
child++;
}
if (arr[father] < arr[child]) {
swap(arr[father], arr[child]);
}
else {
return;
}
father = child;
child = 2 * father + 1;
}
}
void HeapSort(vector
int n = arr.size();
if (n <= 1) {
return;
}
for (int i = n / 2; i >= 0; i--) {
adjustHeap(arr, i, n);
}
while (n - 1) {
swap(arr[0], arr[n - 1]);
adjustHeap(arr, 0, n - 1);
n--;
}
}
void printArr(vector
int n = arr.size();
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
vector
HeapSort(arr);
printArr(arr);
return 0;
}
堆排序
构建出最大堆的时间复杂度为n
由于是完全二叉树，分log2n层，每次遍历n次
时间复杂度：
因为选择是没有顺序的，所以选择排序不能提前退出，不管是什么序列，都需要执行完整的排序过程。
最优：O(nlogn)
最差：O(nlogn)
平均：O(nlogn)
空间复杂度：
不需要额外的空间占用，所以为O(1)。
柚子快报邀请码778899分享：排序算法 算法 C++堆排序
发表评论