首页 > 代码库 > 简单插入排序和希尔排序(原理和C语言实现)
简单插入排序和希尔排序(原理和C语言实现)
简单插入排序的原理很简单:
所谓插入排序，就是将新加入的数据插入到一个有序数组中，并且保证插入后有序。这就要求要找到插入的位置。
（图片来自维基百科）
对于一个已经存在的数组（乱序），要将其有序排列（这里取从小到大），就可以按照下面的步骤：
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 }
简单插入排序和希尔排序(原理和C语言实现)