折半插入排序
折半插入排序是對直接插入排序的簡單改進。此處介紹的折半插入，其實就是通過不斷地折半來快速確定第i個元素的
插入位置，這實際上是一種查找算法：折半查找。Java的Arrays類里的binarySearch()方法，就是折半查找的實現，用
于從指定數組中查找指定元素，前提是該數組已經處于有序狀態。與直接插入排序的效果相同，只是更快了一些，因
為折半插入排序可以更快地確定第i個元素的插入位置
代碼：
java" id="highlighter_495669">
|
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
|
package interview; /** * @author Administrator * 折半插入排序 */public class BinaryInsertSort { public static void binaryInsertSort(DataWrap[] data) { System.out.println("開始排序"); int arrayLength = data.length; for (int i = 1; i < arrayLength; i++) { DataWrap temp = data[i]; int low = 0; int high = i - 1; while (low <= high) { int mid = (low + high) / 2; if (temp.compareTo(data[mid]) > 0) { low = mid + 1; } else { high = mid - 1; } } for (int j = i; j > low; j--) { data[j] = data[j - 1]; } data[low] = temp; System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); binaryInsertSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } |
結果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
排序之前：[9, -16, 21*, 23, -30, -49, 21, 30*, 30]開始排序[-16, 9, 21*, 23, -30, -49, 21, 30*, 30][-16, 9, 21*, 23, -30, -49, 21, 30*, 30][-16, 9, 21*, 23, -30, -49, 21, 30*, 30][-30, -16, 9, 21*, 23, -49, 21, 30*, 30][-49, -30, -16, 9, 21*, 23, 21, 30*, 30][-49, -30, -16, 9, 21, 21*, 23, 30*, 30][-49, -30, -16, 9, 21, 21*, 23, 30*, 30][-49, -30, -16, 9, 21, 21*, 23, 30, 30*]排序之后：[-49, -30, -16, 9, 21, 21*, 23, 30, 30*] |
冒泡排序
代碼：
|
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
|
package interview; /** * @author Administrator * 冒泡排序 */public class BubbleSort { public static void bubbleSort(DataWrap[] data) { System.out.println("開始排序"); int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { boolean flag = false; for (int j = 0; j < arrayLength - 1 - i; j++) { if (data[j].compareTo(data[j + 1]) > 0) { DataWrap temp = data[j + 1]; data[j + 1] = data[j]; data[j] = temp; flag = true; } } System.out.println(java.util.Arrays.toString(data)); if (!flag) break; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); bubbleSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } |
運行結果：
|
1
2
3
4
5
6
7
8
9
10
11
|
排序之前：[9, -16, 21*, 23, -30, -49, 21, 30*, 30]開始排序[-16, 9, 21*, -30, -49, 21, 23, 30*, 30][-16, 9, -30, -49, 21*, 21, 23, 30*, 30][-16, -30, -49, 9, 21*, 21, 23, 30*, 30][-30, -49, -16, 9, 21*, 21, 23, 30*, 30][-49, -30, -16, 9, 21*, 21, 23, 30*, 30][-49, -30, -16, 9, 21*, 21, 23, 30*, 30]排序之后：[-49, -30, -16, 9, 21*, 21, 23, 30*, 30] |
桶式排序
算法的時間效率：時間效率極高，只需經過兩輪遍歷即可算法的空間效率：空間開銷較大，需要兩個數組來完成，算
法的穩定性：穩定
代碼：
|
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
|
package interview; import java.util.Arrays; /** * @author Administrator * 桶式排序 */public class BucketSort { public static void bucketSort(DataWrap[] data, int min, int max) { System.out.println("開始排序"); int arrayLength = data.length; DataWrap[] temp = new DataWrap[arrayLength]; int[] buckets = new int[max - min]; for (int i = 0; i < arrayLength; i++) { buckets[data[i].data - min]++; } System.out.println(Arrays.toString(buckets)); for (int i = 1; i < max - min; i++) { buckets[i] = buckets[i] + buckets[i - 1]; } System.out.println(Arrays.toString(buckets)); System.arraycopy(data, 0, temp, 0, arrayLength); for (int k = arrayLength - 1; k >= 0; k--) { data[--buckets[temp[k].data - min]] = temp[k]; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(5, ""), new DataWrap(-1, ""), new DataWrap(8, ""), new DataWrap(5, "*"), new DataWrap(7, ""), new DataWrap(3, ""), new DataWrap(-3, ""), new DataWrap(1, ""),new DataWrap(3, "*")}; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); bucketSort(data, -3, 10); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } |
結果
|
1
2
3
4
5
6
7
|
排序之前：[9, 5, -1, 8, 5*, 7, 3, -3, 1, 3*]開始排序[1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 1, 1][1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 8, 9, 10]排序之后：[-3, -1, 1, 3, 3*, 5, 5*, 7, 8, 9] |
堆排序
代碼：
|
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
|
package interview; /** * @author Administrator * 堆排序 */public class HeapSort { public static void heapSort(DataWrap[] data) { System.out.println("開始排序"); int arrayLength = data.length; // 循環建堆 for (int i = 0; i < arrayLength - 1; i++) { // 建堆 builMaxdHeap(data, arrayLength - 1 - i); // 交換堆頂和最后一個元素 swap(data, 0, arrayLength - 1 - i); System.out.println(java.util.Arrays.toString(data)); } } // 對data數組從0到lastIndex建大頂堆 private static void builMaxdHeap(DataWrap[] data, int lastIndex) { // 從lastIndex處節點（最后一個節點）的父節點開始 for (int i = (lastIndex - 1) / 2; i >= 0; i--) { // k保存當前正在判斷的節點 int k = i; // 如果當前k節點的子節點存在 while (k * 2 + 1 <= lastIndex) { // k節點的左子節點的索引 int biggerIndex = 2 * k + 1; // 如果biggerIndex小于lastIndex，即biggerIndex +1 // 代表k節點的右子節點存在 if (biggerIndex < lastIndex) { // 如果右子節點的值較大 if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) { // biggerIndex總是記錄較大子節點的索引 biggerIndex++; } } // 如果k節點的值小于其較大子節點的值 if (data[k].compareTo(data[biggerIndex]) < 0) { // 交換它們 swap(data, k, biggerIndex); // 將biggerIndex賦給k，開始while循環的下一次循環 // 重新保證k節點的值大于其左、右節點的值 k = biggerIndex; } else { break; } } } } // 交換data數組中i、j兩個索引處的元素 private static void swap(DataWrap[] data, int i, int j) { DataWrap temp = data[i]; data[i] = data[j]; data[j] = temp; } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); heapSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } |
結果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
排序之前：[9, -16, 21*, 23, -30, -49, 21, 30*, 30]開始排序[-16, 30, 21*, 23, -30, -49, 21, 9, 30*][-16, 23, 21*, 9, -30, -49, 21, 30, 30*][21, 9, 21*, -16, -30, -49, 23, 30, 30*][-49, 9, 21*, -16, -30, 21, 23, 30, 30*][-30, 9, -49, -16, 21*, 21, 23, 30, 30*][-30, -16, -49, 9, 21*, 21, 23, 30, 30*][-49, -30, -16, 9, 21*, 21, 23, 30, 30*][-49, -30, -16, 9, 21*, 21, 23, 30, 30*]排序之后：[-49, -30, -16, 9, 21*, 21, 23, 30, 30*] |
直接插入排序
|
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
|
package interview;public class InsertSort { public static void insertSort(DataWrap[] data){ System.out.println("開始排序"); int arrayLength = data.length; for(int i = 1;i < arrayLength;i++){ DataWrap temp = data[i]; if(data[i].compareTo(data[i-1]) < 0){ int j = i -1; for(;j >= 0 && data[j].compareTo(temp) > 0;j--){ data[j +1] = data[j]; } data[j + 1] = temp; } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); insertSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } |
結果
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
排序之前：[9, -16, 21*, 23, -30, -49, 21, 30*, 30]開始排序[-16, 9, 21*, 23, -30, -49, 21, 30*, 30][-16, 9, 21*, 23, -30, -49, 21, 30*, 30][-16, 9, 21*, 23, -30, -49, 21, 30*, 30][-30, -16, 9, 21*, 23, -49, 21, 30*, 30][-49, -30, -16, 9, 21*, 23, 21, 30*, 30][-49, -30, -16, 9, 21*, 21, 23, 30*, 30][-49, -30, -16, 9, 21*, 21, 23, 30*, 30][-49, -30, -16, 9, 21*, 21, 23, 30*, 30]排序之后：[-49, -30, -16, 9, 21*, 21, 23, 30*, 30] |
歸并排序
算法的時間效率：歸并算法需要遞歸地進行分解、合并，每進行一趟歸并排序，需要merge()方法一次，每次執行
merge()需要比較n次，較差，需要一個與原始序列同樣大小的輔助序列。算法的穩定性：穩定
代碼：
|
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
|
package interview; /** * @author Administrator * 歸并排序 */public class MergeSort { public static void mergeSort(DataWrap[] data) { // 歸并排序 sort(data, 0, data.length - 1); } // 將索引從left到right范圍的數組元素進行歸并排序 private static void sort(DataWrap[] data, int left, int right) { if(left < right){ //找出中間索引 int center = (left + right)/2; sort(data,left,center); sort(data,center+1,right); //合并 merge(data,left,center,right); } } // 將兩個數組進行歸并，歸并前兩個數組已經有序，歸并后依然有序 private static void merge(DataWrap[] data, int left, int center, int right) { DataWrap[] tempArr = new DataWrap[data.length]; int mid = center + 1; int third = left; int temp = left; while (left <= center && mid <= right) { if (data[left].compareTo(data[mid]) <= 0) { tempArr[third++] = data[left++]; } else { tempArr[third++] = data[mid++]; } } while (mid <= right) { tempArr[third++] = data[mid++]; } while (left <= center) { tempArr[third++] = data[left++]; } while (temp <= right) { data[temp] = tempArr[temp++]; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "") }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); mergeSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } |
結果：
|
1
2
3
4
|
排序之前：[9, -16, 21*, 23, -30, -49, 21, 30*, 30]排序之后：[-49, -30, -16, 9, 21*, 21, 23, 30*, 30] |
基數排序
基數排序已經不再是一種常規的排序方法，它更多地像是一種排序方法的應用，基數排序必須依賴于另外的排序方法。
基數排序的總體思路就是將待排數據拆分成多個關鍵字進行排序，也就是說，基數排序的實質是多關鍵字排序。
多關鍵字排序的思路是將待排數據里的排序關鍵字拆分成多個排序關鍵字：第1個子關鍵字、第2個子關鍵字、第3個子
關鍵字。。。然后，根據子關鍵字對待排數據進行排序。在進行多關鍵字排序時有兩種解決方案：
最高位優先法MSD
最低位優先法LSD
比較MSD法和LSD法，一般來講，LSD法要比MSD法來得簡單，因為LSD法是從頭到尾進行若干次分配和收集，執行
的次數取決于構成關鍵字值的成分為多少；而MSD法則要處理各序列與子序列的獨立排序問題，就可能復雜一些。
代碼：
|
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
|
package interview; import java.util.Arrays; /** * @author Administrator * 基數排序 */public class MultiKeyRadixSort { public static void radixSort(int[] data, int radix, int d) { System.out.println("開始排序："); int arrayLength = data.length; int[] temp = new int[arrayLength]; int[] buckets = new int[radix]; for (int i = 0, rate = 1; i < d; i++) { // 重置count數組，開始統計第二個關鍵字 Arrays.fill(buckets, 0); // 當data數組的元素復制到temp數組中進行緩存 System.arraycopy(data, 0, temp, 0, arrayLength); for (int j = 0; j < arrayLength; j++) { int subKey = (temp[j] / rate) % radix; buckets[subKey]++; } for (int j = 1; j < radix; j++) { buckets[j] = buckets[j] + buckets[j - 1]; } for (int m = arrayLength - 1; m >= 0; m--) { int subKey = (temp[m] / rate) % radix; data[--buckets[subKey]] = temp[m]; } System.out.println("對" + rate + "位上子關鍵字排序：" + java.util.Arrays.toString(data)); rate *= radix; } } public static void main(String[] args) { int[] data = { 1100, 192, 221, 12, 13 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); radixSort(data, 10, 4); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } |
結果
|
1
2
3
4
5
6
7
8
9
|
排序之前：[1100, 192, 221, 12, 13]開始排序：對1位上子關鍵字排序：[1100, 221, 192, 12, 13]對10位上子關鍵字排序：[1100, 12, 13, 221, 192]對100位上子關鍵字排序：[12, 13, 1100, 192, 221]對1000位上子關鍵字排序：[12, 13, 192, 221, 1100]排序之后：[12, 13, 192, 221, 1100] |
快速排序
代碼：
|
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
|
package interview; /** * @author Administrator * 快速排序 */public class QuickSort { private static void swap(DataWrap[] data, int i, int j) { DataWrap temp = data[i]; data[i] = data[j]; data[j] = temp; } private static void subSort(DataWrap[] data, int start, int end) { if (start < end) { DataWrap base = data[start]; int i = start; int j = end + 1; while (true) { while (i < end && data[++i].compareTo(base) <= 0) ; while (j > start && data[--j].compareTo(base) >= 0) ; if (i < j) { swap(data, i, j); } else { break; } } swap(data, start, j); subSort(data, start, j - 1); subSort(data, j + 1, end); } } public static void quickSort(DataWrap[] data){ subSort(data,0,data.length-1); } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "") }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); quickSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } |
結果
|
1
2
3
4
|
排序之前：[9, -16, 21*, 23, -30, -49, 21, 30*, 30]排序之后：[-49, -30, -16, 9, 21, 21*, 23, 30*, 30] |
直接選擇排序
代碼：
|
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
|
package interview; /** * @author Administrator * 直接選擇排序 */public class SelectSort { public static void selectSort(DataWrap[] data) { System.out.println("開始排序"); int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { for (int j = i + 1; j < arrayLength; j++) { if (data[i].compareTo(data[j]) > 0) { DataWrap temp = data[i]; data[i] = data[j]; data[j] = temp; } } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "") }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); selectSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
排序之前：[9, -16, 21*, 23, -30, -49, 21, 30*, 30]開始排序[-49, 9, 21*, 23, -16, -30, 21, 30*, 30][-49, -30, 21*, 23, 9, -16, 21, 30*, 30][-49, -30, -16, 23, 21*, 9, 21, 30*, 30][-49, -30, -16, 9, 23, 21*, 21, 30*, 30][-49, -30, -16, 9, 21*, 23, 21, 30*, 30][-49, -30, -16, 9, 21*, 21, 23, 30*, 30][-49, -30, -16, 9, 21*, 21, 23, 30*, 30][-49, -30, -16, 9, 21*, 21, 23, 30*, 30]排序之后：[-49, -30, -16, 9, 21*, 21, 23, 30*, 30] |
希爾排序
代碼：
|
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
|
package interview; /** * @author Administrator * Shell排序 */public class ShellSort { public static void ShellSort(DataWrap[] data) { System.out.println("開始排序"); int arrayLength = data.length; int h = 1; /** * 將數組分割成若干個子序列 */ while (h <= arrayLength / 3) { h = h * 3 + 1; System.out.println("h的結果：" + h); } while (h > 0) { System.out.println("===h的值：" + h + "==="); /** * 將分成的若干子序列進行直接插入排序 */ for (int i = h; i < arrayLength; i++) { DataWrap temp = data[i]; if (data[i].compareTo(data[i - h]) < 0) { int j = i - h; for (; j >= 0 && data[j].compareTo(temp) > 0; j -= h) { data[j + h] = data[j]; } data[j + h] = temp; } System.out.println(java.util.Arrays.toString(data)); } h = (h - 1) / 3; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); ShellSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } |
結果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
排序之前：[9, -16, 21*, 23, -30, -49, 21, 30*, 30]開始排序h的結果：4===h的值：4===[-30, -16, 21*, 23, 9, -49, 21, 30*, 30][-30, -49, 21*, 23, 9, -16, 21, 30*, 30][-30, -49, 21*, 23, 9, -16, 21, 30*, 30][-30, -49, 21*, 23, 9, -16, 21, 30*, 30][-30, -49, 21*, 23, 9, -16, 21, 30*, 30]===h的值：1===[-49, -30, 21*, 23, 9, -16, 21, 30*, 30][-49, -30, 21*, 23, 9, -16, 21, 30*, 30][-49, -30, 21*, 23, 9, -16, 21, 30*, 30][-49, -30, 9, 21*, 23, -16, 21, 30*, 30][-49, -30, -16, 9, 21*, 23, 21, 30*, 30][-49, -30, -16, 9, 21*, 21, 23, 30*, 30][-49, -30, -16, 9, 21*, 21, 23, 30*, 30][-49, -30, -16, 9, 21*, 21, 23, 30*, 30]排序之后：[-49, -30, -16, 9, 21*, 21, 23, 30*, 30] |
所需要的工具類：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
package interview;public class DataWrap implements Comparable<DataWrap>{ int data; String flag; public DataWrap(int data, String flag) { this.data = data; this.flag = flag; } public String toString(){ return data + flag; } @Override public int compareTo(DataWrap dw) { return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1); } } |
以上代碼親測可用，供大家參考。
關于java實現的各種排序算法代碼示例的內容，就到這里，希望對大家有所幫助。有什么問題可以隨時留言，小編會及時回復大家的。
原文鏈接：http://blog.csdn.net/wojiaohuangyu/article/details/52597663
