c語言實(shí)現(xiàn)冒泡排序、希爾排序等多種算法示例

來源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語言|點(diǎ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)

一般來說，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：
⒈ 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
⒉ 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
⒊ 如果該元素（已排序）大于新元素，將該元素移到下一位置
⒋ 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 將新元素插入到下一位置中
⒍ 重復(fù)步驟2~5
如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個(gè)變種，稱為二分查找排序。

復(fù)制代碼代碼如下:

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è)。
對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

復(fù)制代碼代碼如下:

#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)

復(fù)制代碼代碼如下:

  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)

復(fù)制代碼代碼如下:

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ù)組長度至少為2，否則無需排序
         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);//遞歸，對前i個(gè)數(shù)排序
         QuickSort(a+i+1,numsize-1-i);//對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ì)（簡稱為堆性質(zhì)）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），當(dāng)然，這是小根堆，大根堆則換成>=號。//k(i）相當(dāng)于二叉樹的非葉子結(jié)點(diǎn)，K(2i）則是左子節(jié)點(diǎn)，k(2i+1）是右子節(jié)點(diǎn).
若將此序列所存儲(chǔ)的向量R[1..n]看做是一棵完全二叉樹的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹:樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均不大于（或不小于）其左右孩子（若存在）結(jié)點(diǎn)的關(guān)鍵字。

復(fù)制代碼代碼如下:

// array是待調(diào)整的堆數(shù)組，i是待調(diào)整的數(shù)組元素的位置，nlength是數(shù)組的長度
//本函數(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è)元素開始對序列進(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è)有序表，稱為二路歸并。

復(fù)制代碼代碼如下:

//歸并操作
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>

復(fù)制代碼代碼如下:

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;
       }
    }
}