常用排序算法的C語(yǔ)言版實(shí)現(xiàn)示例整理

更新時(shí)間：2016年03月15日 15:15:58 作者：wuzhekai1985

這篇文章主要介紹了常用排序算法的C語(yǔ)言版實(shí)現(xiàn)示例整理,包括快速排序及冒泡排序等,基本上都給出了時(shí)間復(fù)雜度,需要的朋友可以參考下

所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來(lái)。其確切定義如下：
　　輸入：n個(gè)記錄R1，R2，…，Rn，其相應(yīng)的關(guān)鍵字分別為K1，K2，…，Kn。
　　輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
排序的時(shí)間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來(lái)衡量?；镜呐判蛩惴ㄓ腥缦聨追N：交換排序（冒泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、插入排序（直接插入排序、希爾排序）、歸并排序、分配排序（基數(shù)排序、箱排序、計(jì)數(shù)排序）。下面依次列出各種算法的代碼，并進(jìn)行簡(jiǎn)要分析。分配排序算法的代碼沒有列出。
（1）快速排序：快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。最好、平均復(fù)雜度都為O(nlogn)，最壞為O(n^2)。

void quick_sort1(int a[],int l,int r) 
{ 
 if(l >= r) 
  return; 
 int i, j, p; 
 i = l-1, j = l,p = a[r]; 
 while(j < r) 
 { 
  if(a[j] < p) 
   swap(a[++i], a[j]); 
  j++; 
 } 
 swap(a[++i], a[r]); 
 quick_sort1(a, l, i-1); 
 quick_sort1(a, i+1, r); 
}

《算法導(dǎo)論》一書中，給出了這個(gè)程序的偽代碼。當(dāng)數(shù)組元素相等、逆序、順序排列時(shí)，調(diào)用這個(gè)程序會(huì)導(dǎo)致棧溢出。因?yàn)槊看蝿澐侄际亲顗膲姆?。可以改進(jìn)一下。上述程序每次選的劃分基準(zhǔn)元素都是固定的，如果是隨機(jī)產(chǎn)生的，那么可以大大降低出現(xiàn)最壞劃分的概率。

void quick_sort2(int a[],int l,int r) 
{ 
 if(l >= r) 
  return; 
 int i,j,p; 
 i = l-1,j = l; 
 
 p=l + rand()%(r-l); //隨機(jī)產(chǎn)生[l,r)之間的數(shù) 
 swap(a[p], a[r]); 
 p = a[r]; 
 while(j < r) 
 { 
  if(a[j] < p) 
   swap(a[++i], a[j]); 
  j++; 
 } 
 swap(a[++i], a[r]); 
 quick_sort2(a, l, i-1); 
 quick_sort2(a, i+1, r); 
}

但是，當(dāng)數(shù)組元素相等時(shí)，還是出現(xiàn)了棧溢出?？梢宰鋈缦抡{(diào)整。

void quick_sort3(int a[],int l,int r) 
{ 
 if(l >= r) 
  return; 
 int i,j,p; 
 i = l-1, j = r, p = a[r]; 
 while(1) 
 { 
  do { i++; } while(a[i] < p && i < r); 
  do { j--; } while(a[j] > p && j > l); 
  if(i >= j) 
   break; 
  swap(a[i], a[j]); 
 } 
 swap(a[i],a[r]); 
 quick_sort3(a, l, i-1); 
 quick_sort3(a, i+1, r); 
}

但是，當(dāng)數(shù)組元素順序，逆序時(shí)，同樣出現(xiàn)了棧溢出。若將兩者結(jié)合起來(lái)，就可以盡量避免棧溢出。

void quick_sort4(int a[],int l,int r) 
{ 
 if(l >= r) 
  return; 
 int i,j,p; 
 i = l-1, j = r; 
 
 p = l + rand()%(r-l); 
 swap(a[p],a[r]); 
 p = a[r]; 
 while(1) 
 { 
  do { i++; } while(a[i] < p && i < r); 
  do { j--; } while(a[j] > p && j > l); 
  if(i >= j) 
   break; 
  swap(a[i], a[j]); 
 } 
 swap(a[i], a[r]); 
 quick_sort4(a, l, i-1); 
 quick_sort4(a, i+1, r); 
}

（2）冒泡排序：兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。

void bubble_sort1(int a[],int n) 
{ 
 int i,j; 
 for(i = 0; i < n-1; i++) 
 { 
  for(j = i+1; j < n; j++) 
  { 
   if(a[i] > a[j]) 
    swap(a[i], a[j]); 
  } 
 } 
}

可以稍作改進(jìn)，當(dāng)數(shù)組數(shù)元素順序時(shí)，時(shí)間復(fù)雜度為O(n)。加入一個(gè)變量，如果在一遍掃描中，沒有出現(xiàn)交換，那么結(jié)束排序，因?yàn)閿?shù)組已排好序了。

void bubble_sort2(int a[],int n) 
{ 
 int i,j; 
 for(i = 0; i < n-1; i++) 
 { 
  bool exchange = false; 
  for(j = i+1; j < n; j++) 
  { 
   if(a[i] > a[j]) 
   { 
    exchange = true; 
    swap(a[i], a[j]); 
   } 
  } 
  if(exchange == false) 
   break; 
 } 
}

經(jīng)網(wǎng)友指出，上面這個(gè)冒泡排序有問題，無(wú)法得到正確結(jié)果。下面引自網(wǎng)友的正確寫法：

void bubble_sort2(int a[],int n) 
{ 
 int i,j; 
 for(i = 0;i < n-1; i++) 
 { 
  bool exchange = false; 
  for(j = n-1;j > i; j--) 
  { 
   if(a[j-1] > a[j]) 
   { 
    exchange = true; 
    swap(a[j-1], a[j]); 
   } 
  }  
  if(exchange == false) 
   break; 
 } 
}

（3）直接選擇排序：每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排好序的子文件的最后，直到全部記錄排序完畢。

void select_sort1(int a[],int n) 
{ 
 int i,j; 
 for(i = 0; i < n-1; i++) 
 { 
  int min = i; 
  for(j = i+1; j < n; j++) 
  { 
   if(a[j] < a[min]) 
    min = j; 
  } 
  if(min != i) 
   swap(a[i], a[min]); 
 } 
}

（4）堆排序：根據(jù)輸入數(shù)據(jù)，利用堆的調(diào)整算法形成初始堆，然后交換根元素與尾元素，總的元素個(gè)數(shù)減1，然后從根往下調(diào)整。堆排序的最好、最壞、平均時(shí)間復(fù)雜度都為O(nlogn)

void heap_siftdown(int a[],int n,int p) //調(diào)整算法 
{ 
 int i = p,j = i*2+1; 
 int tmp = a[i]; 
 while(j < n) 
 { 
  if(j+1 < n && a[j] < a[j+1]) 
   j++; 
  if(a[j] <= tmp) 
   break; 
  else 
  { 
   a[i] = a[j]; 
   i = j;j = j*2+1; 
  } 
 } 
 a[i] = tmp; 
} 
void heap_sort1(int a[],int n) 
{ 
 int i; 
 for(i = (n-1)/2; i >= 0;i--) 
  heap_siftdown(a, n, i); 
 for(i = n-1;i >= 0; i--) 
 { 
  swap(a[i], a[0]); 
  heap_siftdown(a, i, 0); 
 } 
}

（5）直接插入排序：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。當(dāng)數(shù)組已經(jīng)排好序，直接插入排序的時(shí)間復(fù)雜度為O(n)

void insert_sort1(int a[],int n) 
{ 
 int i,j; 
 for(i = 1; i < n; i++) 
 { 
  for(j = i; j > 0 && a[j]<a[j-1]; j--) 
   swap(a[j-1], a[j]); 
 } 
}

如果將交換函數(shù)展開，可以加快排序的速度。

void insert_sort2(int a[],int n) 
{ 
 int i,j; 
 for(i = 1; i < n; i++) 
 { 
  for(j = i; j > 0 && a[j] < a[j-1]; j--) 
  { 
   int t = a[j-1]; 
   a[j-1] = a[j]; 
   a[j] = t; 
  } 
 } 
}

可以進(jìn)一步改進(jìn)，insert_sort2的算法不斷給t賦值，可以將賦值語(yǔ)句移到循環(huán)外面。

void insert_sort3(int a[],int n) 
{ 
 int i,j; 
 for(i = 1;i < n; i++) 
 { 
  int t = a[i]; 
  for(j = i; j > 0 && a[j-1] > t; j--) 
   a[j] = a[j-1]; 
  a[j] = t; 
 } 
}

（6）希爾排序：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為dl的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?br /> 最后一遍的增量必須是1，其實(shí)是就是調(diào)用直接插入排序算法。

void shell_sort1(int a[],int n) 
{ 
 int i = n; 
 do{ 
  i = i/3 + 1; 
  shell_pass1(a, n, i); 
 }while(i > 1); 
} 
void shell_pass1(int a[],int n,int inc) //inc為1時(shí)，其實(shí)就是直接插入排序 
{ 
 int i,j; 
 for(i = inc; i < n; i++) 
 { 
  int t=a[i]; 
  for(j = i;j >= inc && a[j-inc] > t; j-= inc) 
   a[j] = a[j-inc]; 
  a[j] = t; 
 } 
}

（7）歸并排序：利用"歸并"技術(shù)來(lái)進(jìn)行排序。歸并是指將若干個(gè)已排序的子文件合并成一個(gè)有序的文件?？梢杂糜谕馀判?。

void merge_sort1(int a[],int b[],int l,int r) 
{ 
 if(l >= r) 
  return; 
 int m = (l+r)/2; 
 merge_sort1(a, b, l, m); 
 merge_sort1(a, b, m+1, r); 
 merge1(a, b, l, m, r); 
} 
void merge1(int a[],int b[],int l,int m,int r) 
{ 
 int i,j,k; 
 for(i = l; i <= r; i++) 
  b[i] = a[i]; 
 i = l; j = m+1; k = l; 
 while(i <= m && j <= r) 
 { 
  if(b[i] <= b[j]) a[k++] = b[i++]; 
  else a[k++] = b[j++]; 
 } 
 while(i <= m) a[k++] = b[i++]; 
 while(j <= r) a[k++] = b[j++]; 
}

給出上述算法的程序的測(cè)試驅(qū)動(dòng)程序及兩個(gè)輔助程序。要測(cè)試某種排序算法，只需將注釋去掉即可。

#include <iostream> 
#include <ctime> 
using namespace std; 
const int N = 100; 
int a[N]; 
int b[N]; 
 
int main() 
{ 
 int i; 
 srand(time(0)); 
 //for(i=0;i<N;i++) 
 // a[i]= N-i; 
 for(i = 0;i < N; i++) 
  a[i]=rand()%N; 
 long start,end; 
 start = clock(); 
 
 //quick_sort1(a,0,N-1); 
 //quick_sort2(a,0,N-1); 
 //quick_sort3(a,0,N-1); 
 //quick_sort4(a,0,N-1); 
 //bubble_sort1(a,N); 
 //bubble_sort2(a,N); 
 //merge_sort1(a,b,0,N-1); 
 //heap_sort1(a,N); 
 //shell_sort1(a,N); 
 //select_sort1(a,N); 
 //insert_sort1(a,N); 
 //insert_sort2(a,N); 
 //insert_sort3(a,N); 
 
 end = clock(); 
 print_array(a, N); 
 cout<<"total time is : "<<(end-start)/1000.0<<'s'<<endl; 
 return 0; 
} 
 
void swap(int a[],int i,int j) //交換元素 
{ 
 int t = a[i]; 
 a[i] = a[j]; 
 a[j] = t; 
} 
 
void print_array(int a[],int n) //打印元素值 
{ 
 for(int i = 0; i < n; i++) 
 { 
  cout<<a[i]<<' '; 
  if(i%10==0 && i!=0) 
   cout<<endl; 
 } 
 cout<<endl; 
}

您可能感興趣的文章: