直接插入排序——监视哨的作用

直接插入排序

从前往后依次将每一个元素插入到前面已排好的序列中，如当插入到arr[i]时，arr[0]至arr[i-1]已排好序了，将arr[i]与arr[0],arr[2],arr[2],…arr[i-1]依次比较，直到找到正确的插入位置，当把最后一个元素插入完成时，排序结束。

现在我们有这样一个序列：

我们可以将它拆开成两部分，arr[0]是已排好序的，之后全部是未排序的：

首先从arr[1]开始（i=1时），我们将arr[1]插入到前面已排好的序列arr[0]~arr[0]中（即arr[0]~arr[i-1]），让arr[1]依次与已排好的序列中每个元素比较，找比6大的元素，没找到，插入到末尾。

然后接着下一个，当i=2时，将arr[2]插入到前面已排好的序列arr[0]~arr[1]中（即arr[0]~arr[i-1]），让arr[2]依次与已排好的序列中每个元素比较，找比5大的，最后找到6，将5插入到6的位置，6及6以后已排序元素依次后移。

i依次增大，每一步将arr[i]插入到arr[0]~arr[i-1]中，直到i等于元素总个数，说明已全部排序完成，退出循环。

代码如下：

void insert_sort(int arr[],int lengthgh)
{
    int i ,j,k;
    for( i = 1 ; i<length ; i++){//从下标1处开始

        //找到arr[i]插入的位置
        for( j = 0; j<i ;j++){
            if(arr[i]<arr[j])
                break;
        }   
         //如果i==j，说明arr[i]大于前面所有已排序的元素，应该插
         //入到最末尾，也就是arr[i]自己的位置上,所以不需要处理

        if( i != j){ 

        int key = arr[i];//保存待插入元素

        //将插入位置之后所有已排序元素后移一位
            for( k = i ; k > j ; k--)
                arr[k] = arr[k-1];

            //插入待排序元素
            arr[j] = key;
        }
    }
}

这种方式，我们i元素插入到前面有三步：
1. 从前往后依次查找插入位置
2. 将插入位置之后i之前元素全部往后移一格
3. 插入指定元素

这种方式第一次查找插入位置的时候需要将这些元素遍历一遍，移动的时候又得遍历一遍，进行了重复的运算，如果第一步寻找插入位置时，我们从后往前寻找插入位置的话，第一步和第二步就可以一起进行：

1. 从i-1出向前遍历，如果该元素大于此次要插入的元素，往后移动一格，直到找到一个不大于的或到达arr[0]处
2. 插入指定元素

代码：

void insert_sort(int arr[],int length)
{
    int i,j;
    for( i=0 ; i< length; i++){
        int key = arr[i];//将待插入的元素保存起来
        for( j=i-1 ; j>=0; j--){
            if( arr[j]>key)//从后往前将所有大于key的元素往后移一格
                arr[j+1] = arr[j];
            else
                break;
            }   
            arr[j+1] = key;
            //函数运行到此处有两种情况：
            //1，j指向从后往前第一个小于或等于key的元素，只需将key
            //插入到此元素后即j+1处即可
            //2，已排序序列中没有比key大的元素，已被全部往后移动一格，
            //此时i指向-1，将key插入到arr[0]处刚好也是j+1处 
        }
}

做到这里，我本以为这个函数已经搞定了，然后查了些资料，对比了一下自己的代码，发现有很多提到了“监视哨”，然后研究了一下。

监视哨的作用

传进来的那个数组arr，arr[0]中不存储有用的元素，所有的数据存在arr[1]~arr[length]中（传入函数的length值我们规定为有用的元素个数，最后一个元素就是arr[length]）,arr[0]就是监视哨，有两个作用：

第一个作用是用来存储每次待插入的元素，作用和上面那个函数中设置的变量key一样，监视哨要是只有这么一个作用的话，我们为什么要舍弃创建一个临时变量这么简单的办法不用而去用它呢，所以我仔细研究了一下监视哨的第二个作用。

解释第二个作用之前，我们先看一下我们之前写的一段代码：

注意for循环的判定部分，如果将待插入元素存储在arr[0]中，可以省掉这个这个判断条件。
将判断部分改成这样：

for( j=i-1; arr[j]>arr[0]; j--)

然后在循环体内，就不需要任何判断，只用把该元素往后移动一格即可
那么当这个循环体结束时有两种情况，第一种是遇见了第一个不大于arr[0]的元素，此时只要将arr[0]的值赋给arr[j+1]就可以了。
第二种情况是所有元素都不大于arr[0]，j会一直减到0退出，此时只需要把arr[0]赋给arr[1]就好了，arr[1]刚好也是arr[j+1],
所以这部分代码是这样的：

for( j=i-1; arr[j]>arr[0]; j--)
    arr[j+1] = arr[j];
arr[j+1] = arr[0];

我们比较两段代码：

发现设置监视哨确实可以省略判断j>=0这一步，可不要小看了这一步，一次循环少判断一次，n次循环就少判断n次，当要排序的元素数量极其庞大时，提高的效率就十分可观了。

设置监视哨的函数代码：

void insert_sort( int arr[], int length)
{
    int i,j;
    for(i=2; i<=length; i++){
        arr[0] = arr[i];//将待插入元素存放到监视哨中
        for(j=i-1; arr[j]>arr[0]; j--)
            arr[j+1] = arr[j];//将大于待插入元素的全部向后移一个
        arr[j+1] = arr[0];//插入待插入元素
    }   
}