1.插入排序

插入排序（Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。
時間復(fù)雜度:O(n^2);

算法描述：

1.從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序
2.取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
3.如果該元素（已排序）大于新元素，將該元素移到下一位置
4.重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
5.將新元素插入到該位置后
6.重復(fù)步驟2~5

動畫演示：

作者：Swfung8

算法演示：

/*
**直接插入排序
*/
void InsertSort(int a[], int len)
{
  int i, j, key;
  for(i = 1; i < len; ++i){
    key = a[i];
    for(j = i-1; j >=0; --j){
      if(a[j] > key)
        a[j+1] = a[j];
      else
        break;
    }
    a[j+1] = key;
  }
} 

2.折半插入排序

折半插入排序（binary insertion sort）是對插入排序算法的一種改進(jìn)，所謂排序算法過程，就是不斷的依次將元素插入前面已排好序的序列中。時間復(fù)雜度O(n^2);

算法描述：

在將一個新元素插入已排好序的數(shù)組的過程中，尋找插入點(diǎn)時，將待插入?yún)^(qū)域的首元素設(shè)置為a[low]，末元素設(shè)置為a[high]，則輪比較時將待插入元素與a[m]，其中m=(low+high)/2相比較,如果比參考元素大，則選擇a[low]到a[m-1]為新的插入?yún)^(qū)域(即high=m-1)，否則選擇a[m+1]到a[high]為新的插入?yún)^(qū)域（即low=m+1），如此直至low<=high不成立，即將此位置之后所有元素后移一位，并將新元素插入a[high+1]

算法演示：

/*
**折半插入排序
*/
void BinsertSort(int a[], int len)
{
  int i, j;
  int low, high, mid;
  int key;
  for(i = 1; i < len; i++){
    key = a[i];
    low = 1; high = i-1;
    while (low <= high){
      mid = (low+high)/2;
      if(key < a[mid])
        high = mid-1;
      else
        low = mid+1;
    }
    for(j = i-1; j >=high+1; --j)
      a[j+1] = a[j];
    a[high+1] = key;
  }
}

3.希爾排序

希爾排序，也稱為遞減增量排序算法,是插入排序的一種高效的改進(jìn)版本。
希爾排序是一種穩(wěn)定的排序算法，時間復(fù)雜度為O(n^3/2);
希爾算法是基于插入排序的一下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
*插入排序在對幾乎已經(jīng)排好的數(shù)據(jù)操作時，效率高，即可達(dá)到線性排序的效率；
*但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動一位；

算法描述：

1.先取一個正整數(shù) d1(d1 < n)，把全部記錄分成 d1 個組，所有距離為 d1 的倍數(shù)的記錄看成一組，然后在各組內(nèi)進(jìn)行插入排序
2.然后取 d2(d2 < d1)
3.重復(fù)上述分組和排序操作；直到取 di = 1(i >= 1) 位置，即所有記錄成為一個組，最后對這個組進(jìn)行插入排序。一般選 d1 約為 n/2，d2 為 d1 /2， d3 為 d2/2 ，…， di = 1。

動畫演示：

1.假設(shè)有數(shù)組 a = [80, 93, 60, 12, 42, 30, 68, 85, 10]，首先取 d1 = 4，將數(shù)組分為 4 組，如下圖中相同顏色代表一組：

2.然后分別對 4 個小組進(jìn)行插入排序，排序后的結(jié)果為：

3.然后，取 d2 = 2，將原數(shù)組分為 2 小組，如下圖：

4.然后分別對 2 個小組進(jìn)行插入排序，排序后的結(jié)果為：

5.最后，取 d3 = 1，進(jìn)行插入排序后得到最終結(jié)果：

算法演示：

/*
**希爾排序
*/
void ShellSort(int a[], int n)
{
  int i, j, gap;

  for(gap = n/2; gap>0; gap /= 2) //步長
    for(i = 0; i < gap; ++i){ 
      for(j = i+gap; j<n;j+=gap){
        if(a[j] < a[j-gap]){
          int temp = a[j];
          int k = j-gap;
          while(k>=0 && a[k] > temp){
            a[k+gap] = a[k];
            k -= gap;
          }
          a[k+gap] = temp;
        }
      }
    }
}

4.example code：

int main()
{
  int i;
  int a[] = {80, 93, 60, 12, 42, 30, 68, 85, 10};
  InsertSort(a, sizeof(a)/sizeof(a[0]));
  for(i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
    printf("%d ", a[i]);
  printf("\n");
  BinsertSort(a, sizeof(a)/sizeof(a[0]));
  for(i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
    printf("%d ", a[i]);
  printf("\n");
  ShellSort(a, sizeof(a)/sizeof(a[0]));
  for(i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
    printf("%d ", a[i]);
  printf("\n");
  return 0;
} 

最新評論