java代码实现排序算法详解( 三 ) _排序算法

5.4 图示

文章插图

文章插图

6、堆排序? 选择排序。将待排序列构造诚大根堆，根节点则为序列中最大元素，将该节点与最后一个值交换，把剩余的节点重新构建大根堆，继续进行交换，直到待排序列只剩下一个值。
? 大根堆（大顶堆）：父节点一定大于两个子节点的值，即：arr[i] > arr[2i+1] && arr[i] > arr[2i+2]
【java代码实现排序算法详解】? 将大根堆映射到数组中示例：
6.1 算法步骤

将待排序数组构建成大根堆（仍然是无序的），根节点则为数组最大值
将根节点和最后一个节点进行交换，则最大值放到了数组尾部，此时 a[0] ~ a[n-1] 无序
因为步骤2进行了节点交换，需要对 a[0] ~ a[n-1] 重新构建大根堆
重复步骤 2，3 直到全部有序

6.2 时间复杂度

初始化大根堆

? 设元素个数为 n，建堆的高度 (k=log_2(n+1))，
? 第 i 层的非叶子节点的最大操作（交换）次数为 k-i
? 第 i 层的节点个数为 (2^{i-1})
? 所以第 i 层总共需要操作 ((k-i)(2^{i-1})) 次，总共需要操作的次数为
[S = (k-1)*2^0 + (k-2)*2^{1}+(k-3)*2^2+cdots+(k-(k-1))*2^{k-1-1} ]

? 用 2S - S计算 S 的值:
[S = 2^1+2^2+cdots+2^{k-1}-(k-1)\ S = 2^k-k-1 ]

? 将 (k=log_2{(n+1)}Approx log_2n) 代入得
[O(n) = n - log_2n-1 \取最高项O(n) = n ]

? 则初始化大根堆的时间复杂度 O(n) = n
2.重新调整堆
? 根节点和待排序数组的最后一个元素 a[i] 交换之后，需要重新调整堆，最大调整次数 = a[i] 所在堆的层数 = (log_2i)，总共需要调整的次数 = ((n-1)(log_2n)) ，所以调整堆的时间复杂度为
[O(n) = nlog_2n ]

总的时间复杂度 (O(n) = n + nlog_2n = nlog_2n)
6.3 代码实现

public static int[] HeapSort(int[] arr) { int len = arr.length; // 对所有元素建立大根堆 buildMaxHeap(arr, len); // 从数组尾开始进行循环，每次找到待排序序列的最大值 for (int i = arr.length - 1; i > 0; i--) {// 此时arr[0]为最大值，交换根节点arr[0]和最后一个节点 iswap(arr, 0, i);len--;// 剩余元素重新建堆heapify(arr, 0, len); } return arr;}private static void buildMaxHeap(int[] arr, int len) { for (int i = len / 2; i >= 0; i--) {heapify(arr, i, len); }}/** * @param arr排序数组 * @param parent 父节点下标 * @param len待排序数组 length */private static void heapify(int[] arr, int parent, int len) { // 计算父节点的两个子节点下标 int left = 2 * parent + 1; int right = 2 * parent + 2; // largest为父节点和子节点最大值的下标 int largest = parent; // 比较左右子节点和父节点的大小 if (left < len && arr[left] > arr[largest]) {largest = left; } if (right < len && arr[right] > arr[largest]) {largest = right; } // 如果当前的最大值不是当前父节点，需要进行元素交换，// 交换之后的子节点作为父节点时不一定是大根堆，需要重新建堆 if (largest != parent) {swap(arr, parent, largest);heapify(arr, largest, len); }}private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}

6.4 图示初始化大根堆：