【排序算法】计数排序引发的围观风波——一种O(n)的排序
前言
計算機課上,老師給一串數字6 1 6 9 9 1 4 2 1 5 8 8,問道:這一串數字,你們寫個程序給我看,要求效率較高。學不出來的別下課了。
頓時場下一片嘩然,但有很多小朋友硬著頭皮啪啪啪的開始敲了。
老師走到pigpian身邊,pigpian很難得皺了皺眉頭
很難很難得寫下了下面代碼:
老師:“gun吧,都2020年還用O(n2)得算法,快,快回去吃飯吧,快gun吧”。pigpian一臉無奈得走出教室,接著老師問道有沒有其他人寫出來,慢慢得挪到doudou得旁邊。
doudou著急解釋道:老師,你看我的O(nlogn)得快排算法:
int a[]= {6,1,6,9,9,1,4,2,1,5,8,8}; Arrays.sort(a); System.out.println(Arrays.toString(a));老師輕蔑得嘲諷道:“gun 吧,就知道投機取巧,我看你海!回去吃飯吧” 緊著著老師走到bigmao 的旁邊,bigmao 給老師看了他的代碼:
private static void quicksort(int [] a,int left,int right) {int low=left;int high=right;//下面兩句的順序一定不能混,否則會產生數組越界!!!very important!!!if(low>high)return;int k=a[low];//取最左側的一個作為衡量,最后要求左側都比它小,右側都比它大。while(low<high){while(low<high&&a[high]>=k){high--;}//這樣就找到第一個比它小的了a[low]=a[high];while(low<high&&a[low]<=k){low++;}a[high]=a[low]; }a[low]=k;quicksort(a, left, low-1);quicksort(a, low+1, right); }老師臉角泛起微光:“不錯不錯,手寫快排還是挺棒的,回去吃飯吧!”。
此時bigsai舉起他的小手手:“老師快來,我寫的這個賊快”。bigsai亮起他的代碼:
int a[]= {6,1,6,9,9,1,4,2,1,5,8,8}; int count[]=new int[10]; for(int i=0;i<a.length;i++) {count[a[i]]++; } int index=0; for(int i=0;i<count.length;i++) {while (count[i]-->0) {a[index++]=i;} } System.out.println(Arrays.toString(a));"不錯不錯,這個方法效率確實很高,你回去把這種排序的方法和大家分享一下吧!"老師驚艷道!
待bigsai出門后,站在門外的pigpian和doudou攔住問道:“sai哥這是啥東東啊”。
"計數排序。流程看圖,聽我下面慢慢講:"
計數排序介紹
或許上面的代碼你看起來還有點懵逼,但是不要緊,我們在這里給你講明白什么是計數排序。對于計數排序,百度百科是這么說的:
計數排序是一個非基于比較的排序算法,該算法于1954年由 Harold H. Seward 提出。它的優勢在于在對一定范圍內的整數排序時,它的復雜度為Ο(n+k)(其中k是整數的范圍),快于任何比較排序算法。 當然這是一種犧牲空間換取時間的做法,而且當O(k)>O(n*log(n))的時候其效率反而不如基于比較的排序(基于比較的排序的時間復雜度在理論上的下限是O(n*log(n)), 如歸并排序,堆排序)
對于額外數組該如何理解呢?
我們慢慢來,在以前介紹桶排序的時候,我們知道每個桶里面是可以給一個范圍的數字放進去。從每個桶的實質來看可以是List集合。
但如果每個桶中只有一種元素,那么這個桶就可以不需要使用集合去儲存標記,而是用一個數字即可進行標記認為它出現了多少次。
所以這種每個桶只能放一種元素的,我們不需要每個桶再用List集合去裝,而用數組的值儲存對應編號出現的詞數即可,例如上述的a[1]=2表示其中的1號桶出現兩次,而a[3]=0表示元素3沒有出現過。
而這樣的數值如何計算呢?
- 很簡單,對待排序目標序列遍歷一次,每次遍歷的值讓這個值的編號加上1,說明對應元素詞數加一。例如上述第一個1就a[1]++,第二個5就a[5]++……
- 然后取值時候遍歷這個數字,順序將目標編號的數字取出來即可。(每取一個對應位置數值減1直到為0為止)。例如上述遍歷這個數組,就獲得1 1 2 4 4 5這個序列。你看看,這個時間復雜度是不是O(n)的?
上面算法設計就很好了嘛?當然不是,如果是1,2 ,3之類數據肯定沒啥問題,但是如果1000001,1000002,1000003之類的序列你這么開數組不是太多空間了?并且前面也要遍歷很多無用的次數。
所以我們在設計具體算法的時候,先找到最小值min,再找最大值max。然后創建這個區間大小的數組,從min的位置開始計數,這樣就可以最大程度的壓縮空間,提高空間的使用效率。
代碼實現
通過上述分析,計數排序的實現代碼為:
import java.util.Arrays;public class test {public static void jishusort(int a[]){int min=Integer.MAX_VALUE;int max=Integer.MIN_VALUE;for(int i=0;i<a.length;i++)//找到max和min{if(a[i]<min) min=a[i];if(a[i]>max)max=a[i];}int count[]=new int[max-min+1];//對元素進行計數for(int i=0;i<a.length;i++){count[a[i]-min]++;}//排序取值int index=0;for(int i=0;i<count.length;i++){while (count[i]-->0) {a[index++]=i+min;//有min才是真正值}}}public static void main(String[] args) {int a[]= {6,1,6,9,9,1,4,2,1,5,8,8};jishusort(a);System.out.println(Arrays.toString(a));}}打印結果為:
[1, 1, 1, 2, 4, 5, 6, 6, 8, 8, 9, 9]
結語
通過上面我想計數排序你已經搞得很清楚了,計數排序的時間復雜度為O(n+k)其中k為正數范圍;線性時間大部分都比其他排序快一點,但是也不一定,例如你遇到1 2 4 2 100001這樣一個序列,其中k的范圍為10000,雖然他是O(n+k)=O(k)k遠大于n情況,但是此時O(k)>O(nlogn)因為n太小,而K太大,需要遍歷的詞數太多了。
所以即使計數排序它是線性但是并非所有情況都是最好的方法,并且也占用了太多內存。當數據范圍波動不是很大,數據相對比較集中,這時候用計數排序肯定是最好的啦,這點和桶排序的要求很像哦,沒錯,它其實就是一種特殊的桶排序,他的桶大小為1,用數值計數詞數而以,其他都是一樣的操作。
此時bigsai沾沾自喜終于講完了,在旁邊的pigpian和doudou直呼:講的真的太好了,我不光要把它收藏下來,我還要給你點贊!
bigsai笑了,心想光點贊哪里夠🤭,陰森森的沖著兩個少女……說到:點贊收藏哪里夠,公眾號也順便一波:bigsai 關注一波,后面還會講其他的。
結語
原創不易,最后我請你幫兩件事幫忙一下:
star支持一下, 您的肯定是我在csdn創作的源源動力。
微信搜索「bigsai」,關注我的公眾號,不僅免費送你電子書,我還會第一時間在公眾號分享知識技術。加我還可拉你進力扣打卡群一起打卡LeetCode。
記得關注、咱們下次再見!
總結
以上是生活随笔為你收集整理的【排序算法】计数排序引发的围观风波——一种O(n)的排序的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: LeetCode精讲 03无重复字符的最
- 下一篇: LeetCode 04寻找两个正序数组的