c語(yǔ)言實(shí)現(xiàn)冒泡排序、希爾排序等多種算法示例
實(shí)現(xiàn)以下排序
插入排序O(n^2)
冒泡排序 O(n^2)
選擇排序 O(n^2)
快速排序 O(n log n)
堆排序 O(n log n)
歸并排序 O(n log n)
希爾排序 O(n^1.25)
1.插入排序 O(n^2)
一般來(lái)說(shuō)，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：
⒈ 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序
⒉ 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
⒊ 如果該元素（已排序）大于新元素，將該元素移到下一位置
⒋ 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 將新元素插入到下一位置中
⒍ 重復(fù)步驟2~5
如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來(lái)減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個(gè)變種，稱為二分查找排序。
void insert_sort(int* array,unsignedint n){
int i,j;
int temp;
for(i=1;i<n;i++){
temp=*(array+i);
for(j=i;j>0&&*(array+j-1)>temp;j--){
*(array+j)=*(array+j-1);
}
*(array+j)=temp;
}
}
2.冒泡排序 O(n^2)
冒泡排序算法的運(yùn)作如下：
比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
#include<stdio.h>
#defineSIZE8
void bublle_sort(int a[],int n){//n為數(shù)組a的元素個(gè)數(shù)
int i,j,temp;
for(j=0;j<n-1;j++)
for(i=0;i<n-1-j;i++)
if(a[i]>a[i+1]){//數(shù)組元素大小按升序排列
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
int main(){
int number[SIZE]={95,45,15,78,84,51,24,12};
int i;
bublle_sort(number,SIZE);
for(i=0;i<SIZE;i++){
printf("%d",number[i]);
}
printf("\n");
}
3.選擇排序 O(n^2)
void select_sort(int * a, int n){
register int i, j, min, t;
for( i =0; i < n -1; i ++) {
min = i; //查找最小值
for( j = i +1; j < n; j ++)
if( a[min] > a[j])
min = j; //交換
if(min != i) {
t = a[min];
a[min] = a[i];
a[i] = t;
}
}
}
4.快速排序 O(n log n)
void QuickSort(int a[],int numsize){//a是整形數(shù)組，numsize是元素個(gè)數(shù)
int i=0,j=numsize-1;
int val=a[0];//指定參考值val大小
if(numsize>1){//確保數(shù)組長(zhǎng)度至少為2，否則無(wú)需排序
while(i<j{//循環(huán)結(jié)束條件
for(;j>i;j--)//從后向前搜索比val小的元素，找到后填到a[i]中并跳出循環(huán)
if(a[j]<val){
a[i]=a[j];break;
}
for(;i<j;i++)//從前往后搜索比val大的元素，找到后填到a[j]中并跳出循環(huán)
if(a[i]>val){
a[j]=a[i];break;
}
}
a[i]=val;//將保存在val中的數(shù)放到a[i]中
QuickSort(a,i);//遞歸，對(duì)前i個(gè)數(shù)排序
QuickSort(a+i+1,numsize-1-i);//對(duì)i+1到numsize這numsize-1-i個(gè)數(shù)排序
}
}
5. 堆排序 O(n log n)
n個(gè)關(guān)鍵字序列Kl，K2，…，Kn稱為（Heap），當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡(jiǎn)稱為堆性質(zhì)）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），當(dāng)然，這是小根堆，大根堆則換成>=號(hào)。//k(i）相當(dāng)于二叉樹(shù)的非葉子結(jié)點(diǎn)，K(2i）則是左子節(jié)點(diǎn)，k(2i+1）是右子節(jié)點(diǎn).
若將此序列所存儲(chǔ)的向量R[1..n]看做是一棵完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹(shù):樹(shù)中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均不大于（或不小于）其左右孩子（若存在）結(jié)點(diǎn)的關(guān)鍵字。
// array是待調(diào)整的堆數(shù)組，i是待調(diào)整的數(shù)組元素的位置，nlength是數(shù)組的長(zhǎng)度
//本函數(shù)功能是：根據(jù)數(shù)組array構(gòu)建大根堆
void HeapAdjust(int array[], int i, int nLength)
{
int nChild;
int nTemp;
for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
{
// 子結(jié)點(diǎn)的位置=2*（父結(jié)點(diǎn)位置）+ 1
nChild = 2 * i + 1;
// 得到子結(jié)點(diǎn)中較大的結(jié)點(diǎn)
if ( nChild < nLength-1 && array[nChild + 1] > array[nChild])
++nChild;
// 如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較大的子結(jié)點(diǎn)往上移動(dòng)，替換它的父結(jié)點(diǎn)
if (nTemp < array[nChild])
{
array[i] = array[nChild];
array[nChild]= nTemp;
}
else
// 否則退出循環(huán)
break;
}
}
// 堆排序算法
void HeapSort(int array[],int length)
{
int tmp;
// 調(diào)整序列的前半部分元素，調(diào)整完之后第一個(gè)元素是序列的最大的元素
//length/2-1是第一個(gè)非葉節(jié)點(diǎn)，此處"/"為整除
for (int i = floor(length -1)/ 2 ; i >= 0; --i)
HeapAdjust(array, i, length);
// 從最后一個(gè)元素開(kāi)始對(duì)序列進(jìn)行調(diào)整，不斷的縮小調(diào)整的范圍直到第一個(gè)元素
for (int i = length - 1; i > 0; --i)
{
// 把第一個(gè)元素和當(dāng)前的最后一個(gè)元素交換，
// 保證當(dāng)前的最后一個(gè)位置的元素都是在現(xiàn)在的這個(gè)序列之中最大的
/// Swap(&array[0], &array[i]);
tmp = array[i];
array[i] = array[0];
array[0] = tmp;
// 不斷縮小調(diào)整heap的范圍，每一次調(diào)整完畢保證第一個(gè)元素是當(dāng)前序列的最大值
HeapAdjust(array, 0, i);
}
}
6.歸并排序 O(n log n)
將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè) 有序表合并成一個(gè)有序表，稱為二路歸并。
//歸并操作
void Merge(int sourceArr[], int targetArr[], int startIndex, int midIndex, int endIndex)
{
int i, j, k;
for(i = midIndex+1, j = startIndex; startIndex <= midIndex && i <= endIndex; j++)
{
if(sourceArr[startIndex] < sourceArr[i])
{
targetArr[j] = sourceArr[startIndex++];
}
else
{
targetArr[j] = sourceArr[i++];
}
}
if(startIndex <= midIndex)
{
for(k = 0; k <= midIndex-startIndex; k++)
{
targetArr[j+k] = sourceArr[startIndex+k];
}
}
if(i <= endIndex)
{
for(k = 0; k <= endIndex- i; k++)
{
targetArr[j+k] = sourceArr[i+k];
}
}
}
//內(nèi)部使用遞歸，空間復(fù)雜度為n+logn
void MergeSort(int sourceArr[], int targetArr[], int startIndex, int endIndex)
{
int midIndex;
int tempArr[100]; //此處大小依需求更改
if(startIndex == endIndex)
{
targetArr[startIndex] = sourceArr[startIndex];
}
else
{
midIndex = (startIndex + endIndex)/2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(tempArr, targetArr,startIndex, midIndex, endIndex);
}
}
//調(diào)用
int _tmain(int argc, _TCHAR* argv[])
{
int a[8]={50,10,20,30,70,40,80,60};
int b[8];
MergeSort(a, b, 0, 7);
for(int i = 0; i < sizeof(a) / sizeof(*a); i++)
cout << b[i] << ' ';
cout << endl;
system("pause");
return 0;
}
7.希爾排序 O(n^1.25）
先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?BR>
void ShellSort(int a[], int n){
int d, i, j, temp;
for(d = n/2;d >= 1;d = d/2){
for(i = d; i < n;i++){
temp = a[i];
for(j = i - d;(j >= 0) && (a[j] > temp);j = j-d){
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
}
相關(guān)文章
這篇文章主要為大家介紹了socket編程之bind()函數(shù)使用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-10-10
這篇文章主要介紹了C++ 多態(tài)和虛函數(shù)的相關(guān)資料，文中示例代碼非常詳細(xì)，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-07-07
基于opencv實(shí)現(xiàn)視頻中的顏色識(shí)別功能
這篇文章主要介紹了基于opencv實(shí)現(xiàn)視頻中的顏色識(shí)別功能,文章詳細(xì)介紹了顏色識(shí)別的原理及opencv中的顏色模型，基于c++代碼實(shí)現(xiàn)顏色識(shí)別功能，需要的朋友可以參考下2022-07-07
C語(yǔ)言實(shí)現(xiàn)時(shí)間處理工具的示例代碼
這篇文章主要為大家詳細(xì)介紹了利用C語(yǔ)言實(shí)現(xiàn)時(shí)間處理工具的相關(guān)資料，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，需要的可以參考一下2022-09-09
Qt實(shí)現(xiàn)實(shí)時(shí)鼠標(biāo)繪制圖形
這篇文章主要介紹了Qt中QGraphicsView架構(gòu)下如何實(shí)現(xiàn)實(shí)時(shí)鼠標(biāo)繪制圖形，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起動(dòng)手試一試2022-02-02
VS2019開(kāi)發(fā)簡(jiǎn)單的C/C++動(dòng)態(tài)鏈接庫(kù)并進(jìn)行調(diào)用的實(shí)現(xiàn)
這篇文章主要介紹了VS2019開(kāi)發(fā)簡(jiǎn)單的C/C++動(dòng)態(tài)鏈接庫(kù)并進(jìn)行調(diào)用的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
C++實(shí)現(xiàn)多線程查找文件實(shí)例
這篇文章主要介紹了C++實(shí)現(xiàn)多線程查找文件實(shí)例,對(duì)于深入學(xué)習(xí)C++程序設(shè)計(jì)有著很好的參考借鑒價(jià)值,需要的朋友可以參考下2014-10-10
C++?Cartographer源碼中關(guān)于MapBuilder的聲明與構(gòu)造
這篇文章主要介紹了C++?Cartographer源碼中關(guān)于MapBuilder的聲明與構(gòu)造，前面已經(jīng)談到了Cartographer中添加軌跡的方法和傳感器的數(shù)據(jù)流動(dòng)走向。在添加軌跡的時(shí)候，除了添加位姿估計(jì)器還有采樣器，訂閱回調(diào)函數(shù)之外，最重要的是通過(guò)map_builder_bridge添加了一條軌跡2023-03-03
C 語(yǔ)言關(guān)于聯(lián)合體的相關(guān)知識(shí)
這篇文章主要介紹了C 語(yǔ)言關(guān)于聯(lián)合體的相關(guān)知識(shí)，文中講解非常細(xì)致，代碼幫助大家更好的理解學(xué)習(xí)，感興趣的朋友可以了解下2020-06-06
vscode實(shí)現(xiàn)本地代碼自動(dòng)同步到遠(yuǎn)程機(jī)器的步驟
這篇文章主要介紹了vscode實(shí)現(xiàn)本地代碼自動(dòng)同步到遠(yuǎn)程機(jī)器的步驟,本文分步驟給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-06-06