堆排及时间复杂度分析

箴言:

初始阶段，不需要去纠结那一种更优美，非要找出那一种是最好的，其实能解决问题的就是好办法。

一，常见排序时间复杂度

	冒泡	快排	归并	堆排	桶排
时间	O(n^2)	O(nlogn)	O(nlogn)	O(nlogn)	kn
空间	O(1)	O(1)	O(nlogn)	O(1)	kn

二，堆排

前情提要:

堆属于完全树，完全树可以理解为一个数组。如果不是完全树，就没办法和数组等价，就不会有下面这种父级和子级之间的关系。

已知父级下标i
左孩子下标: 2*i+1
右孩子下标: 2*i+2
已知孩子结点j(无论左还是右)
父级下标 (j-1)/2

堆排序过程:

堆排序分成两个阶段，第一个阶段从由无序数组建立一个大/小根堆，第二个阶段在大/小根堆的基础上调整，形成有序数组。

从无序数组到大根堆：

对于数组中每一个元素，我们需要将其和其父级做对比，若比父级大，则进行交换，直到最顶层为止。

代码:(其实找父亲的时候可以不区分左右减一除二即可，我这里就不改了)

    public static void builddui(int[] arr) {for (int i = 0; i < arr.length; i++) {int j = i;int p = 0;if (j % 2 == 1) {//左孩子p = (j - 1) / 2;} else {p = (j - 2) / 2;//右孩子}while (p >= 0 && arr[p] < arr[j]) {int t = arr[p];//交换位置arr[p] = arr[j];arr[j] = t;j = p;p = (j - 1) / 2;}}}

从大根堆到有序序列:

最后一个位置和堆顶交换，将交换之后的堆顶下沉到正确的位置。然后堆顶和倒数第二个交换，堆顶下沉到正确的位置，直到剩下一个为止。这是一个堆顶元素不断下沉的过程。

代码:(r表示的是最后一个的索引位置)

    public static void weichidui(int[] arr, int r) {int t = arr[r];arr[r] = arr[0];arr[0] = t;int cur = 0;//当前下标while (2 * cur + 1 < r) {int index = 2 * cur + 1;int maxv = arr[index];if (2 * cur + 2 < r && arr[index] < arr[2 * cur + 2]) {index = 2 * cur + 2;maxv = arr[2 * cur + 2];}if (maxv > arr[cur]) {int tmp = arr[cur];arr[cur] = arr[index];arr[index] = tmp;}cur = index;}}

时间复杂度分析:

上述两个阶段分别分析: 从无序序列到建成大顶堆: 已知数组中数量为n,每正确插入一个元素，时间复杂度为logn(因为树的深度为logn)，因为插入n个元素，时间复杂度为nlogn。

从大顶堆到有序序列:每次首尾交换之后都需要将堆顶元素下沉到正确的位置，时间复杂度为logn(因为树的深度为logn，比较交换次数其实是小于logn的，但是理解为logn就行)，需要下沉n次，所以时间复杂度是nlogn。

ABOVE ALL，堆排时间复杂度为2nlogn,也就是O(nlogn),一切操作都是在原数组上进行的操作，所以空间复杂度为O(1)。

堆排序是一个完美的排序方式，无论时间或者空间，数据量小的时候差距不明显，数据量越大，优势就会越明显。

代码:

数组:[34,56,23,33,5,46,4,57,6,76,34,42,634,6,536,3,3423,3,1,5,537,3,57,3563,4,65,764,4]

import java.util.Arrays;/*** @Author YuLing* @Date 2024-02-07 19:14* @Description:* @Version 1.0*/
public class dui {public static void main(String[] args) {int[] arr = new int[]{34,56,23,33,5,46,4,57,6,76,34,42,634,6,536,3,3423,3,1,5,537,3,57,3563,4,65,764,4};builddui(arr);System.out.println(Arrays.toString(arr));for (int i = 0; i < arr.length; i++) {weichidui(arr,  arr.length - 1 - i);}System.out.println(Arrays.toString(arr));}public static void builddui(int[] arr) {for (int i = 0; i < arr.length; i++) {int j = i;int p = 0;if (j % 2 == 1) {//左孩子p = (j - 1) / 2;} else {p = (j - 2) / 2;//右孩子}while (p >= 0 && arr[p] < arr[j]) {int t = arr[p];//交换位置arr[p] = arr[j];arr[j] = t;j = p;p = (j - 1) / 2;}}}public static void weichidui(int[] arr, int r) {int t = arr[r];arr[r] = arr[0];arr[0] = t;int cur = 0;//当前下标while (2 * cur + 1 < r) {int index = 2 * cur + 1;int maxv = arr[index];if (2 * cur + 2 < r && arr[index] < arr[2 * cur + 2]) {index = 2 * cur + 2;maxv = arr[2 * cur + 2];}if (maxv > arr[cur]) {int tmp = arr[cur];arr[cur] = arr[index];arr[index] = tmp;}cur = index;}}
}

输出:

[3563, 634, 3423, 57, 537, 764, 76, 34, 6, 56, 57, 46, 536, 4, 6, 3, 33, 3, 1, 5, 5, 3, 34, 23, 4, 42, 65, 4]
[1, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 23, 33, 34, 34, 42, 46, 56, 57, 57, 65, 76, 536, 537, 634, 764, 3423, 3563]