本文實例講述了java幾種排序算法的實現及簡單分析。分享給大家供大家參考。具體如下：
|
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
|
package test;public class first {/*普通的插入排序*/public void insertSort(int[] list) {int i, j;list[0] = -999;//相當于設置一個監視哨兵，不用判斷是否越界，//但要求數組從第二個數開始即i=1開始存儲for (i = 1; i < list.length; i++) {j = i;while (list[j] < list[j - 1]) {int temp = list[j];list[j] = list[j - 1];list[j - 1] = temp;j = j - 1;}}}/*折半插入，在直接插入的基礎上，添加二叉查找*/public void binInsertSort(int[] r, int low, int high) {for (int i = low + 1; i <= high; i++){int temp = r[i]; // 保存待插入元素int hi = i - 1;int lo = low; // 設置初始區間while (lo <= hi){ // 折半確定插入位置int mid = (lo + hi) / 2;if (temp < r[mid])hi = mid - 1;elselo = mid + 1;}for (int j = i - 1; j > hi; j--)r[j + 1] = r[j]; // 移動元素r[hi + 1] = temp; // 插入元素}}/*希爾排序或shell */public void shellSort(int[] r, int low, int high, int[] delta){for (int k=0;k<delta.length;k++)shellInsert(r, low, high, delta[k]);}private void shellInsert(int[] r, int low, int high, int deltaK){for (int i=low+deltaK; i<=high; i++)if (r[i]<r[i-deltaK]){int temp = r[i];int j = i-deltaK;for(; j>=low&&temp<r[j]; j=j-deltaK)r[j+deltaK] = r[j];r[j+deltaK] = temp;}}/*簡單的選擇交換*/public void selectSort(int[] r, int low, int high) {for (int k = low; k < high - 1; k++) { // 作n-1 趟選取int min = k;for (int i = min + 1; i <= high; i++)// 選擇關鍵字最小的元素if (r[i] < r[min])min = i;if (k != min) {int temp = r[k]; // 關鍵字最小的元素與元素r[k]交換r[k] = r[min];r[min] = temp;}// end of if}}/*堆排序-大頂堆*/public void heapSort(int[] r){int n = r.length - 1;for (int i=n/2; i>=1; i--)heapAdjust(r,i,n);for (int i=n; i>1; i--){int temp = r[1];r[1] = r[i];r[i] = temp;heapAdjust(r,1,i-1);}}//調整堆private void heapAdjust(int[] r, int low, int high){int temp = r[low];for (int j = 2 * low; j <= high; j = j * 2) {if (j < high && r[j] < r[j + 1])j++;if (temp > r[j])break;r[low] = r[j];low = j;}r[low] = temp;}public static void main(String[] args) {first fs = new first();int[] a = { 100, 9, 8, 9, 9, 7, 7, 0, 0, 99, 55, 7, 6, 5, 4, 3, 2, 1 };int[] k={5,3,1};// fs.insertSort(a);//fs.binInsertSort(a, 0, a.length - 1);//fs.shellSort(a, 0,a.length-1,k);//fs.selectSort(a, 0, a.length-1);fs.heapSort(a);for (int i = 0; i < a.length; i++) {System.out.println(a[i]);}}} |
插入排序、交換排序、選擇排序、歸并排序等排序方法，都有一個共同的特點，那就是它們都是通過比較元素的大小來確定元素之間的相對位置的，即上述排序方法都是基于比較的排序方法。下面，我們就基于比較的排序方法進行一個對比和總結。
我們主要從算法的平均時間復雜度、最壞時間復雜度、空間復雜度以及排序的穩定性等方面，對各中排序方法加以比較。
排序方法 平均時間復雜度最壞時間復雜度空間復雜度 穩定性
直接插入排序 Ο(n2) Ο(n2) Ο(1) 穩定
起泡排序 Ο(n2) Ο(n2) Ο(1) 穩定
快速排序 Ο(n log n) Ο(n2) Ο(log n) 不穩定
簡單選擇排序 Ο(n2) Ο(n2) Ο(1) 不穩定
堆排序 Ο(n log n) Ο(n log n) Ο(1) 不穩定
歸并排序 Ο(n log n) Ο(n log n) Ο(n) 穩定
從時間性能上看，快速排序是所有排序算法中實際性能最好的，然而快速排序在最壞情況下的時間性能不如堆排序和歸并排序。這一點可以通過對快速排序進行改進來避免，一種通過隨機選擇樞軸元素的隨機快速排序，可以使得出現最壞情況出現的幾率非常小，在實際的運用中可以認為不存在。在堆排序和歸并排序的比較中，當n 較大時，歸并排序所需時間較少，然而它需要較多的輔助存儲空間。
從方法穩定性上來看，大多數時間復雜度為Ο(n2)的排序均是穩定的排序方法，除簡單選擇排序之外。而多數時間性能較好的排序方法，例如快速排序、堆排序、希爾排序都是不穩定的。一般來說，排序過程中的比較是在相鄰的兩個元素之間進行的排序方法是穩定的。
并且，排序方法的穩定性是由方法本身決定的，對于不穩定的排序方法而言，不管其描述形式如何，總能找到一種不穩定的實例。
綜上所述，上面討論的所有排序方法中，沒有哪一個是絕對最優的，在實際的使用過程中，應當根據不同情況選擇適當的排序方法。
希望本文所述對大家的java程序設計有所幫助。
