歸并排序
-
特點
- 非原地，空間復雜度O(n)
- 穩定
- O(nlogn)
-
歸并排序的思想是如果要排序一個陣列，我們先把陣列從中間分為前后兩部分，然后對前后部分分別排序，再將排好序的兩部分合在一起，這樣整個陣列就都有序了
快速排序
-
特點
- 原地
- 不穩定
- O(nlongn)
-
選擇一個磁區點pivot，把它放到正確的地方，這樣陣列被分為兩部分，然后前后兩部分繼續此程序
桶排序
-
核心思想：將要排序的資料分到幾個有序的桶里，每個桶里的資料再單獨進行排序，最后把每個桶里的資料按順序取出，組成的序列就是有序的了
-
時間復雜度：O(n)
-
如果要排序的資料有 n 個，我們把它們均勻地劃分到 m 個桶內，每個桶里就有 k=n/m 個元素
-
每個桶內部使用快速排序，時間復雜度為 O(k * logk)，m 個桶排序的時間復雜度就是 O(m * k * logk)
-
因為 k=n/m，所以整個桶排序的時間復雜度就是 O(n*log(n/m))
-
當桶的個數 m 接近資料個數 n 時，log(n/m) 就是一個非常小的常量，這個時候桶排序的時間復雜度接近 O(n)
-
-
桶排序比較適合用在外部排序中，資料存盤在外部磁盤中，資料量比較大，記憶體有限，無法將資料全部加載到記憶體中
-
桶排序對資料的要求
-
資料容易被劃分為m個桶，并且桶與桶直接有著天然的順序
-
資料在各個桶之間分布比較均勻，在極端情況下，如果資料全都被劃到一個桶里，那就退化為O(nlogn)的排序演算法了
-
計數排序
-
桶排序的特殊情況，當要排序的資料所處范圍并不大時，我們可以把資料分為max-min+1個桶（比如高考滿分750分，設定751個桶放置考生成績），桶記憶體放資料出現的次數
-
具體做法
-
遍歷原陣列A，資料每出現一次，對應桶的計數+1（C[n]++）
-
得出排序好的資料
-
將桶內資料順序求和（每個桶內不再是資料出現次數，而是小于等于該資料的個數）
-
準備好一個結果陣列R
-
從后到前遍歷原陣列A，取出C[n]，C[n]代表原陣列中小于等于n的資料一共有C[n]個，那么原資料A[n]就應該放到結果陣列R的C[n]處，然后將C[n]--
-
快排、計數Java實作
/**
* 快速排序
*
* @param arr 陣列
* @param p 要排序部分左下標
* @param r 右下標
*/
public static void quickSort(int arr[], int p, int r) {
if (p >= r) return;
//選擇一個磁區點（設為r）
int pivot = arr[r];
//將磁區點放到它正確的位置
//[p,i)為已處理區間，[j,r)為未處理區間，處理完畢后i左邊全小于等于pivot，右邊全大于pivot
int i = p;
for(int j = p; j < r ; j++){
//將小于pivot的值放到已處理區間
if(arr[j] < pivot){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
//最后將pivot放在i處
int temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
//重復選擇-放置程序
quickSort(arr,p,i-1);
quickSort(arr,i+1,r);
}
/**
* 計數排序
* @param arr
* @param max
*/
public static void countingSort(int arr[], int max){
//桶C用于存盤累計值
//統計各資料出現次數
int c[] = new int[max + 1];
for(int i : arr)
c[i]++;
//得出排序好的陣列
//C中資料累計相加
for(int i = 1; i < c.length; i++){
c[i] += c[i - 1];
}
//從后往前遍歷原陣列 將arr[n]放置在R[c[arr[n]]]處
int result[] = new int[arr.length];
for(int i = arr.length - 1; i >= 0; i--){
result[--c[arr[i]]] = arr[i];
}
for(int i = 0; i < arr.length; i++)
arr[i] = result[i];
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27699.html
標籤：其他
下一篇：6.排序總結和優化