排序算法總結

1 排序算法

1.1 快速排序

1.1.1 算法思想

先取一個隨機數，然后和數組的最后一個數交換
進行partition過程，也就是比數組最后一個數小的放在數組左邊，大的放在右邊，相等的在數組中間，最后把數組的最后一個數也要放到中間位置，然后返回相等的那一批數的最左索引和最右索引。
遞歸前兩個過程

1.1.2 時間復雜度

O (N * logN)

1.1.3 代碼實現

public class QuickSort {private static void quickSort(int[] arr) {if (arr == null || arr.length < 2) {return;}process(arr, 0, arr.length - 1);}private static void process(int[] arr, int left, int right) {if (left >= right) {return;}swap(arr, left + (int)(Math.random() * (right - left + 1)), right);int[] partition = partition(arr, left, right);process(arr, left, partition[0] - 1);process(arr, partition[1] + 1, right);}private static int[] partition(int[] arr, int left, int right) {int index = left;int small = left - 1;int big = right;while (index < big) {if (arr[index] == arr[right]) {index++;} else if (arr[index] < arr[right]) {swap(arr, index++, ++small);}else {swap(arr, index, --big);}}swap(arr, right, big);return new int[] {++small, big};}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arr = {1,2,8,9,5};quickSort(arr);for (int i : arr) {System.out.print(i + " ");}}
}

1.2 堆排序

1.2.1 算法思想

給了一個數組，把數組看成完全二叉樹結構，現在開始變成堆
從完全二叉樹的最后一個值開始進行heapify過程，也就是把每一個值都要和子節點比較大小，把這個節點為頂的樹變成堆結構
變成大根堆堆結構之后，將堆頂元素和數組最后一個元素互換，堆的長度減一的同時要進行heapify操作，把剩下元素的要恢復堆結構
重復第三步操作，每次都取一個最大值出來放到原堆的最后，數組有序

1.2.2 時間復雜度

O (N * logN)

1.2.3 代碼實現

public class HeapSort {public static void heapSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int heapSize = arr.length;for (int i = arr.length - 1; i >= 0; i--) {heapify(arr, i, heapSize);}swap(arr, 0, --heapSize);while (heapSize > 0) {heapify(arr, 0, heapSize);swap(arr, 0, --heapSize);}}private static void heapify(int[] arr, int index, int heapSize) {int left = index * 2 + 1;while (left < heapSize) {int largest = left + 1 < heapSize ? (arr[left] < arr[left + 1] ? left + 1 : left) : left;largest = arr[index] < arr[largest] ? largest : index;if (largest == index) {return;}swap(arr, largest, index);index = largest;left = index * 2 + 1;}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arr = {1,9,7,3,6,4,8,2,5};heapSort(arr);for (int i : arr) {System.out.print(i + " ");}}
}

1.3 桶排序

不基于比較的排序算法，，分為兩類，但是都有約束條件

計數排序：要排序的數都要是0或正整數
基數排序：必須是十進制的數，而且是0或正整數

給的數越多，代價越大。一旦要升級的話，要付出的代價更加顯而易見。

要排序的最大的數越大，計數排序需要的空間就越多，要排序比如{9，1，96656412}，那么此時就需要輔助數組的長度就要是96656413了，很明顯性價比不高，就需要用基數排序，基數排序只用兩個輔助數組，而且一個計數器數組長度長度固定為10，一個輔助數組長度和要排序的數組長度相同，浪費的空間小。但是如果要排序的數中最大數越小，那么此時就可以用計數排序。

1.3.1 計數排序

算法思想

給定數組，范圍[0，intMax]
定義一個輔助數組，輔助數組的長度就是給定數組的長度
遍歷數組，給定數組的值與輔助數組的索引對應，
每當有一個給定數組的值等于輔助數組的索引，那么這個索引上的值加一
遍歷完成之后，再遍歷輔助數組，
每當輔助數組的值不為0，就把輔助數組的索引覆蓋在給定數組中
每覆蓋一次，輔助數組的值減一，直到減為0才能遍歷下一次

時間復雜度

O (N)

代碼實現

public class CountSort {public static void countSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int max = arr[0];for (int i = 1; i < arr.length; i++) {max = Math.max(max, arr[i]);}int[] bucket = new int[max + 1];for (int a : arr) {bucket[a]++;}int index = 0;for (int i = 0; i < bucket.length; i++) {while (bucket[i]-- > 0) {arr[index++] = i;}}}// 寫比較器驗證public static void comparator(int[] arr) {if (arr == null || arr.length < 2) {return;}Arrays.sort(arr);}public static int[] generateRandomArr(int arrLen) {int[] ans = new int[arrLen];for (int i = 0; i < arrLen; i++) {int num = (int) (Math.random() * 1000 + 1);ans[i] = num;}return ans;}public static void main(String[] args) {int arrLength = 1000;int testTimes = 1000000;for (int i = 0; i < testTimes; i++) {int arrLen = (int) (Math.random() * arrLength + 1);int[] arr1 = generateRandomArr(arrLen);int[] arr2 = new int[arr1.length];for (int j = 0; j < arr1.length; j++) {arr2[j] = arr1[j];}countSort(arr1);comparator(arr2);for (int j = 0; j < arr1.length; j++) {if (arr1[j] != arr2[j]) {System.out.println("Oops!");}}}System.out.println("Finish!");}
}

1.3.2 基數排序

算法思想

算法步驟：

給定數組的最大數有幾位就遍歷幾遍（最外層的遍歷），先從個位數字開始遍歷
- 目的是從個位數字開始，先把數組中的每個數的個位數字排序，之后再排十位，以此類推。
- 第一次遍歷
  - 遍歷每個數組，遍歷的過程中，只看現在遍歷的數的個位數字，也就是不管數組有多大，每次看的數字只有[0,9]
  - 定義一個計數器數組，每個數字出現一個，計數器數組的與這個數字相等的索引上的值加一
- 第二次遍歷
  - 遍歷計數器數組，數組中的每個數等于前面自己的值和前一個數的值相加
  - 目的是找出比這個數小的數字有多少個
- 第三次遍歷
  - 定義一個輔助數組，長度和給定數組的長度相同
  - 從給定數組的末尾開始往前遍歷
  - 看計數器數字中，和給定數組的末尾數字的個為數字相同的數字有幾個，也就是找比這個數字小的或者等于有多少個
  - 這個數字減一就是輔助數組的索引，索引上放的數字就是給定數組的現在遍歷到的數。
  - 這個理解就相當于隊列，小的肯定在前面，相同的先進的先出（第一次遍歷中，先遍歷的在前面，后遍歷的在后面，那么最后一個遍歷的肯定在最后面）
- 第四次遍歷
  - 交換輔助數組和給定數組的每一個值
  - 接下來就要結束整個大的個位數的遍歷，開始遍歷十位上的數

時間復雜度

O(N)

代碼實現

public class RadixSort {public static void radixSort(int[] arr) {if (arr == null || arr.length < 2) {return;}radixSort(arr, 0, arr.length - 1, maxBits(arr));}// 求數組中最大的數有幾位：1000  --->  4位private static int maxBits(int[] arr) {int max = arr[0];for (int i = 1; i < arr.length; i++) {max = Math.max(max, arr[i]);}int ans = 0;while (max != 0) {max /= 10;ans++;}return ans;}// 基數排序的實現public static void radixSort(int[] arr, int left, int right, int digit) {final int radix = 10;int[] help = new int[right - left + 1];for (int d = 1; d <= digit; d++) {int[] count = new int[radix];int i = 0;int j = 0;for (i = left; i <= right; i++) {j= getDigit(arr[i], d);count[j]++;}for (i = 1; i < radix; i++) {count[i] += count[i - 1];}for (i = right; i >= left; i--) {j = getDigit(arr[i], d);help[count[j] - 1] = arr[i];count[j]--;}for (i = left, j = 0; i <= right; i++, j++) {arr[i] = help[j];}}}// num這個數的digit位的數字：(123，1) ---> 3private static int getDigit(int num, int digit) {return ((num / (int) Math.pow(10, digit - 1)) % 10);}// 對數器測試public static void comparator(int[] arr) {if (arr == null || arr.length < 2) {return;}Arrays.sort(arr);}public static int generateRandomNum(int num) {return (int) (Math.random() * num + 1);}public static int[] generateRandomArr(int arrLen, int num) {int length = (int) (Math.random() * arrLen + 1);int[] ans = new int[length];for (int i = 0; i < length; i++) {ans[i] = generateRandomNum(num);}return ans;}public static void main(String[] args) {int num = 1000;int arrLen = 100;int testTimes = 1000000;for (int i = 0; i < testTimes; i++) {int[] arr1 = generateRandomArr(arrLen, num);int[] arr2 = new int[arr1.length];for (int j = 0; j < arr1.length; j++) {arr2[j] = arr1[j];}radixSort(arr1);comparator(arr2);for (int j = 0; j < arr1.length; j++) {if (arr2[j] != arr1[j]) {System.out.println("Oops!");}}}System.out.println("Finish!");}
}

排序算法總結

1 總結

不基于比較的排序（桶排序），對樣本數據有嚴格的要求，不易改寫
基于比較的排序，只要規定好兩個樣本怎么比大小就可以直接復用
基于比較的排序，時間復雜度的極限是O(N*logN)
時間復雜度O(N*logN)，額外空間復雜度低于O(N)且穩定的基于比較的排序是不存在的
為了絕對的速度選擇快排，為了省空間選堆排，為了穩定性選歸并

2 常見的坑

歸并排序的額外空間復雜度可以變成O(1)，“歸并排序內部緩存法”，但是將變得不穩定。（還不如用堆排）
“原地歸并排序”不好，會讓時間復雜度變成O(N*2)。（不如用插入排序）
快速排序穩定性改進，論文：“01 stable sort”，但是會對樣本數據要求更多。（不如用桶排序）
- 題目：在整型數組中，請把奇數放在數組左邊，偶數放在數組右邊，要求所有基數之間原始的相對次序不變，所有偶數之間原始相對次序不變，要求時間復雜度O(N),額外空間復雜度O(1)。