原地堆排序

原地堆排序基本理解

基于堆相关的操作,我们可以很容易的定义堆排序。例如,假设我们已经读入一系列数据并创建了一个堆,一个最直观的算法就是反复的调用extractMax函数,因为该函数总是能够返回堆中最大的值,然后把它从堆中删除,从而对这一系列返回值的输出就得到了该序列的降序排列。真正的原地堆排序使用了另外一个小技巧。

堆排序的过程

  1. 创建一个堆$H[0…n-1]$
  2. 把堆首(最大值)和堆尾互换
  3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
  4. 重复步骤2,直到堆的尺寸为1

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package Heap.HeapSort;

/**
* @ Description: 利用堆的shiftDown思想实现堆排序,不需要堆数据结构
* @ Date: Created in 09:04 2018/7/31
* @ Author: Anthony_Duan
*/
public class HeapSortInPlace {
private HeapSortInPlace(){}

public static void sort(Comparable[] arr) {

int n =arr.length;


/**
* 因为是原地排序 所以索引从0开始
* 从(最后一个元素索引-1)/2开始
* 最后一个元素索引n-1
*
* 第一个for循环是将一个数组转化为堆
* 第二个for循环是将堆中第一个元素(最大值)与最后一个元素进行交换
* 此时最大值已经在属于它的位置上了,
* 对数组第一个到倒数第二个的执行shiftDown操作 此时又是一个最大堆
* 执行到最后所有元素都会按从小到大排列
*/
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
shiftDown2(arr, n, i);
}

for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
shiftDown2(arr, i, 0);
}
}


private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

/**
* 原始shiftDown过程
* @param arr
* @param n
* @param k
*/
private static void shiftDown(Comparable[] arr, int n, int k) {
while (2 * k + 1 < n) {
int j = 2 * k + 1;
if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
j += 1;
}
if (arr[k].compareTo(arr[j]) >= 0) {
break;
}
swap(arr, k, j);
k = j;
}
}

/**
* 优化版shiftDown过程,使用赋值的方式取代不断的swap
* 这个优化的思路与优化插入排序的思路一样
* @param arr
* @param n
* @param k
*/
private static void shiftDown2(Comparable[] arr, int n, int k) {
Comparable e = arr[k];
while (2 * k + 1 < n) {
int j = 2 * k + 1;
if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
j += 1;
}
if (e.compareTo(arr[j]) >= 0) {
break;
}
arr[k] = arr[j];
k = j;
}
arr[k] = e;

}
public static void main(String[] args) {

int N = 1000000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
SortTestHelper.testSort("Heap.HeapSort.HeapSortInPlace", arr);

return;
}
}
-------------End Of This ArticleThank You For Reading-------------