本文將通過動態(tài)演示+代碼的形式系統(tǒng)地總結(jié)十大經(jīng)典排序算法。
排序算法
算法分類
十種常見排序算法可以分為兩大類:
比較類排序:通過比較來決定元素間的相對次序,由于其時(shí)間復(fù)雜度不能突破O(nlogn),因此也稱為非線性時(shí)間比較類排序。
非比較類排序:不通過比較來決定元素間的相對次序,它可以突破基于比較排序的時(shí)間下界,以線性時(shí)間運(yùn)行,因此也稱為線性時(shí)間非比較類排序。
算法復(fù)雜度
排序算法 | 平均時(shí)間復(fù)雜度 | 最差時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 數(shù)據(jù)對象穩(wěn)定性 |
---|---|---|---|---|
冒泡排序 | O(n2) | O(n2) | O(1) | 穩(wěn)定 |
選擇排序 | O(n2) | O(n2) | O(1) | 數(shù)組不穩(wěn)定、鏈表穩(wěn)定 |
插入排序 | O(n2) | O(n2) | O(1) | 穩(wěn)定 |
快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不穩(wěn)定 |
堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不穩(wěn)定 |
歸并排序 | O(n*log2n) | O(n*log2n) | O(n) | 穩(wěn)定 |
希爾排序 | O(n*log2n) | O(n2) | O(1) | 不穩(wěn)定 |
計(jì)數(shù)排序 | O(n+m) | O(n+m) | O(n+m) | 穩(wěn)定 |
桶排序 | O(n) | O(n) | O(m) | 穩(wěn)定 |
基數(shù)排序 | O(k*n) | O(n2) | 穩(wěn)定 |
1. 冒泡排序
算法思想:
比較相鄰的元素。如果第一個(gè)比第二個(gè)大,就交換它們兩個(gè)
對每一對相鄰元素作同樣的工作,從開始第一對到結(jié)尾的最后一對,這樣在最后的元素應(yīng)該會是最大的數(shù);
針對所有的元素重復(fù)以上的步驟,除了最后一個(gè);
重復(fù)步驟1~3,直到排序完成。
代碼:
voidbubbleSort(inta[],intn) { for(inti=0;ia[j+1]) { inttmp=a[j];//交換 a[j]=a[j+1]; a[j+1]=tmp; } } } }
2. 選擇排序
算法思想:
在未排序序列中找到最?。ù螅┰?,存放到排序序列的起始位置
從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?,然后放到已排序序列的末
以此類推,直到所有元素均排序完畢
代碼:
voidselectionSort(intarr[],intn){ intminIndex,temp; for(inti=0;i
3. 插入排序
算法思想:
從第一個(gè)元素開始,該元素可以認(rèn)為已經(jīng)被排序;
取出下一個(gè)元素,在已經(jīng)排序的元素序列中從后向前掃描;
如果該元素(已排序)大于新元素,將該元素移到下一位置;
重復(fù)步驟3,直到找到已排序的元素小于或者等于新元素的位置;
將新元素插入到該位置后;
重復(fù)步驟2~5。
代碼:
voidprint(inta[],intn,inti){ cout<
算法分析:
插入排序在實(shí)現(xiàn)上,通常采用in-place排序(即只需用到O(1)的額外空間的排序),因而在從后向前掃描過程中,需要反復(fù)把已排序元素逐步向后挪位,為最新元素提供插入空間。
4.快速排序
快速排序的基本思想是通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分,其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小,則可分別對這兩部分記錄繼續(xù)進(jìn)行排序,以達(dá)到整個(gè)序列有序。
算法思想:
選取第一個(gè)數(shù)為基準(zhǔn)
將比基準(zhǔn)小的數(shù)交換到前面,比基準(zhǔn)大的數(shù)交換到后面
遞歸地(recursive)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序
代碼:
voidQuickSort(vector&v,intlow,inthigh){ if(low>=high)//結(jié)束標(biāo)志 return; intfirst=low;//低位下標(biāo) intlast=high;//高位下標(biāo) intkey=v[first];//設(shè)第一個(gè)為基準(zhǔn) while(first=key) last--; if(first
5.堆排序
堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu),并同時(shí)滿足堆積的性質(zhì):即子節(jié)點(diǎn)的鍵值或索引總是小于(或者大于)它的父節(jié)點(diǎn)。
算法思想:
將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆,此堆為初始的無序區(qū);
將堆頂元素R[1]與最后一個(gè)元素R[n]交換,此時(shí)得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n];
由于交換后新的堆頂R[1]可能違反堆的性質(zhì),因此需要對當(dāng)前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆,然后再次將R[1]與無序區(qū)最后一個(gè)元素交換,得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1,則整個(gè)排序過程完成。
代碼:
#include#include usingnamespacestd; //堆排序:(最大堆,有序區(qū))。從堆頂把根卸出來放在有序區(qū)之前,再恢復(fù)堆。 voidmax_heapify(intarr[],intstart,intend){ //建立父節(jié)點(diǎn)指標(biāo)和子節(jié)點(diǎn)指標(biāo) intdad=start; intson=dad*2+1; while(son<=?end)?{?//若子節(jié)點(diǎn)在范圍內(nèi)才做比較 ????????if?(son?+?1?<=?end?&&?arr[son]?arr[son])//如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)代表調(diào)整完成,直接跳出函數(shù) return; else{//否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)與孫節(jié)點(diǎn)比較 swap(arr[dad],arr[son]); dad=son; son=dad*2+1; } } } voidheap_sort(intarr[],intlen){ //初始化,i從最后一個(gè)父節(jié)點(diǎn)開始調(diào)整 for(inti=len/2-1;i>=0;i--) max_heapify(arr,i,len-1); //先將第一個(gè)元素和已經(jīng)排好的元素前一位做交換,再從新調(diào)整(剛調(diào)整的元素之前的元素),直到排序完成 for(inti=len-1;i>0;i--){ swap(arr[0],arr[i]); max_heapify(arr,0,i-1); } } intmain(){ intarr[]={3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6}; intlen=(int)sizeof(arr)/sizeof(*arr); heap_sort(arr,len); for(inti=0;i
6. 歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并,得到完全有序的序列;即先使每個(gè)子序列有序,再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表,稱為2-路歸并。
算法思想:
把長度為n的輸入序列分成兩個(gè)長度為n/2的子序列;
對這兩個(gè)子序列分別采用歸并排序;
將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。
代碼:
voidprint(inta[],intn){ for(intj=0;j
7. 希爾排序
1959年Shell發(fā)明,第一個(gè)突破O(n2)的排序算法,是簡單插入排序的改進(jìn)版。它與插入排序的不同之處在于,它會優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。
算法思想:
選擇一個(gè)增量序列t1,t2,…,tk,其中ti>tj,tk=1;
按增量序列個(gè)數(shù)k,對序列進(jìn)行k 趟排序;
每趟排序,根據(jù)對應(yīng)的增量ti,將待排序列分割成若干長度為m 的子序列,分別對各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí),整個(gè)序列作為一個(gè)表來處理,表長度即為整個(gè)序列的長度。
代碼:
voidshell_sort(Tarray[],intlength){ inth=1; while(h=1){ for(inti=h;i=h&&array[j]
8 計(jì)數(shù)排序
計(jì)數(shù)排序不是基于比較的排序算法,其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序,計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
算法思想:
找出待排序的數(shù)組中最大和最小的元素;
統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù),存入數(shù)組C的第i項(xiàng);
對所有的計(jì)數(shù)累加(從C中的第一個(gè)元素開始,每一項(xiàng)和前一項(xiàng)相加);
反向填充目標(biāo)數(shù)組:將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng),每放一個(gè)元素就將C(i)減去1。
代碼:
#include#include #include usingnamespacestd; //計(jì)數(shù)排序 voidCountSort(vector &vecRaw,vector &vecObj) { //確保待排序容器非空 if(vecRaw.size()==0) return; //使用vecRaw的最大值+1作為計(jì)數(shù)容器countVec的大小 intvecCountLength=(*max_element(begin(vecRaw),end(vecRaw)))+1; vector vecCount(vecCountLength,0); //統(tǒng)計(jì)每個(gè)鍵值出現(xiàn)的次數(shù) for(inti=0;i0;i--)//此處逆序是為了保持相同鍵值的穩(wěn)定性 vecObj[--vecCount[vecRaw[i-1]]]=vecRaw[i-1]; } intmain() { vector vecRaw={0,5,7,9,6,3,4,5,2,8,6,9,2,1}; vector vecObj(vecRaw.size(),0); CountSort(vecRaw,vecObj); for(inti=0;i
9 桶排序
將值為i的元素放入i號桶,最后依次把桶里的元素倒出來。
算法思想:
設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。
尋訪序列,并且把項(xiàng)目一個(gè)一個(gè)放到對應(yīng)的桶子去。
對每個(gè)不是空的桶子進(jìn)行排序。
從不是空的桶子里把項(xiàng)目再放回原來的序列中。
代碼:
voidBucket_Sort(inta[],intn,intmax){ inti,j=0; int*buckets=(int*)malloc((max+1)*sizeof(int)); //將buckets中的所有數(shù)據(jù)都初始化為0 memset(buckets,0,(max+1)*sizeof(int)); //1.計(jì)數(shù) for(i=0;i0){ a[j++]=i; } } } intmain(){ intarr[]={9,5,1,6,2,3,0,4,8,7}; Bucket_Sort(arr,10,9); for(inti=0;i10;?i++)?{ ????????printf("%d?",?arr[i]); ????} ????printf(" "); ? ????return?0; }
10 基數(shù)排序
一種多關(guān)鍵字的排序算法,可用桶排序?qū)崿F(xiàn)。
算法思想:
取得數(shù)組中的最大數(shù),并取得位數(shù);
arr為原始數(shù)組,從最低位開始取每個(gè)位組成radix數(shù)組;
對radix進(jìn)行計(jì)數(shù)排序(利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn))
代碼:
intmaxbit(intdata[],intn)//輔助函數(shù),求數(shù)據(jù)的最大位數(shù) { intmaxData=data[0];///=p) { //p*=10;//Maybeoverflow maxData/=10; ++d; } returnd; /*intd=1;//保存最大的位數(shù) intp=10; for(inti=0;i=p) { p*=10; ++d; } } returnd;*/ } voidradixsort(intdata[],intn)//基數(shù)排序 { intd=maxbit(data,n); int*tmp=newint[n]; int*count=newint[10];//計(jì)數(shù)器 inti,j,k; intradix=1; for(i=1;i<=?d;?i++)?//進(jìn)行d次排序 ????{ ????????for(j?=?0;?j?10;?j++) ????????????count[j]?=?0;?//每次分配前清空計(jì)數(shù)器 ????????for(j?=?0;?j?=0;j--)//將所有桶中記錄依次收集到tmp中 { k=(data[j]/radix)%10; tmp[count[k]-1]=data[j]; count[k]--; } for(j=0;j
審核編輯:湯梓紅
-
算法
+關(guān)注
關(guān)注
23文章
4552瀏覽量
92020 -
C語言
+關(guān)注
關(guān)注
180文章
7575瀏覽量
134046 -
代碼
+關(guān)注
關(guān)注
30文章
4671瀏覽量
67765 -
數(shù)據(jù)結(jié)構(gòu)
+關(guān)注
關(guān)注
3文章
568瀏覽量
40030 -
排序算法
+關(guān)注
關(guān)注
0文章
51瀏覽量
10042
原文標(biāo)題:C語言 | 動圖演示十大經(jīng)典排序算法(含代碼)
文章出處:【微信號:混說Linux,微信公眾號:混說Linux】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論