算法導論讀書筆記（8）

算法導論讀書筆記（8）

目錄

• 計數排序
  • 計數排序的簡單Java實現
• 基數排序
  • 基數排序的簡單Java實現
• 桶排序

計數排序

計數排序 假設 n 個輸入元素中的每一個都是介于0到 k 之間的整數，此處 k 為某個整數。當 k = O ( n )時，計數排序的運行時間為 Θ ( n )。

計數排序的基本思想就是對每一個輸入元素 x ，確定出小于 x 的元素個數。有了這一信息，就可以把 x 直接放到它在最終輸出數組上的位置上。

COUNTING-SORT(A, B, k)
1  let C[0 .. k] be a new array
2  for i = 0 to k
3      C[i] = 0
4  for j = 1 to A.length
5      C[A[j]] = C[A[j]] + 1
6  // C[i] now contains the number of elements equal to i.
7  for i = 1 to k
8      C[i] = C[i] + C[i - 1]
9  // C[i] now contains the number of elements less than or equal to i.
10 for j = A.length downto 1
11     B[C[A[j]]] = A[j]
12     C[A[j]] = C[A[j]] - 1

計數排序的一個重要性質是它是穩定的：具有相同值得元素在輸出數組中的相對次序與它們在輸入數組中的次序相同。而且，計數排序經常作為基數排序算法的一個子程序。

計數排序的簡單Java實現

/**
 * 計數排序
 */
public static int[] countingSort(int[] array, int k) {int[] result = new int[array.length];int[] temp = new int[k];for (int i = 0; i < k; i++)temp[i] = 0;for (int j = 0; j < array.length; j++)temp[array[j]]++;for (int i = 1; i < k; i++)temp[i] = temp[i] + temp[i - 1];for (int j = array.length - 1; j >= 0; j--) {result[temp[array[j]] - 1] = array[j];temp[array[j]]--;}return result;
}

基數排序

基數排序 要求待排序的元素擁有相同的位數。從元素的低位到高位依次排序。

RADIX-SORT(A, d)
1 for i = 1 to d
2     use a stable sort to sort array A on digit i

基數排序的簡單Java實現

public static void radixSort(int[] array) {int len = String.valueOf(array[0]).toString().length();for (int i = 0; i < len; i++)radixQuickSort(array, i);
}

/**
 * 計數排序的變形
 */
public static void radixQuickSort(int[] array, int power) {int[] result = new int[array.length];int[] temp = new int[10];for (int i = 0; i < 10; i++)temp[i] = 0;for (int j = 0; j < array.length; j++)temp[getDigit(array[j], power)]++;for (int i = 1; i < 10; i++)temp[i] = temp[i] + temp[i - 1];for (int j = array.length - 1; j >= 0; j--) {result[temp[getDigit(array[j], power)] - 1] = array[j];temp[getDigit(array[j], power)]--;}for (int i = 0; i < result.length; i++)array[i] = result[i];
}

/**
 * 獲得數字第n位的值
 */
public static int getDigit(int value, int power) {return (int) (value / Math.pow(10, power)) % 10;
}

桶排序

當 桶排序 （bucket sort）的輸入符合均勻分布時，它可以以線性時間運行。桶排序假設輸入由一個隨機過程產生，該過程將元素均勻地分布在區間[ 0， 1 )上。

桶排序的思想就是把區間[ 0， 1 )劃分成 n 個相同大小的子區間，或稱 桶 。然后，將 n 個輸入數分布到各個桶中去。因為輸入數均勻分布在[ 0， 1 )上，所以，一般不會有很多數落在一個桶中的情況。為得到結果，先對各個桶中的元素進行排序，然后按次序把桶中的元素列出來即可。

BUCKET-SORT(A)
1  let B[0 .. n - 1] be a new array
2  n = A.length
3  for i = 0 to n - 1
4      make B[i] an empty list
5  for i = 1 to n
6      insert A[i] into list B[FLOOR(nA[i])]
7  for i = 0 to n - 1
8      sort list B[i] with insertion sort
9  concatenate the lists B[0], B[1], ..., B[n - 1] together in order