常用排序算法的C語言版實現(xiàn)示例整理
所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關(guān)鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量?；镜呐判蛩惴ㄓ腥缦聨追N：交換排序（冒泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、插入排序（直接插入排序、希爾排序）、歸并排序、分配排序（基數(shù)排序、箱排序、計數(shù)排序）。下面依次列出各種算法的代碼，并進行簡要分析。分配排序算法的代碼沒有列出。
（1）快速排序：快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。最好、平均復雜度都為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);
}
《算法導論》一書中，給出了這個程序的偽代碼。當數(shù)組元素相等、逆序、順序排列時，調(diào)用這個程序會導致棧溢出。因為每次劃分都是最壞壞分?？梢愿倪M一下。上述程序每次選的劃分基準元素都是固定的，如果是隨機產(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); //隨機產(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);
}
但是，當數(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);
}
但是，當數(shù)組元素順序，逆序時，同樣出現(xiàn)了棧溢出。若將兩者結(jié)合起來，就可以盡量避免棧溢出。
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)兩個記錄的次序相反時即進行交換，直到?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]);
}
}
}
可以稍作改進，當數(shù)組數(shù)元素順序時，時間復雜度為O(n)。加入一個變量，如果在一遍掃描中，沒有出現(xiàn)交換，那么結(jié)束排序，因為數(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)友指出，上面這個冒泡排序有問題，無法得到正確結(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)整算法形成初始堆，然后交換根元素與尾元素，總的元素個數(shù)減1，然后從根往下調(diào)整。堆排序的最好、最壞、平均時間復雜度都為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）直接插入排序：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當位置，直到全部記錄插入完成為止。當數(shù)組已經(jīng)排好序，直接插入排序的時間復雜度為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;
}
}
}
可以進一步改進，insert_sort2的算法不斷給t賦值，可以將賦值語句移到循環(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）希爾排序：先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插人排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
最后一遍的增量必須是1，其實是就是調(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時，其實就是直接插入排序
{
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ù)來進行排序。歸并是指將若干個已排序的子文件合并成一個有序的文件?？梢杂糜谕馀判?。
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++];
}
給出上述算法的程序的測試驅(qū)動程序及兩個輔助程序。要測試某種排序算法，只需將注釋去掉即可。
#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;
}
相關(guān)文章
位圖實際上就是一個數(shù)組，因為數(shù)組有隨機訪問的功能，比較方便查找，這個數(shù)組一般是整形，今天通過本文給大家分享c++位圖的實現(xiàn)原理及實現(xiàn)代碼，感興趣的朋友跟隨小編一起看看吧2021-05-05
這篇文章主要介紹了VC實現(xiàn)獲取本機MAC地址的方法,需要的朋友可以參考下2014-07-07
這篇文章主要為大家詳細介紹了如何利用Qt實現(xiàn)MP3音樂播放器，文中的示例代碼講解詳細，具有一定的參考價值，感興趣的小伙伴可以了解一下2023-03-03
這篇文章主要為大家詳細介紹了C++17中std::byte的具體使用,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2023-11-11
C++中拷貝構(gòu)造函數(shù)的總結(jié)詳解
深拷貝和淺拷貝可以簡單理解為：如果一個類擁有資源，當這個類的對象發(fā)生復制過程的時候，資源重新分配，這個過程就是深拷貝，反之，沒有重新分配資源，就是淺拷貝2013-09-09
這篇文章主要介紹了vscode+leetcode環(huán)境配置，本文通過實例圖文相結(jié)合給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-03-03
本文主要介紹了C++ sort排序函數(shù)用法詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-06-06
本文主要介紹了Qt中暫停程序的幾種方法小結(jié),包含了4種方式,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-07-07
這篇文章主要介紹了C++的四種類型轉(zhuǎn)換，有詳細的示例代碼展示，對于學習C++的同學有一定的參考價值，感興趣的同學可以參考本文2023-04-04
本文主要介紹了QT5?Thread線程，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-05-05