排序算法--堆排序【图文详解】

“留在码头的船才最安全” “但亲爱的，那不是造船的目的。

堆--插入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);}
}