歡迎光臨
每天分享高質量文章

漫畫:什麼是計數排序?

(點選上方公眾號,可快速關註)


來源:程式員小灰




—————  第二天  —————












————————————



















假定20個隨機整數的值如下:


9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9 ,7,9


如何給這些無序的隨機整數排序呢?


非常簡單,讓我們遍歷這個無序的隨機數列,每一個整數按照其值對號入座,對應陣列下標的元素進行加1操作。


比如第一個整數是9,那麼陣列下標為9的元素加1:



第二個整數是3,那麼陣列下標為3的元素加1:



繼續遍曆數列並修改陣列……


最終,數列遍歷完畢時,陣列的狀態如下:



陣列每一個下標位置的值,代表了數列中對應整數出現的次數。


有了這個“統計結果”,排序就很簡單了。直接遍歷陣列,輸出陣列元素的下標值,元素的值是幾,就輸出幾次:


0,1,1,2,3,3,3,4,4,5,5,6,7,7,8,9,9,9,9,10


顯然,這個輸出的數列已經是有序的了。








  1. public static int[] countSort(int[] array) {

  2.    //1.得到數列的最大值

  3.    int max = array[0];

  4.    for(int i=1; i

  5.        if(array[i] > max){

  6.            max = array[i];

  7.        }

  8.    }

  9.    //2.根據數列最大值確定統計陣列的長度

  10.    int[] countArray = new int[max+1];

  11.    //3.遍曆數列,填充統計陣列

  12.    for(int i=0; i

  13.        countArray[array[i]]++;

  14.    }

  15.    //4.遍歷統計陣列,輸出結果

  16.    int index = 0;

  17.    int[] sortedArray = new int[array.length];

  18.    for(int i=0; i

  19.        for(int j=0; j

  20.            sortedArray[index++] = i;

  21.        }

  22.    }

  23.    return sortedArray;

  24. }


  25. public static void main(String[] args) {

  26.    int[] array = new int[] {4,4,6,5,3,2,8,1,7,5,6,0,10};

  27.    int[] sortedArray = countSort(array);

  28.    System.out.println(Arrays.toString(sortedArray));

  29. }


這段程式碼在一開頭補充了一個步驟,就是求得數列的最大整數值max。後面建立的統計陣列countArray,長度就是max+1,以此保證陣列的最後一個下標是max。








95,94,91,98,99,90,99,93,91,92





怎麼解決這個問題呢?


很簡單,我們不再以(輸入數列的最大值+1)作為統計陣列的長度,而是以(數列最大值和最小值的差+1)作為統計陣列的長度。


同時,數列的最小值作為一個偏移量,用於統計陣列的對號入座。


以剛才的數列為例,統計陣列的長度為  99-90+1 = 10 ,偏移量等於數列的最小值 90 。


對於第一個整數95,對應的統計陣列下標是 95-90 = 5,如圖所示:









什麼意思呢?讓我們看看下麵的例子:



給定一個學生的成績表,要求按成績從低到高排序,如果成績相同,則遵循原表固有順序。


那麼,當我們填充統計陣列以後,我們只知道有兩個成績併列95分的小夥伴,卻不知道哪一個是小紅,哪一個是小綠:








下麵的講解會有一些燒腦,請大家扶穩坐好。我們仍然以剛才的學生成績表為例,把之前的統計陣列變形成下麵的樣子:




這是如何變形的呢?統計陣列從第二個元素開始,每一個元素都加上前面所有元素之和。


為什麼要相加呢?初次看到的小夥伴可能會覺得莫名其妙。


這樣相加的目的,是讓統計陣列儲存的元素值,等於相應整數的最終排序位置。比如下標是9的元素值為5,代表原始數列的整數9,最終的排序是在第5位。


接下來,我們建立輸出陣列sortedArray,長度和輸入數列一致。然後從後向前遍歷輸入數列:


第一步,我們遍歷成績表最後一行的小綠:


小綠是95分,我們找到countArray下標是5的元素,值是4,代表小綠的成績排名位置在第4位。


同時,我們給countArray下標是5的元素值減1,從4變成3,,代表著下次再遇到95分的成績時,最終排名是第3。




第二步,我們遍歷成績表倒數第二行的小白:


小白是94分,我們找到countArray下標是4的元素,值是2,代表小白的成績排名位置在第2位。


同時,我們給countArray下標是4的元素值減1,從2變成1,,代表著下次再遇到94分的成績時(實際上已經遇不到了),最終排名是第1。




第三步,我們遍歷成績表倒數第三行的小紅:


小紅是95分,我們找到countArray下標是5的元素,值是3(最初是4,減1變成了3),代表小紅的成績排名位置在第3位。


同時,我們給countArray下標是5的元素值減1,從3變成2,,代表著下次再遇到95分的成績時(實際上已經遇不到了),最終排名是第2。




這樣一來,同樣是95分的小紅和小綠就能夠清楚地排出順序了,也正因此,最佳化版本的計數排序屬於穩定排序


後面的遍歷過程以此類推,這裡就不再詳細描述了。





  1. public static int[] countSort(int[] array) {

  2.    //1.得到數列的最大值和最小值,並算出差值d

  3.    int max = array[0];

  4.    int min = array[0];

  5.    for(int i=1; i

  6.        if(array[i] > max) {

  7.            max = array[i];

  8.        }

  9.        if(array[i] < min) {

  10.            min = array[i];

  11.        }

  12.    }

  13.    int d = max - min;

  14.    //2.建立統計陣列並統計對應元素個數

  15.    int[] countArray = new int[d+1];

  16.    for(int i=0; i

  17.        countArray[array[i]-min]++;

  18.    }

  19.    //3.統計陣列做變形,後面的元素等於前面的元素之和

  20.    int sum = 0;

  21.    for(int i=0;i

  22.        sum += countArray[i];

  23.        countArray[i] = sum;

  24.    }

  25.    //4.倒序遍歷原始數列,從統計陣列找到正確位置,輸出到結果陣列

  26.    int[] sortedArray = new int[array.length];

  27.    for(int i=array.length-1;i>=0;i--) {

  28.        sortedArray[countArray[array[i]-min]-1]=array[i];

  29.        countArray[array[i]-min]--;

  30.    }

  31.    return sortedArray;

  32. }

  33. public static void main(String[] args) {

  34.    int[] array = new int[] {95,94,91,98,99,90,99,93,91,92};

  35.    int[] sortedArray = countSort(array);

  36.    System.out.println(Arrays.toString(sortedArray));

  37. }












1.當數列最大最小值差距過大時,並不適用計數排序。


比如給定20個隨機整數,範圍在0到1億之間,這時候如果使用計數排序,需要建立長度1億的陣列。不但嚴重浪費空間,而且時間複雜度也隨之升高。


2.當數列元素不是整數,並不適用計數排序。


如果數列中的元素都是小數,比如25.213,或是0.00000001這樣子,則無法建立對應的統計陣列。這樣顯然無法進行計數排序。




【關於投稿】


如果大家有原創好文投稿,請直接給公號傳送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章連結

② 示例:
【投稿】
《不要自稱是程式員,我十多年的 IT 職場總結》:

http://blog.jobbole.com/94148/


③ 最後請附上您的個人簡介哈~



覺得本文有幫助?請分享給更多人

關註「演演算法愛好者」,修煉程式設計內功

贊(0)

分享創造快樂

© 2024 知識星球   網站地圖