折半插入排序
折半插入排序是对直接插入排序的简单改进。此处介绍的折半插入，其实就是通过不断地折半来快速确定第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
