排序算法--堆排序【图文详解】
“留在码头的船才最安全” “但亲爱的，那不是造船的目的。
堆--插入heapInsert
原来有一个大根堆，如图：
-
现在要新插入一个数字50，进行插入
-
流程：和父亲相比，如果比父亲大，和父亲交换，直到不比父亲大，或者来到0位置
void heapInsert(vector<int>& arr, int i) {
while (arr[i] > arr[(i - 1) / 2]) {
swap(arr[i], arr[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
-
插入50
-
50比13大，交换
-
50比20大，交换
-
50比40大，交换
调整成功！
-
由于完全二叉树有n个节点，会有logn深度，因此插入的时间复杂度是O(logn)
堆调整 heapify
还是上面的那个例子，想把0位置的40，改为4，此时破坏了大根堆的性质，如何调整？
-
假设当前下标为i，如果i位置有左孩子和右孩子，则左孩子的下标为
l=i*2+1，右孩子为l+1 -
左右孩子比较出最大的孩子
-
最大的孩子和当前数字比较，如果孩子大，那么交换，如果是自己大，那么不动
-
4和20交换
-
4和13交换
-
堆调整完成，时间复杂度O(logn)
void heapify(vector<int>& arr, int i, int size) {
//可能没有左孩子
int l = i * 2 + 1;//左孩子下标
while (l < size) {
//有左孩子
//右孩子：l+1
//评选，左右孩子的最强的孩子下标是什么
//1次比较！！
int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
//上面已经选最强的孩子，接下来，当前的数字，和最强的孩子之前，最强下标是谁？
//2次比较！！
best = arr[best] > arr[i] ? best : i;
if (best == i) {
break;//最强的是自己，不用向下调整了
}
//最强孩子比自己更强
swap(arr[best], arr[i]);
i = best;
l = i * 2 + 1;
}
}
堆排序
-
从顶到底建立堆的时间复杂度是
O(nlogn) -
大数归为的时间复杂度是
O(nlogn) -
因此总时间复杂度
O(nlogn)
void heapInsert(vector<int>& arr, int i) {
while (arr[i] > arr[(i - 1) / 2]) {
swap(arr[i], arr[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
void heapify(vector<int>& arr, int i, int size) {
//可能没有左孩子
int l = i * 2 + 1;//左孩子下标
while (l < size) {
//有左孩子
//右孩子：l+1
//评选，左右孩子的最强的孩子下标是什么
//1次比较！！
int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
//上面已经选最强的孩子，接下来，当前的数字，和最强的孩子之前，最强下标是谁？
//2次比较！！
best = arr[best] > arr[i] ? best : i;
if (best == i) {
break;//最强的是自己，不用向下调整了
}
//最强孩子比自己更强
swap(arr[best], arr[i]);
i = best;
l = i * 2 + 1;
}
}
void heapsort1(vector<int>& arr) {
//1.建堆
int n = arr.size();
for (int i = 0;i < n;i++) {
heapInsert(arr,i);
}
//2.大数归位
int size = n;
while (size > 1) {
swap(arr[0], arr[--size]);//0位置的数字和最后一个交换
heapify(arr, 0, size);//再调整0位置这个数字
}
}
-
从底到顶建堆时间复杂度是
O(n),会比自顶向底快一点，但总的时间复杂度不变，都是O(nlogn) -
大数归为的时间复杂度是
O(nlogn) -
因此总时间复杂度
O(nlogn)
void heapify(vector<int>& arr, int i, int size) {
//可能没有左孩子
int l = i * 2 + 1;//左孩子下标
while (l < size) {
//有左孩子
//右孩子：l+1
//评选，左右孩子的最强的孩子下标是什么
//1次比较！！
int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
//上面已经选最强的孩子，接下来，当前的数字，和最强的孩子之前，最强下标是谁？
//2次比较！！
best = arr[best] > arr[i] ? best : i;
if (best == i) {
break;//最强的是自己，不用向下调整了
}
//最强孩子比自己更强
swap(arr[best], arr[i]);
i = best;
l = i * 2 + 1;
}
}
void heapsort2(vector<int>& arr) {
int n = arr.size();
for (int i = n - 1;i >= 0;i--) {
heapify(arr, i, n);
}
//2.大数归位和heapsort1一样的代码
int size = n;
while (size > 1) {
swap(arr[0], arr[--size]);
heapify(arr, 0, size);
}
}
