動圖演示C語言10大經(jīng)典排序算法(含代碼)

本文將通過動態(tài)演示+代碼的形式系統(tǒng)地總結(jié)十大經(jīng)典排序算法。

排序算法

算法分類

十種常見排序算法可以分為兩大類：

• 比較類排序：通過比較來決定元素間的相對次序，由于其時間復(fù)雜度不能突破O(nlogn)，因此也稱為非線性時間比較類排序。

• 非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運(yùn)行，因此也稱為線性時間非比較類排序。

1. 冒泡排序

• 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個

• 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會是最大的數(shù)；

• 針對所有的元素重復(fù)以上的步驟，除了最后一個；

• 重復(fù)步驟1~3，直到排序完成。

代碼：

voidbubbleSort(inta[],intn)
{
for(inti=0;i-1;++i)
{
for(intj=0;j-1;++j)
{
if(a[j]>a[j+1])
{
inttmp=a[j];//交換
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
}

2. 選擇排序

算法思想：

• 在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置

• 從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪?/p>

• 以此類推，直到所有元素均排序完畢

代碼：

voidselectionSort(intarr[],intn){
intminIndex,temp;
for(inti=0;i1;i++){
minIndex=i;
for(varj=i+1;jif(arr[j]//尋找最小的數(shù)
minIndex=j;//將最小數(shù)的索引保存
}
}
temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
for(intk=0;iprintf("%d",arr[k]);
}
}

3. 插入排序

• 從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序；

• 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；

• 如果該元素（已排序）大于新元素，將該元素移到下一位置；

• 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；

• 將新元素插入到該位置后；

• 重復(fù)步驟2~5。

代碼：

voidprint(inta[],intn,inti){
cout<":";
for(intj=0;j<8;j++){
cout<"";
}
cout<<endl;
}
voidInsertSort(inta[],intn)
{
for(inti=1;iif(a[i]-1]){//若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入
intj=i-1;
intx=a[i];//復(fù)制為哨兵，即存儲待排序元素
a[i]=a[i-1];//先后移一個元素
while(x//查找在有序表的插入位置
a[j+1]=a[j];
j--;//元素后移
}
a[j+1]=x;//插入到正確位置
}
print(a,n,i);//打印每趟排序的結(jié)果
}

}

intmain(){
inta[15]={2，3,4,5,15，19，16，27，36，38，44，46，47，48，50};
InsertSort(a,15);
print(a,15,15);
}

插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

4.快速排序

快速排序的基本思想是通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。

• 選取第一個數(shù)為基準(zhǔn)

• 將比基準(zhǔn)小的數(shù)交換到前面，比基準(zhǔn)大的數(shù)交換到后面

• 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序

代碼：

voidQuickSort(vector<int>&v,intlow,inthigh){
if(low>=high)//結(jié)束標(biāo)志
return;
intfirst=low;//低位下標(biāo)
intlast=high;//高位下標(biāo)
intkey=v[first];//設(shè)第一個為基準(zhǔn)

while(first//將比第一個小的移到前面
while(first=key)
last--;
if(first//將比第一個大的移到后面
while(firstif(first//
v[first]=key;
//前半遞歸
QuickSort(v,low,first-1);
//后半遞歸
QuickSort(v,first+1,high);
}

5.堆排序

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子節(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

• 將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)；

• 將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(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ū)最后一個元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個數(shù)為n-1，則整個排序過程完成。

代碼：

#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]?1])//先比較兩個子節(jié)點(diǎn)指標(biāo)，選擇最大的
son++;
if(arr[dad]>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從最后一個父節(jié)點(diǎn)開始調(diào)整
for(inti=len/2-1;i>=0;i--)
max_heapify(arr,i,len-1);
//先將第一個元素和已經(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;icout<'';
cout<endl;
return0;
}

6. 歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。

• 把長度為n的輸入序列分成兩個長度為n/2的子序列；

• 對這兩個子序列分別采用歸并排序；

• 將兩個排序好的子序列合并成一個最終的排序序列。

代碼：

voidprint(inta[],intn){
for(intj=0;jcout<"";
}
cout<<endl;
}

//將r[i…m]和r[m+1…n]歸并到輔助數(shù)組rf[i…n]
voidMerge(ElemType*r,ElemType*rf,inti,intm,intn)
{
intj,k;
for(j=m+1,k=i;i<=m?&&?j?<=n?;?++k){
????if(r[j]elserf[k]=r[i++];
}
while(i<=?m)??rf[k++]?=?r[i++];
??while(j<=?n)??rf[k++]?=?r[j++];
??print(rf,n+1);
}

voidMergeSort(ElemType*r,ElemType*rf,intlenght)
{
intlen=1;
ElemType*q=r;
ElemType*tmp;
while(lenints=len;
len=2*s;
inti=0;
while(i+len-1,i+len-1);//對等長的兩個子表合并
i=i+len;
}
if(i+s-1,lenght-1);//對不等長的兩個子表合并
}
tmp=q;q=rf;rf=tmp;//交換q,rf，以保證下一趟歸并時，仍從q歸并到rf
}
}


intmain(){
inta[10]={2，3,4，5,15,19,26,27,36,38,44,46,47,48,50};
intb[10];
MergeSort(a,b,15);
print(b,15);
cout<<"結(jié)果：";
print(a,10);
}

7. 希爾排序

1959年Shell發(fā)明，第一個突破O(n2)的排序算法，是簡單插入排序的改進(jìn)版。它與插入排序的不同之處在于，它會優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。

• 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；

• 按增量序列個數(shù)k，對序列進(jìn)行k 趟排序；

• 每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進(jìn)行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

代碼：

voidshell_sort(Tarray[],intlength){
inth=1;
while(h3){
h=3*h+1;
}
while(h>=1){
for(inti=h;ifor(intj=i;j>=h&&array[j]array[j-h];j-=h){
std::swap(array[j],array[j-h]);
}
}
h=h/3;
}
}

8 計數(shù)排序

計數(shù)排序不是基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復(fù)雜度的排序，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

• 找出待排序的數(shù)組中最大和最小的元素；

• 統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)；

• 對所有的計數(shù)累加（從C中的第一個元素開始，每一項(xiàng)和前一項(xiàng)相加）；

• 反向填充目標(biāo)數(shù)組：將每個元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個元素就將C(i)減去1。

代碼：

#include
#include
#include

usingnamespacestd;

//計數(shù)排序
voidCountSort(vector<int>&vecRaw,vector<int>&vecObj)
{
//確保待排序容器非空
if(vecRaw.size()==0)
return;

//使用vecRaw的最大值+1作為計數(shù)容器countVec的大小
intvecCountLength=(*max_element(begin(vecRaw),end(vecRaw)))+1;
vector<int>vecCount(vecCountLength,0);

//統(tǒng)計每個鍵值出現(xiàn)的次數(shù)
for(inti=0;i//后面的鍵值出現(xiàn)的位置為前面所有鍵值出現(xiàn)的次數(shù)之和
for(inti=1;i1];

//將鍵值放到目標(biāo)位置
for(inti=vecRaw.size();i>0;i--)//此處逆序是為了保持相同鍵值的穩(wěn)定性
vecObj[--vecCount[vecRaw[i-1]]]=vecRaw[i-1];
}

intmain()
{
vector<int>vecRaw={0,5,7,9,6,3,4,5,2,8,6,9,2,1};
vector<int>vecObj(vecRaw.size(),0);

CountSort(vecRaw,vecObj);

for(inti=0;icout<"";
cout<endl;

return0;
}

9 桶排序

將值為i的元素放入i號桶，最后依次把桶里的元素倒出來。

• 設(shè)置一個定量的數(shù)組當(dāng)作空桶子。

• 尋訪序列，并且把項(xiàng)目一個一個放到對應(yīng)的桶子去。

• 對每個不是空的桶子進(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.計數(shù)
for(i=0;iprintf("%d:%d
",a[i],buckets[a[i]]);
}
printf("
");
//2.排序
for(i=0;i1;i++){
while((buckets[i]--)>0){
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("
");

return0;
}

10 基數(shù)排序

一種多關(guān)鍵字的排序算法，可用桶排序?qū)崿F(xiàn)。

• 取得數(shù)組中的最大數(shù)，并取得位數(shù)；

• arr為原始數(shù)組，從最低位開始取每個位組成radix數(shù)組；

• 對radix進(jìn)行計數(shù)排序（利用計數(shù)排序適用于小范圍數(shù)的特點(diǎn)）

代碼：

intmaxbit(intdata[],intn)//輔助函數(shù)，求數(shù)據(jù)的最大位數(shù)
{
intmaxData=data[0];///
///先求出最大數(shù)，再求其位數(shù)，這樣有原先依次每個數(shù)判斷其位數(shù)，稍微優(yōu)化點(diǎn)。
for(inti=1;iif(maxDataintd=1;
intp=10;
while(maxData>=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];//計數(shù)器
inti,j,k;
intradix=1;
for(i=1;i<=?d;?i++)?//進(jìn)行d次排序
{
for(j=0;j10;j++)
count[j]=0;//每次分配前清空計數(shù)器
for(j=0;j10;//統(tǒng)計每個桶中的記錄數(shù)
count[k]++;
}
for(j=1;j10;j++)
count[j]=count[j-1]+count[j];//將tmp中的位置依次分配給每個桶
for(j=n-1;j>=0;j--)//將所有桶中記錄依次收集到tmp中
{
k=(data[j]/radix)%10;
tmp[count[k]-1]=data[j];
count[k]--;
}
for(j=0;j//將臨時數(shù)組的內(nèi)容復(fù)制到data中
data[j]=tmp[j];
radix=radix*10;
}
delete[]tmp;
delete[]count;
}

審核編輯 ：李倩