内部排序：插入排序和希尔排序的N种实现

内部排序：插入排序和希尔排序的N种实现2014-12-06前言

本来想将所有的内部排序总结为一篇博文，但是随着研究的深入，还是放弃了这个念头，斟前酌后，还是觉得分开来写比较好，具体原因，看完本篇博文也就自然明了了。

本篇文章主要探讨插入排序和希尔排序，之所将二者放在一起，很明显，是因为希尔排序是建立在插入排序的基础之上的。

注：以下各排序算法的N种实现方法大部分都是我根据算法思想，自己写出来的，或者是参考其本身的经典实现，我自己都已测试通过，但不敢保证一定都没问题，如果有疑问，欢迎指出。

插入排序

插入排序的思想很简单，它的基本操作就是将一个数据插入到已经排好序的序列中，从而得到一个新的有序序列。根据查找插入位置的实现思路不同，它又可以分为：直接插入排序、折半插入排序、2-路插入排序。。。这里，我们主要探讨下直接插入排序和折半插入排序。

直接插入排序

直接插入排序是最基本的插入排序方法，也是一种最简单的排序方法。其基本实现思想如下：

1、首先把第一个元素单独看做一个有序序列，依次将后面的元素插入到该有序序列中；

2、插入的时候，将该元素逐个与前面有序序列中的元素进行比较，找到合适的插入位置，形成新的有序序列；

3、当有序序列扩大为整个原始序列的大小时，排序结束。

第一种实现方法

按照该思想，我第一次写出来的实现代码如下：

/* 第一种代码形式 插入排序后的顺序为从小到大 */void Insert_Sort1（int *arr,int len）{int i;//从第1个元素开始循环执行插入排序for（i=1;i<len;i++） { //将第i个元素分别与前面的元素比较，插入适当的位置if（arr[i]<arr[i-1]）{ //一直向左进行比较，直到插入到适当的位置int key = arr[i];int count = 0;//用来记录key在与前面元素时向左移动的位置while（i>0 && key<arr[i-1]）{arr[i] = arr[i-1];arr[i-1] = key;i--;count++;}//将待插入的数定位到下一个元素，//因为后面还要执行i++，所以这里不再加1i += count;} }}

第二种实现方法

很明显，上面的代码有些冗杂，如果面试的时候让你手写插入排序的代码，很难一下子写出来。于是，我考虑将while循环去掉，直接在后面再来一个for循环，每次比较，遇到比自己大的就交换，直到遇到比自己小的，才退出for循环。这样代码改成了如下形式：

/* 第二种代码形式 插入排序后的顺序为从小到大 */void Insert_Sort2（int *arr,int len）{int i,j;for（i=1;i<len;i++）for（j=i-1;j>=0 && arr[j]>arr[j+1];j--）{//交换元素数值//由于arr[j]不等于arr[j+1]，//因此可以安全地用该交换方法arr[j]^=arr[j+1];arr[j+1]^=arr[j];arr[j]^=arr[j+1];}}

第三种实现方法

上面的代码要用到数据的交换，即每次要插入的元素要逐个地与前面比它大的元素互换位置，而数据交换需要三步赋值操作，我们完全可以避免进行如此多的操作（排序算法中一般都会尽量避免数据的交换操作），为了提高执行效率（虽然该执行效率的提高可能并没有那么显著），我们再回过头来看第一种实现方法，我们可以通过key变量先将待插入的数据保存起来，在比较时只将元素右移一位即可，最后再将key放到要插入的位置，这样可以减少两个赋值操作的执行时间。这样我们可以把代码改成如下实现形式：

/* 第三种代码形式 插入排序后的顺序为从小到大 */void Insert_Sort3（int *arr,int len）{int i,j;for（i=1;i<len;i++）if（arr[i] < arr[i-1]）{ //向前逐个比较，直到需要插入的地方int key = arr[i];for（j=i-1;j>=0 && arr[j]>key;j--）arr[j+1] = arr[j];arr[j+1] = key;//插入key}}

这也是最常见的实现形式，如果在面试中要手写插入排序的话，直接把这种实现代码写出来就可以了。

另外，很明显可以看出来，对于长度为n的待排序咧，直接插入排序的平均时间复杂度为O（n*n），而且直接插入排序的比较次数与原始序列的中各元素的位置密切相关，待排序的序列越接近于有序，需要比较的次数就越小，时间复杂度也就越小。

折半插入排序

直接插入排序算法简单，且容易实现，当待排序的长度n很小时，是一种很好的排序方法，尤其当原始序列接近有序时，效率更好。如果待排序的长度n很大，则不适宜采用直接排序。这时我们可以考虑对其做些改进，我们可以从减少比较和移动的次数入手，因此可以采用折半插入排序，其思想类似于折半查找，这里不再详细说明，直接给出实现代码：

/* 插入排序后的顺序为从小到大 */void BInsert_Sort（int *arr,int len）{int i;//从第1个元素开始循环执行插入排序for（i=1;i<len;i++） { int low =0;int high = i-1;int key = arr[i];//循环至要插入的两个点之间while（low<=high）{int mid = （low+high）/2; if（key<arr[mid]）high = mid-1;elselow = mid+1;}//循环结束后low=high+1，并且low位置即为key要插入的位置//从low到i的元素依次后移一位int j;for（j=i;j>low;j--）arr[j] = arr[j-1];//将key插入到low位置处arr[low] = key;}}

从代码中可以看出，折半插入排序所需附加的存储空间与直接插入排序相等，时间上来看，折半插入排序减少了比较的次数，但是元素的移动次数并没有减少。因此，折半插入排序的平均时间复杂度仍为O（n*n）。

希尔排序希尔排序（shell排序），又称缩小增量排序。上面我们提到，直接插入排序在原始序列越接近有序的情况下，排序效率越高，希尔排序正是利用了直接插入排序的这个优势。希尔排序的基本思想如下：

它将序列按照某个增量间隔分为几个子序列，分别对子序列进行插入排序，而后再取另一增量间隔，对划分的子序列进行插入排序，依次往后。。。待序列已经大致有序，最后再对整个序列进行插入排序（即增量间隔为1），从而得到有序序列。

本文的重点放在排序算法的各种代码实现上，因此不再对具体的实现思想做过多的阐述，读者可以查阅相关资料或书籍来熟悉希尔排序的具体思想。由于希尔排序要用到插入排序，因此，我们依次根据上面基本插入排序的三种不同实现方法来书写希尔排序的代码。

第一种实现方法

仔细分析希尔排序的实现思想，会发现，如果要循环对各个子序列依次进行插入排序，我们需要在直接插入排序代码的外面再加一层for循环，用来循环所有的子序列。我们根据插入排序的第一种实现方法写出的代码如下：

/* 第一种形式的代码 对长为len的数组进行一趟增量为ader的插入排序 本算法在插入排序算法的第一种实现形式上进行修改得到 */void Shell_Insert1（int *arr,int len,int ader）{int i,k;//循环对ader个子序列进行插入排序操作for（k=0;k<ader;k++）for（i=ader+k;i<len;i+=ader）//对一个子序列进行插入排序操作{ //将第i个元素分别与前面的每隔ader个位置的元素比较，插入适当的位置if（arr[i]<arr[i-ader]）{ //一直向左进行比较，直到插入到适当的位置int key = arr[i];int count = 0;//用来记录key在与前面元素比较时向左移动了几个ader长度while（i>k && key<arr[i-ader]）{arr[i] = arr[i-ader];arr[i-ader] = key;i -= ader;count++;}//将待插入的数定位到下一个元素，执行下一次插入排序//因为后面还要执行i+=ader，所以这里回到原位置即可i += count*ader;} }}

第二种实现方法