经典排序之 堆排序（附两种建堆思路及代码）

堆排序

先做下记录，后序加上讲解
两种建立堆，一种就地，一种是插入

buildMaxHeap

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
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while (scan.hasNext()) {
			int num = Integer.parseInt(scan.nextLine());
			String[] inputs = scan.nextLine().split(" ");
			int[] origins = new int[num];
			int i = 0;
			for (String s : inputs) {
				origins[i++] = Integer.parseInt(s);
			}
			heapSort(origins, num);
			for (int oi = num - 1; oi >= 0; oi--)
				System.out.print(origins[oi] + " ");
			System.out.println();
		}
	}
	public static void heapSort(int[] arr, int length) {
		buildHeapInPlace(arr, length);
		for (int i = 0; i < length; i++) {
			swap(arr, 0, length - 1 - i);
			minHeap(arr, 0, length - 1 - i);
		}
	}
	public static void buildHeapInPlace(int[] arr, int length) {
		for (int i = (length - 1 - 1) >>> 1; i >= 0; i--)
			minHeap(arr, i, length);
	}
	public static void minHeap(int[] arr, int mark, int length) {
		int left = (mark << 1) + 1;
		int right = (mark << 1) + 2;
		while (left < length) {
			int min = left;
			if (right < length && arr[right] < arr[left])
				min = right;
			if (arr[min] < arr[mark]) {
				swap(arr, min, mark);
				mark = min;
				left = (mark << 1) + 1;
				right = (mark << 1) + 2;
			} else {
				break;
			}
		}
	}
	public static void swap(int[] arr, int one, int two) {
		int temp = arr[one];
		arr[one] = arr[two];
		arr[two] = temp;
	}
}

maxHeapInsert

逐个插入，建立堆

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while (scan.hasNext()) {
			int num = Integer.parseInt(scan.nextLine());
			String[] inputs = scan.nextLine().split(" ");
			int[] origins = new int[num];
			int i = 0;
			for (String s : inputs) {
				origins[i++] = Integer.parseInt(s);
			}
			heapSortTwo(origins, num);
			for (int oi = num - 1; oi >= 0; oi--)
				System.out.print(origins[oi] + " ");
			System.out.println();
		}
	}
	public static void heapSortTwo(int[] arr, int length) {
		int[] copy = buildHeapInsert(arr, length);
		for (int i = 0; i < length; i++) {
			swap(copy, 0, length - 1 - i);
			minHeapDown(copy, 0, length - 1 - i);
		}
		System.arraycopy(copy, 0, arr, 0, length);
	}
	/**
	 * 逐个插入建立最小堆
	 * @param arr
	 * @param length
	 */
	public static int[] buildHeapInsert(int[] arr, int length) {
		int[] heapArr = new int[length];
		int heapLength = 0;
		for (int i = 0; i < length; i++) {
			heapArr[i] = arr[i];
			minHeapUp(heapArr, i, ++heapLength);
		}
		return heapArr;
	}
	/**
	 * 维持堆的性质 上溯
	 * @param arr
	 * @param mark
	 * @param length
	 */
	public static void minHeapUp(int[] arr, int mark, int length) {
		int parent = (mark - 1) >> 1;
		while (parent >= 0) {
			if (arr[parent] > arr[mark]) {
				swap(arr, parent, mark);
				mark = parent;
				parent = (mark - 1) >> 1;
			} else {
				break;
			}
		}
	}
	
	public static void heapSortOne(int[] arr, int length) {
		buildHeapInPlace(arr, length);
		for (int i = 0; i < length; i++) {
			swap(arr, 0, length - 1 - i);
			minHeapDown(arr, 0, length - 1 - i);
		}
	}
	
	/**
	 * 就地改变数组，建立堆
	 * @param arr
	 * @param length
	 */
	public static void buildHeapInPlace(int[] arr, int length) {
		for (int i = (length - 1 - 1) >>> 1; i >= 0; i--)
			minHeapDown(arr, i, length);
	}
	/**
	 * 维持堆的性质 下溯
	 * @param arr
	 * @param mark
	 * @param length
	 */
	public static void minHeapDown(int[] arr, int mark, int length) {
		int left = (mark << 1) + 1;
		int right = (mark << 1) + 2;
		while (left < length) {
			int min = left;
			if (right < length && arr[right] < arr[left])
				min = right;
			if (arr[min] < arr[mark]) {
				swap(arr, min, mark);
				mark = min;
				left = (mark << 1) + 1;
				right = (mark << 1) + 2;
			} else {
				break;
			}
		}
	}
	public static void swap(int[] arr, int one, int two) {
		int temp = arr[one];
		arr[one] = arr[two];
		arr[two] = temp;
	}
}

备注

可以通过这个牛客网 在线排序 OJ 检测自己排序算法

http://www.nowcoder.com/questionTerminal/508f66c6c93d4191ab25151066cb50ef