c語言排序算法總結

一.希爾（Shell）排序法

/* Shell 排序法 */

#include <stdio.h>

void sort(int v[],int n)

{

     int gap,i,j,temp;

     for(gap=n/2;gap>0;gap /= 2) /* 設定排序的步長，步長gap每次減半，直到減到1 */

     {

          for(i=gap;i<n;i++)  /* 定位到每一個元素 */

          {

               for(j=i-gap;(j >= 0) && (v[j] > v[j+gap]);j -= gap ) /* 比較相距gap遠的兩個元素的大小，根據排序方向決定如何調換 */

               {

                temp=v[j];

                v[j]=v[j+gap];

                v[j+gap]=temp;

               }

          }

     }

}

二.二分插入法

/* 二分插入法 */

void HalfInsertSort(int a[], int len)

     int i, j,temp;

     int low, high, mid;

     for (i=1; i<len; i++)

          temp = a[i];/* 儲存但前元素 */

          low = 0;

          high = i-1;

          while (low <= high) /* 在a[low...high]中折半查找有序插入的位置 */

               mid = (low + high) / 2; /* 找到中間元素 */

               if (a[mid] > temp)  /* 如果中間元素比但前元素大，目前元素要插入到中間元素的左側 */

                high = mid-1;

               else    /* 如果中間元素比目前元素小，但前元素要插入到中間元素的右側 */

                low = mid+1;

          }       /* 找到目前元素的位置，在low和high之間 */

          for (j=i-1; j>high; j--)/* 元素後移 */

           a[j+1] = a[j];

          }

          a[high+1] = temp; /* 插入 */

三.直接插入法

/*直接插入法*/

void InsertionSort(int input[],int len) 

     int i,j,temp;

     for (i = 1; i < len; i++) 

          temp = input[i];  /* 操作目前元素，先儲存在其它變量中 */

          for (j = i - 1;j>-1&&input[j] > temp ; j--) /* 從目前元素的上一個元素開始查找合适的位置 */

               input[j + 1] = input[j]; /* 一邊找一邊移動元素 */

               input[j] = temp;

四.帶哨兵的直接排序法

 /**

     * 帶哨兵的直接插入排序,數組的第一個元素不用于存儲有效資料

     * 将input[0]作為哨兵，可以避免判定input[j]中，數組是否越界

     * 因為在j--的過程中，當j減小到0時,變成了input[0]與input[0]

     * 自身進行比較，很明顯這個時候說明位置i之前的數字都比input[i]小

     * 位置i上的數字不需要移動，直接進入下一輪的插入比較。

     *

     */

void InsertionSortWithPiquet(int input[],int len) 

     int i,j;

     for (i = 2; i < len; i++)  /* 保證數組input第一進制素的存儲資料無效，從第二個資料開始與它前面的元素比較 */

          input[0] = input[i];

          for (j = i - 1; input[j] > input[0] ; j--) 

               input[j + 1] = input[j];

               input[j] = input[0]; /* input[j]一直都是排序的元素中最大的那一個 */

五.冒泡法

/* 冒泡排序法 */

void Bublesort(int a[],int n)

     int i,j,k;

     for(j=0;j<n;j++)   /* 氣泡法要排序n次*/

          for(i=0;i<n-j;i++)  /* 值比較大的元素沉下去後，隻把剩下的元素中的最大值再沉下去就可以啦 */

               if(a[i]>a[i+1])  /* 把值比較大的元素沉到底 */

                    k=a[i];

                    a[i]=a[i+1];

                    a[i+1]=k;

六.選擇排序法

/*算法原理：首先以一個元素為基準，從一個方向開始掃描，

 * 比如從左至右掃描，以A[0]為基準。接下來從A[0]...A[9]

 * 中找出最小的元素，将其與A[0]交換。然後将基準位置右

 * 移一位，重複上面的動作，比如，以A[1]為基準，找出

 * A[1]~A[9]中最小的，将其與A[1]交換。一直進行到基準位

 * 置移到數組最後一個元素時排序結束（此時基準左邊所有元素

 * 均遞增有序，而基準為最後一個元素，故完成排序）。

 */

void Selectsort(int A[],int n) 

     int i,j,min,temp; 

     for(i=0;i<n;i++) 

          min=i; 

          for(j=i+1;j<=n;j++)  /* 從j往前的資料都是排好的，是以從j開始往下找剩下的元素中最小的 */

               if(A[min]>A[j])  /* 把剩下元素中最小的那個放到A[i]中 */

                temp=A[i]; 

                A[i]=A[j]; 

                A[j]=temp;

    } 

七.快速排序

/* 快速排序（quick sort）。在這種方法中，

 * n 個元素被分成三段（組）：左段left，

 * 右段right和中段middle。中段

 * 僅包含一個元素。左段中各元素都小于等

 * 于中段元素，右段中各元素都大于等于中

 * 段元素。是以left和right中的元

 * 素可以獨立排序，并且不必對left和

 * right的排序結果進行合并。

 * 使用快速排序方法對a[0:n-1]排序

 * 從a[0:n-1]中選擇一個元素作為middle，

 * 該元素為支點把餘下的元素分割為兩段left

 * 和right，使得left中的元素都小于

 * 等于支點，而right 中的元素都大于等于支點

 * 遞歸地使用快速排序方法對left 進行排序

 * 遞歸地使用快速排序方法對right 進行排序

 * 所得結果為left+middle+right

void Quick_sort(int data[],int low,int high) 

 int mid; 

 if(low<high) 

 {

  mid=Partition(data,low,high); 

  Quick_sort(data,low,mid-1); /* 遞歸調用 */

  Quick_sort(data,mid+1,high);

 } 

/* 要注意看清楚下面的資料之間是如何替換的，

 * 首先選一個中間值，就是第一個元素data[low],

 * 然後從該元素的最右側開始找到比它小的元素，把

 * 該元素複制到它中間值原來的位置(data[low]=data[high])，

 * 然後從該元素的最左側開始找到比它大的元素，把

 * 該元素複制到上邊剛剛找到的那個元素的位置(data[high]=data[low])，

 * 最後将這個剛空出來的位置裝入中間值(data[low]=data[0])，

 * 這樣一來比mid大的都會跑到mid的右側，小于mid的會在左側，

 * 最後一行，傳回的low是中間元素的位置，左右分别遞歸就可以排好序了。

int Partition(int data[],int low,int high) 

    data[0]=data[low];

 mid=data[low]; 

 while(low < high) 

  while((low < high) && (data[high] >= mid))

  {

   --high;

  }

  data[low]=data[high]; /* 從high的位置開始往low的方向找，找到比data[low]小的元素，存到data[low]中 */

  while((low < high) && (data[low] < mid)) /* 新得到的data[low]肯定小于原來的data[low]即mid */

   ++low;

  data[high]=data[low];  /* 從low的位置開始往high的方向找，找到比data[high]大的元素，存在data[high]中 */

 }

 data[low]=data[0];    /* 把low的新位置存上原來的data[low]的資料 */

 return low;     /* 遞歸時，把它做為右側元素的low */

} 

八.堆排序

/**************************************************************

 * 堆的定義 n 個元素的序列 {k1,k2,...,kn}當且僅當滿足下列關系時，

 * 稱為堆:

 * ki<=k2i     ki<=k2i+1     (i=1,2,...,n/2)

 * 或

 * ki>=k2i     ki>=k2i+1     (i=1,2,...,n/2)

 * 堆排序思路：

 * 建立在樹形選擇排序基礎上；

 * 将待排序列建成堆（初始堆生成）後，序列的第一個元素（堆頂元素）就一定是序列中的最大元素；

 * 将其與序列的最後一個元素交換，将序列長度減一；

 * 再将序列建成堆（堆調整）後，堆頂元素仍是序列中的最大元素，再次将其與序列最後一個元素交換并縮短序列長度；

 * 反複此過程，直至序列長度為一，所得序列即為排序後結果。

 **************************************************************/

void HeapAdjust(int data[],int s,int m) /* 排列成堆的形式 */

{ 

     int j,rc; 

     rc=data[s];     /* 儲存處理元素 */

     for(j=2*s;j<=m;j*=2)        /* 處理父親元素 */

          if(j<m && data[j]<data[j+1])  ++j; /* 取較大的孩子節點 */

          if(rc>data[j]) break; 

          data[s]=data[j];   /* 父節點比較大的孩子節點大則互換 ,保證父節點比所有子節點都大（父節點存儲在前面）*/

          s=j; 

     } 

    data[s]=rc;     /* 相當于data[j]=rc */

void Heap_sort(int data[],int long_n) /* 堆排序函數 */

     int i,temp; 

     for(i=long_n/2;i>0;--i)  /* 還沒有讀懂這樣處理的原因，希望大家不吝賜教 */

      HeapAdjust(data,i,long_n); /* 處理後，data[i]是這個數組後半部分的最大值 */

     for(i=long_n;i>0;--i)

      temp=data[1];    /* 把根元素（剩下元素中最大的那個）放到結尾 ,下一次隻要排剩下的數就可以啦*/

      data[1]=data[i]; 

      data[i]=temp;   

      HeapAdjust(data,1,i-1);