排序算法--堆排序【图文详解】
“留在码头的船才最安全” “但亲爱的，那不是造船的目的。
堆--插入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);}
}