算法導(dǎo)論讀書筆記（8）

目錄

• 計數(shù)排序
  • 計數(shù)排序的簡單Java實現(xiàn)
• 基數(shù)排序
  • 基數(shù)排序的簡單Java實現(xiàn)
• 桶排序

計數(shù)排序

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

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

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

計數(shù)排序的一個重要性質(zhì)是它是穩(wěn)定的：具有相同值得元素在輸出數(shù)組中的相對次序與它們在輸入數(shù)組中的次序相同。而且，計數(shù)排序經(jīng)常作為基數(shù)排序算法的一個子程序。

計數(shù)排序的簡單Java實現(xiàn)

/** * 計數(shù)排序 */ 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; }

基數(shù)排序

基數(shù)排序 要求待排序的元素?fù)碛邢嗤奈粩?shù)。從元素的低位到高位依次排序。

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

基數(shù)排序的簡單Java實現(xiàn)

public static void radixSort(int[] array) {int len = String.valueOf(array[0]).toString().length();for (int i = 0; i < len; i++)radixQuickSort(array, i); } /** * 計數(shù)排序的變形 */ 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]; } /** * 獲得數(shù)字第n位的值 */ public static int getDigit(int value, int power) {return (int) (value / Math.pow(10, power)) % 10; }

桶排序

當(dāng) 桶排序 （bucket sort）的輸入符合均勻分布時，它可以以線性時間運行。桶排序假設(shè)輸入由一個隨機(jī)過程產(chǎn)生，該過程將元素均勻地分布在區(qū)間[ 0， 1 )上。

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

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

轉(zhuǎn)載于:https://www.cnblogs.com/sungoshawk/p/3646265.html

總結(jié)

以上是生活随笔為你收集整理的算法导论读书笔记（8）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。