七大基于比較的排序
直接插入排序
思想：以雙指針來進行遍歷數組和尋找較小元素的操作，每次找到較小元素的時候就將其插入到前面的適當位置，當遍歷完整個數組，并完成插入操作后，排序完成。
時間復雜度：最好情況：O(N)
最壞情況：O（N^2）
空間復雜度：O(1)
結論：當一組數據趨近于有序，適用于插入排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public static void insertSort(int[] array) { //該循環實現對整個數組的遍歷操作 for (int i = 1; i < array.length; ++i) { //記錄將被插入的元素(i下標元素) int tmp = array[i]; //j指向i的前一個元素 int j = i - 1; for (; j >= 0; j--) { //如果j指向的元素比被插入元素大，就往后移一位 if (array[j] > tmp) { array[j + 1] = array[j]; } else {//否則就找到了插入位置，跳出該循環 break; } } //j+1即為插入位置 array[j + 1] = tmp; }} |
希爾排序
思想：將數組不斷分組再進行排序，當分組的長度為1時，進行的就是直接插入排序。
時間復雜度：O(N1.3 ~ N1.5)
空間復雜度：O(1)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public static void shellSort(int[] array) { int gap = array.length; while (gap > 1) { //gap為1時，就是直接插入排序 gap = gap / 3 + 1; shell(array, gap); }}public static void shell(int[] array, int gap) { for (int i = gap; i < array.length; ++i) { int tmp = array[i]; int j = i - gap; for (; j >= 0; j -= gap) { if (array[j] > tmp) { array[j + gap] = array[j]; } else { break; } } array[j + gap] = tmp; }} |
選擇排序
思想：選擇排序是一種簡單直觀的排序算法。它的工作原理是：第一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰?，繼續放在起始位置直到未排序元素個數為0。
時間復雜度：O（N2）
空間復雜度：O（N2）
|
1
2
3
4
5
6
7
8
9
10
11
|
public static void selectSort(int[] array){ for(int i = 0;i<array.length;++i){ for(int j = i+1;j<array.length;++j){ if(array[j]<array[i]){ int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } }} |
堆排序
思想：從小到大排序，就先建一個大堆，堆頭元素就是整個數組中最大的數，==因此我們每次將堆頭元素與堆尾元素交換，交換一次，堆尾下標往前移動一位，形成一個新堆，再向下調整構建成大堆；==以此循環，直到堆尾下標與堆頭下標重合，堆排序完成。
時間復雜度：O(N*log N)
空間復雜度：O(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
|
public static void heapSort(int[] array) { createHeap(array);//建大堆 int end = array.length - 1; //將堆頭元素與堆尾元素互換位置，就將最大元素放到了最后一位，舍去最后一位小標重新將堆向下調整；直到堆為空，數組中元素就排序完成。 while (end >= 0) { int tmp = array[0]; array[0] = array[end]; array[end] = tmp; end--; siftDown(array, 0, end); } } //從小到大排序，建一個大堆 public static void createHeap(int[] array) { for (int parent = (array.length - 1) / 2; parent >= 0; parent--) { siftDown(array, parent, array.length-1); } } //向下調整大堆 public static void siftDown(int[] array, int root, int end) { int parent = root; int child = 2 * parent + 1; while (child <= end) { if (child + 1 <= end && array[child] < array[child + 1]) child++; if (array[parent] < array[child]) { int tmp = array[parent]; array[parent] = array[child]; array[child] = tmp; parent = child; child = parent * 2 + 1; } else { break; } } } |
冒泡排序
思想：相鄰的元素兩兩比較，較大的數下沉，較小的數冒起來，這樣一趟比較下來，最大(小)值就會排列在一端。該冒泡排序為優化過的排序，定義一個boolean類型的變量來判斷數組是否已經有序，若有序可以直接返回，以此來減少時間復雜度。
時間復雜度：最壞：O（N2）
? 最優：O（N）
空間復雜度:O(1)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public static void bubbleSort(int[] array) { //最外層循環為比較的趟數 for (int i = 0; i < array.length - 1; ++i) { //flag是為了判斷接下來的循環是否有必要進行 boolean flag = false; //內層循環為每趟比較的次數 for (int j = 0; j < array.length - 1 - i; ++j) { if (array[j] > array[j + 1]) { int tmp = array[j]; array[j] = array[j + 1]; array[j + 1] = tmp; flag = true; } } //flag==false說明這趟循環沒有交換數據，也就是說數組已經有序，可以直接返回。 if (flag == false) return; } } |
快速排序
思想：先找到一個中間元素，將小于這個元素的數放到它的左邊，大于這個元素的數放到它的右邊，再將左右兩部分進行上述操作，重復以往，就完成快排操作。
時間復雜度：最好：O(Nlog 2N)
最壞：O(N2)
時間復雜度平均：O(Nlog2N)
空間復雜度：O(Nlog2N)
|
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
|
public static void quickSort(int[] array, int l, int r) { if (l >= r) return; //因為用do while（）循環，所以先將左右指針向兩邊移動一位 int i = l - 1, j = r + 1; //取數組中間元素的值作為這個分割點 int mid = array[(l + r)>>1]; while (i < j) { //左邊的數小于中間值，指針向右移動 do ++i; while (array[i] < mid); //右邊的數大于中間值，指針向左移動 do --j; while (array[j] > mid); //兩個指針停下后交換元素 if (i < j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } //遞歸左半部分 quickSort(array, l, j); //遞歸右半部分 quickSort(array, j + 1, r); } |
歸并排序
思想：先分組再排序，和快排操作順序相反。將數組分為左右兩部分，再對左右兩部分 分別再分組，以此類推，直到每一部分只有一個元素，然后按順序合并為一個個新的有序數組，小數組歸并為大數組，以此類推就得到排序后的數組。
時間復雜度：O(N*logN)
空間復雜度：O(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
|
public static void mergeSort(int[] array){ mergerSortInternal(array,0,array.length-1); } public static void mergerSortInternal (int[] array,int l,int r){ if(l>=r) return; int mid = (l+r)>>1; //遞歸左半部分 mergerSortInternal(array,l,mid); //遞歸右半部分 mergerSortInternal(array,mid+1,r); //歸并 merge(array,l,mid,r); } public static void merge(int[] array,int l,int mid, int r){ int s1 = l,e1 = mid; int s2 = mid+1, e2 = r; int [] tmp = new int[r-l+1]; int k = 0; //比較兩個有序小數組元素，將小的元素放到新數組前面，大的元素放到新數組后面 while(s1<=e1 && s2<=e2){ if(array[s1]<array[s2]){ tmp[k++] = array[s1++]; }else{ tmp[k++] = array[s2++]; } } //處理剩余元素 while(s1<=e1) tmp[k++] = array[s1++]; while(s2<=e2) tmp[k++] = array[s2++]; //將排完序的新數組元素放回原數組中 for(int i = 0;i<tmp.length;++i){ array[i+l] = tmp[i]; } } |
到此這篇關于Java重點之基于比較的七大排序的文章就介紹到這了,更多相關Java 排序內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/m0_52373742/article/details/120406634
