数据结构排序系列之插入排序（一）

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总结