計數排序
計數排序不是一個比較排序算法，該算法于1954年由 Harold H. Seward提出，通過計數将時間複雜度降到了O(N)。
計數排序就是在數組中找到一個最大值，建構最大值+ 1長度的bucket數組，例如 1 2 3 4 9 ，最大值為9數組長度為10，為0留一個位置。然後周遊數組，根據數值放到bucket數組對應的index中，index個數+ 1，然後把bucket資訊倒出來。
private static void countSort(int[] arr) {
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int[] bucket = new int[max + 1];
//記錄每個元素出現的頻率
for (int i = 0; i < arr.length; i++) {
//為arr[i]位置上的數結果+ 1
bucket[arr[i]]++;
}
int temp = 0;
//按照bucket的結果，按照頻率把資料拿出來即可
for (int i = 0; i < bucket.length; i++) {
for (int j = 0; j < bucket[i]; j++) {
arr[temp++] = i;
}
}
}
2.基數排序
基數排序
arr[17,23,0,96,17,23，13，1，100]
先分堆，統計每個數頻次，基于資料狀況的排序，不基于資料比較
要求資料狀況在很小的範圍，否則複雜度很高，樣本必須為十進制的數
a.首先找到最大值,确定最大值為100，其中100是三位十進制
b.不足補0，13變013，依次類推
b.準備十個桶，挨個周遊，根據個位數去選擇去哪個桶
c.将桶中資料依次倒出
d.根據十位數字進桶、将桶中資料倒出
e.根據百位數組進行桶，将桶中資料導出
f.數字有序
- 首先找到最大值100，擷取最大值的位數，100的位數為3
先按照各位數周遊
4. 從後向前周遊，找到我對應的對應位上數向前挪一個位置，就是我要進去了的位置。
5. for循環存放資訊，将存放資訊放進數組中。
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
public static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
//先找到最大值
max = Math.max(max, arr[i]);
}
int res = 0;
//擷取最大值的位數
while (max != 0) {
res++;
max /= 10;
}
return res;
}
// arr[begin..end]排序
public static void radixSort(int[] arr, int L, int R, int digit) {
final int radix = 10;
int i = 0, j = 0;
// 有多少個數準備多少個輔助空間
int[] bucket = new int[R - L + 1];
for (int d = 1; d <= digit; d++) { // 有多少位就進出幾次
// 10個空間
int[] count = new int[radix]; // count[0..9]
//
for (i = L; i <= R; i++) {
//擷取第d位上的數，記錄下來
j = getDigit(arr[i], d);
count[j]++;
}
//統計小于等于個位數上數值個數有幾個
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
//然後将比這個範圍小的數減去一，
//這樣的話就可以記錄每一個個位數值上資訊,就按照個位數從小到大的排好了
for (i = R; i >= L; i--) {
//擷取這個數的位資訊，
j = getDigit(arr[i], d);
//由于基數排序需要十個隊列，為了節省空間，
//例如目前digit為1， i = 22， 那麼j = 2，
// count[2] 是找到個位數比2的值要小，那麼count[2]個數減去1,就是我要去的位置了
bucket[count[j] - 1] = arr[i];
count[j]--;
}
for (i = L, j = 0; i <= R; i++, j++) {
arr[i] = bucket[j];
}
}
}
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
- 桶排序思想下的排序都是不基于比較的排序，
- 時間複雜度O(N),額外空間複雜度位O(M)
- 應用範圍優先，需要樣本的資料狀況滿足桶的劃分。
排序算法的穩定性及其彙總
同樣值得個體之間，如果不因為排序而改變相對次序，就是這個排序是有穩定性得，否則就沒有。
不具備穩定性的排序：選擇排序、快速排序、堆排序
備穩定性的排序：歸并排序、插入排序、冒泡排序、桶排序
目前沒有找到時間複雜度O(N *logN)，額外空間複雜度O(1)，又穩定的排序
排序算法的穩定性及其彙總
-
各個排序差別
選擇排序，先選出最小值與最小值交換.
插入排序，目前值與前面的值比大小，如果比前面值小，交換，一直到前面沒有比我小的或者是到頭了
冒泡排序, 向後找，相同時不交換位置，不同時且大于後面的值交換
歸并排序，先拆分，如果左面小于等于右面，拷貝左面
堆排序， 自己維持一個二叉樹，将整體變成大根堆
快速排序， 随機選一個數做partition，然後小于等于區向後挪，大于區向前找，之後再與大于等于區第一個數交換位置
希爾排序， 改造的插入排序
| 排序名稱 | 時間複雜度 | 額外空間複雜度 | 是否穩定 |
|---|---|---|---|
| 選擇排序 | O(N ^2) | O(1) | × |
| – | – | – | – |
| 插入排序 | O(N ^2) | O(1) | √ |
| – | – | – | – |
| 冒泡排序 | O(N ^2) | O(1) | √ |
| – | – | – | – |
| 歸并排序 | O(N *logN) | O(N) | √ |
| – | – | – | – |
| 堆排序 | O(N *logN) | O(1) | × |
| – | – | – | – |
| 桶排序 | O(N *logN) | O(M) | √ |
| – | – | – | – |
| 快速排序 | O(N ^2) | O(1) | × |
-
.排序的選擇？
A.不在乎穩定性，在短時間内快速排序，隻在乎名額與常數時間，選擇快排，常數時間最低
B.額外空間少，使用堆排序
C.追求穩定用歸并
-
歸并排序可以将空間複雜度變為O(1)麼，可以的，使用内部緩存法，但用完就不穩定了。
原地歸并排序，空間複雜度是O(1)也穩定，但是時間複雜度變為O(N^2)
快速排序可以做穩定麼?可以，但額外空間複雜度變0(N)， o1 stable sort
有一道題目，奇數在左邊，偶數在右邊，還要求原始相對次數不變，時間複雜度是O(N),額外空間複雜度是O(1)
這個是不可能實作的，因為這是0，1标準排序,那麼必須要交換位置，肯定不穩定。
-
經典快排，如果L-R不夠60.直接使用插入排序，O(N^2)在常數很優，N不大時常數很好，O(N*logN)在排程上很優