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

更新時間：2014年04月29日 09:37:42 作者：

c語言實現(xiàn)插入排序、冒泡排序、選擇排序、快速排序、堆排序、歸并排序、希爾排序示例,需要的朋友可以參考下

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

復制代碼代碼如下:

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)

冒泡排序算法的運作如下：
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
針對所有的元素重復以上的步驟，除了最后一個。
持續(xù)每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

復制代碼代碼如下:

#include<stdio.h>
#defineSIZE8
void bublle_sort(int a[],int n){//n為數組a的元素個數
    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]){//數組元素大小按升序排列
             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是整形數組，numsize是元素個數
     int i=0,j=numsize-1;
     int val=a[0];//指定參考值val大小
     if(numsize>1){//確保數組長度至少為2，否則無需排序
         while(i<j{//循環(huán)結束條件
            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中的數放到a[i]中
         QuickSort(a,i);//遞歸，對前i個數排序
         QuickSort(a+i+1,numsize-1-i);//對i+1到numsize這numsize-1-i個數排序
    }
}

5. 堆排序 O(n log n)
n個關鍵字序列Kl，K2，…，Kn稱為（Heap），當且僅當該序列滿足如下性質（簡稱為堆性質）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），當然，這是小根堆，大根堆則換成>=號。//k(i）相當于二叉樹的非葉子結點，K(2i）則是左子節(jié)點，k(2i+1）是右子節(jié)點.
若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹:樹中任一非葉子結點的關鍵字均不大于（或不小于）其左右孩子（若存在）結點的關鍵字。

復制代碼代碼如下:

// array是待調整的堆數組，i是待調整的數組元素的位置，nlength是數組的長度
//本函數功能是：根據數組array構建大根堆
void HeapAdjust(int array[], int i, int nLength)
{
    int nChild;
    int nTemp;
    for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
    {
        // 子結點的位置=2*（父結點位置）+ 1
        nChild = 2 * i + 1;
        // 得到子結點中較大的結點
        if ( nChild < nLength-1 && array[nChild + 1] > array[nChild])
            ++nChild;
        // 如果較大的子結點大于父結點那么把較大的子結點往上移動，替換它的父結點
        if (nTemp < array[nChild])
        {
            array[i] = array[nChild];
            array[nChild]= nTemp;
        }
        else
        // 否則退出循環(huán)
            break;
    }
}

// 堆排序算法
void HeapSort(int array[],int length)
{  
    int tmp;
    // 調整序列的前半部分元素，調整完之后第一個元素是序列的最大的元素
    //length/2-1是第一個非葉節(jié)點，此處"/"為整除
    for (int i = floor(length -1)/ 2 ; i >= 0; --i)
        HeapAdjust(array, i, length);
    // 從最后一個元素開始對序列進行調整，不斷的縮小調整的范圍直到第一個元素
    for (int i = length - 1; i > 0; --i)
    {
        // 把第一個元素和當前的最后一個元素交換，
        // 保證當前的最后一個位置的元素都是在現(xiàn)在的這個序列之中最大的
      ///  Swap(&array[0], &array[i]);
          tmp = array[i];
          array[i] = array[0];
          array[0] = tmp;
        // 不斷縮小調整heap的范圍，每一次調整完畢保證第一個元素是當前序列的最大值
        HeapAdjust(array, 0, i);
    }
}

6.歸并排序 O(n log n)

將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

復制代碼代碼如下:

//歸并操作
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+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);
    }
}

//調用
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）
先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。

復制代碼代碼如下:

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

您可能感興趣的文章: