简单插入排序和希尔排序(原理和C语言实现)

浏览数：21 / 时间：2015年06月08日

简单插入排序的原理很简单:

　　所谓插入排序，就是将新加入的数据插入到一个有序数组中，并且保证插入后有序。这就要求要找到插入的位置。

（图片来自维基百科）

对于一个已经存在的数组（乱序），要将其有序排列（这里取从小到大），就可以按照下面的步骤：

　　1.先假定一个有序数组，这个数组只有一个元素，就是第一个元素，它一定是有序的;

　　2.我们从第二个数（下标为1）开始向后遍历数组;

　　　　for(insert_index=1; insert_index < arr_len; insert_index++){

　　　　}

　　3.找到第二个数应该插入的位置，然后insert_index继续向后遍历;

　　　　问题来啦：怎么找到应该插入的位置？

　　　　　　insert_position从insert_index前面一个位置向前遍历（注意不要越界，它的范围是>=0的），直到找到比arr[insert_index]小的数，

　　　　　　此时position不再变化并且指向这个值。　　　　

　　　　　　注意，实际上插入的位置应该是insert_position之后的那个位置。

　　　　　　for(insert_pos=insert_index-1; insert_pos>=0; insert_pos--){

}

　　4.找到position后，要判断找到的这个位置是不是连续的，如果是连续的，就没有必要插入;

　　　　e.g. 34 45 56

pos insert_index

　　　　　　pos指向insert_index前一个位置，此时不用做插入操作。

　　　　　　if(insert_pos+1 != insert_index)...　　

　　5.先将这个insert_index所指向的值保存，temp=insert_index，然后数组依次后移;

　　　　int temp = arr[insert_index];

　　　　for(index=insert_index-1; index > insert_pos; insert_index--){

　　　　　　arr[index+1]=arr[index];

　　　　}

　　6.后移完成，此时将insert_index的值插入;

　　　　arr[insert_pos + 1] = temp; //还记得吗？是要插入到pos后面的; 此时的index是等于insert_pos的

好此时我们整理一下：

要用到的变量：insert_index insert_pos index 数组 arr 长度arr_len

 1 for(insert_index=1;insert_index<arr_len;insert_index++){                                                                            
 2      //查找insert_pos  从insert_index前一个位置开始向前遍历
 3      for(insert_pos=insert_index-1;insert_pos>=0;insert_pos--){
 4          //如果insert_pos<insert_index  查找成功
 5          if(arr[insert_pos]<arr[insert_index]){
 6              break;
 7          }
 8      }
 9  }
10  
11  //已经找到插入位置，将数组后移
12  if(insert_pos+1!=insert_index){//判断是否是连续的  如果是连续的不需要做插入操作;
13      //将insert_index 暂存
14      temp=arr[insert_index];
15      //遍历后移
16      for(index=insert_index-1;index>insert_pos;index--){
17          arr[index+1]=arr[index];
18      }
19      arr[insert_pos+1]=temp;//放置在pos的后面
20  }

知道原理后，就可以将上述代码简化：

上述代码是先找到插入位置，然后再将数组后移

我们可以在遍历时判断交换直至到达插入位置

 1  void sort(int *arr, int arr_len)
 2  {
 3      int i,j;
 4      for(i=1;i<arr_len;i++){
 5          j=i-1;
 6          temp=a[i];
 7          while(j>=0&&arr[j]>temp){
 8              arr[j+1]=arr[j];
 9              j=j-1;
10          }
11          arr[j+1]=temp;
12      }
13   }

这种方法就可以直接拿来转换成希尔排序;

所谓的希尔排序，就是对其设定步长，而不是每个都交换判断

（图片来自维基百科）

 1 void shell(int *arr, int arr_len)
 2 {
 3     int i,j;
 4     int gap=0;
 5     int tamp;
 6     while(gap<=arr_len){
 7         gap=3*gap+1;
 8     }
 9     while(gap>0){
10         for(i=gap;i<arr_len;i++){
11             j=i-gap;
12             temp=arr[i];
13             while(j>=0&&arr[j]>temp){
14                 arr[j+gap]=arr[j];
15                 j=j-gap;
16             }
17             arr[j+gap]=temp;
18         }
19         gap=(gap-1)/3;
20     }
21 }