排序算法（3）--插入排序（插入、希尔）

一、直接插入排序（insertion sort）
       原理：直接插入排序是一种非常简单直观的排序方法，其主要原理是构建有序序列，从后向前扫描将未排序序列元素依次插入到有序序列中。即给定序列A[1...n]，假设有序序列A[1...i]，将A[i+1]元素插入到A[1...i]中，有序序列个数增加，依次循环知道A[n]元素插入到有序序列中，排序完成。
       代码实现：

/************************************************************************/
/* 直接插入排序 */
/************************************************************************/
void SelectionSort(int *a, int size)
{
    int i = 0, j = 0;
    int tmp = 0;

    for (i = 1; i < size; i++)
    {
        tmp = a[i];

        for(j = i - 1; j >= 0; j--)
        {
            if(tmp < a[j])
                a[j + 1] = a[j];
            else break;
        }

        a[j + 1] = tmp;
    }
}

        性能分析：从算法原理和代码实现可以轻松的看出，直接插入排序的比较时间和数据交换时间跟序列的有序性有直接关系。在最好情况下，即序列是正序的，比较和赋值的次数是O(1)，时间复杂度是O(n)；在最坏情况下，即序列是逆序，比较和赋值的次数是n(n-1)/2；所以平均时间复杂度是O(n^2)。由此可以看出，直接插入排序适合数据量少，序列基本有序的情况下。
二、二分查找插入排序（binary insertion sort）
       原理：在直接插入排序中，将元素插入到有序序列中，采用的是从后向前遍历查找出插入位置，如果查找操作比交换操作代价大的话，是否可以减少查找时间呢？答案是肯定的，由于插入到的是有序序列，在查找位置的时候使用二分法查找，效率会更高。二分查找插入排序与直接插入排序算法类似，只不过在确定插入位置时采用了二分法查找。
       代码实现：

/************************************************************************/
/* 二分查找(若没找到，返回大于key值的最小元素的位置) */
/************************************************************************/
int binarySearch(int *a, int low, int high, int key)
{
    int mid = (low + high) / 2;

    if(low > high)
        return low;

    if(a[mid] == key)
        return mid;
    else if(a[mid] < key)
        return binarySearch(a, mid + 1, high, key);
    else
        return binarySearch(a, low, mid - 1, key);
}
/************************************************************************/
/* 二分查找排序 */
/************************************************************************/
void binaryInsertSort(int *a, int size)
{
    int i = 0, j = 0, site = 0;
    int tmp = 0;

    for(i = 1; i < size; i++)
    {
        // 二分查找插入位置
        site = binarySearch(a, 0, i - 1, a[i]);

        tmp = a[i];

        // 将有序数组进行移位
        for(j = i; j > site; j--)
            a[j] = a[j - 1];

        // 插入数据
        a[site] = tmp;
    }
}

       性能分析：二分查找插入排序，是直接插入排序的一个变种。这种排序方法只是减少了比较次数，并没有减少数据交换次数，所以平均时间复杂度与最坏情况时间复杂度与直接插入排序一样；但是最佳情况下，由于二分查找消耗了多的时间，所以此时直接插入排序由于二分查找插入排序。由此可以看出，数据量小且基本有序时，直接插入排序更合适；数据量大时，二分查找插入排序由于直接插入排序。
三、希尔排序（shell port）
        原理：希尔排序是直接插入排序的一种改进。也叫缩小增量排序。由于直接插入排序在数据量小、基本有序的条件下排序效率高，所以鉴于此衍生了希尔排序。他的基本思想是分组插入排序，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2                 一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
       代码实现：

/************************************************************************/
/* 增量为dl的一趟插入排序 */
/************************************************************************/
void ShellInsert(int *a, int dl, int size)
{
    int i = 0, j = 0, tmp = 0;

    for(i = dl; i < size; i += dl)
    {
        tmp = a[i];

        for(j = i - dl; j >= 0; j -= dl)
        {
            if(a[j] > tmp)
                a[j + dl] = a[j];
            else break;
        }

        a[j + dl] = tmp;
    }
}
/************************************************************************/
/* 希尔排序 */
/************************************************************************/
void ShellSort(int *a, int size)
{
    int dl = size / 2;

    while(dl >= 1)
    {
        ShellInsert(a, dl, size);
        dl /= 2;
    }
}

       性能分析：希尔排序是直接插入排序的改进，增加了执行效率。希尔排序的时间复杂度与增量序列的选取有关，但是没有快速排序算法（O(n(logn))）快，所以中等大小规模数据表现良好，对规模非常大的数据排序不是最优选择。希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差，而且希尔排序代码简单，易于实现。专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。