資料結構排序系列之插入排序（一）

1.插入排序

插入排序我們介紹直接插入排序和希爾排序（縮小增量排序）。基本思想：每次将一個待排序的元素按其關鍵字的大小插入到前面已排好序的檔案的适當位置中，直到所有的元素插入完為止。

1.1.直接插入排序

算法思想：

假設要排序的元素存儲到一個數組R，在排序過程中，将數組分成：有序區R[0…i-1]，初始時有序區中有數組的第一個元素R[0]；無序區R[i…n]。每次排序時，從無序區取出第一個元素按其關鍵字大小插入到有序區的适當位置。經過n-1次就可以完成排序。

算法實作：

#include <stdio.h>

// n為數組長度
void insertSort(int R[],int n){

  int count=0;
  int move = 0;
  // R[i..n] 無序區  
  for(int i=1;i<n;i++){
    int temp = R[i]; // 從無序區取出第一個元素出來插入到有序區中
    // R[0..i-1] 有序區
    if(temp >= R[i-1]){
      count++;
            continue;} // 直接插入到有序區最後

    // 插入到有序區的适當位置
    int insertPosition=0;
    // 找到适當的插入位置
    for(int j=i-1; j >= 0;j--){
      count++;
      if(temp < R[j]){
        R[j+1] = R[j];
        insertPosition = j;
        move++;
      }else{
        break;
      }
    }
    // 将元素插入到适當位置
    R[insertPosition] = temp;

  }
  printf("count:%d\n,move:%d\n",count,move);
}

int main(){
  //int data[] = {46,39,17,23,28,55,18,46};
  int data[] = {36,25,48,27,65,25,43,58.76,32};
  for(int i=0;i < 10 ; i++){
         printf("%d ",data[i]);
  }
  printf("\n");  
  insertSort(data,10);
  for(int j =0;j < 10;j++){
          
         printf("%d ",data[j]);
  }
  printf("\n");
  return 0;
}      

1.2.希爾排序

算法思想：

假定待排序數組R，一開始選取一個小于數組長度n的增量d1，将數組分成d1個分組，所有下标距離為d1的倍數的元素放在同一個分組内，即第一組為R[1]，R[1+d]，R[1+2d]，R[1+3d],…，第二組為R[2]，R[2+d]，R[2+2d]，R[2+3d],…，依次類推。然後對每個分組進行直接插入排序。再選取d2作為第二個增量，重複上述操作。直到選取的增量dt=1(dt < dt-1<…<d2<d1)把所有的元素放在同一組中進行直接插入排序。

算法實作：

#include <stdio.h>

void shellInsert(int R[],int d,int n){
  int count=0;// 總比較次數
  int move = 0;// 總移動次數
  // R是待排序的數組,d是增量，n是數組長度
  if(d >= n) return; // 所取增量d要小于n 
  // 将數組R分成d個分級
  for(int i = 0; i < d; i++){
    
    // 對每個分組進行直接插入排序

    // 無序區 [i+xd..] x倍d
    for(int j = i+d; j < n; j += d){

      // 從無序區取出一個元素
      int temp = R[j];
      // 直接插入到有序區最後
      if(temp >= R[j-d]){
        count++;
        continue;
      }
      // 插入位置
      int insertPosition = 0;
      // 有序區[i..i+xd-d]
      for(int k = j-d; k >= i; k -= d){
        count++;
        if(temp < R[k]){
          R[k+d] = R[k];
          insertPosition = k;
          move++;
        }else{
          break;
        }
      }
      // 插入元素
      R[insertPosition] = temp;
    }
  }
  printf("count:%d\n,move:%d\n",count,move);

}

int main(){
  int R[] = {36,25,48,27,65,25,43,58,76,32};
  shellInsert(R,5,10);// 選取增量5
  shellInsert(R,3,10);// 選取增量3
  shellInsert(R,1,10);// 選取增量1
  for(int i = 0; i < 10; i ++ ){
    printf("%d ",R[i]);
  }
  printf("\n");
  return 0;
}      

上面的算法中，一個分組排完序，再到下一個分組，我們稍微變化一下，不再是一次性把一個分組排好序再到下一個，由于分組排序中，上一個分組的元素的下一個元素，在數組中的位置就是下一個分組的元素，我們根據這種特點可以“同時”一起排序：

#include <stdio.h>

// R是待排序的數組，n是數組長度，d是分組增量
void shellInsert(int R[],int n,int d){

   // d個分組同時輪流排序
   // 因為數組從0開始，是以R[0]元素下标加上增量d後的元素是R[d]
   // 如果我們的數組從1開始，那麼加增量距離後的元素是R[d+1]
   for(int i = d;i < n; i++){
      // 如果後面的元素比前面的元素要小就調整一個位置
      if(R[i] < R[i-d]){
         // 待排序元素
         int temp = R[i];
         int j = i - d; // 記錄前面元素的位置
         // 找到适合R[i]插入的位置
         while(j >= 0 && temp < R[j]){
            // j >= 0 保證數組不越界
            // temp < R[j] 檢查是否需要調整位置

            //  将前面的元素往後挪
            R[j+d] = R[j];
            j = j - d; // 再向前一個位置
         }
         // 将R[i]插入到适當的位置
         R[j+d] = temp;

      }
   }
}
int main(){
   int data[] = {36,25,48,27,65,25,43,58,76,32};
   int k[] = {5,3,1};
   for(int i = 0;i < 3;i++){
      shellInsert(data,10,k[i]);
   }
   for(int i = 0 ; i < 10; i++){
      printf("%d ", data[i]);
   }
   printf("\n");
   return 0;
}      

1.3總結