常用排序算法的C語言版實(shí)現(xiàn)示例整理
所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：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ù)來衡量?；镜呐判蛩惴ㄓ腥缦聨追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é)合起來，就可以盡量避免棧溢出。
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è)冒泡排序有問題，無法得到正確結(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賦值，可以將賦值語句移到循環(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ù)來進(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;
}
相關(guān)文章
Qt實(shí)現(xiàn)界面滑動(dòng)切換效果的思路詳解
這篇文章主要介紹了Qt實(shí)現(xiàn)界面滑動(dòng)切換效果,主要包括設(shè)計(jì)思路及主要函數(shù)講解，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-07-07
這篇文章主要給大家詳細(xì)介紹了c++如何實(shí)現(xiàn)堆棧及創(chuàng)建對(duì)象，文中先進(jìn)行了簡(jiǎn)單的介紹，而后給出了詳細(xì)的示例代碼及注釋，相信對(duì)大家的理解和學(xué)習(xí)很有幫助，有需要的朋友們下面跟著小編一起來學(xué)習(xí)學(xué)習(xí)吧。2016-12-12
關(guān)于C++讀入數(shù)字按位取出與進(jìn)制轉(zhuǎn)換問題(典型問題)
這篇文章主要介紹了關(guān)于C++讀入數(shù)字按位取出與進(jìn)制轉(zhuǎn)換問題,是一個(gè)非常典型的問題，本文通過實(shí)例舉例給大家介紹的非常詳細(xì)，需要的朋友可以參考下2020-02-02
怎么實(shí)現(xiàn)類的成員函數(shù)作為回調(diào)函數(shù)
不使用成員函數(shù)，為了訪問類的成員變量，可以使用友元操作符(friend)，在C++中將該函數(shù)說明為類的友元即可2013-10-10
下面小編就為大家?guī)硪黄猚++ 端口掃描程序?qū)崿F(xiàn)案例。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-05-05
這篇文章主要給大家介紹了關(guān)于C語言自定義類型的保姆級(jí)講解，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
typedef用法一共七種，分別是：為基本數(shù)據(jù)類型起別名、為結(jié)構(gòu)體起別名、為指針類型起別名、為數(shù)組類型起別名、為枚舉類型起別名、為模版函數(shù)起別名。本文就來分別講講這7個(gè)用法的具體實(shí)現(xiàn)吧2023-04-04
本篇文章是對(duì)C++字符串替換函數(shù)的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
基于c++11的event-driven library的理解
這篇文章主要介紹了基于c++11的event-driven library的理解，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02
C++實(shí)現(xiàn)LeetCode(172.求階乘末尾零的個(gè)數(shù))
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(172.求階乘末尾零的個(gè)數(shù)),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08