经典算法回顾之插入排序

　　插入排序的基本思想是：每次选择待排序的记录序列的第一个记录，按照排序值的大小将其插入到已排序的记录序列中的适当位置，直到所有记录全部排序完毕。

直接插入排序：

　　直接插入排序是一种最简单的排序方法，整个排序过程为：先将第一个记录看做一个有序记录序列，然后从第二个记录开始，依次将为排序的记录插入这个有序的记录序列中，直到整个文件中的全部记录排序完毕。

　　算法代码：

#include <iostream>
using namespace std;

template<typename T>
void DirectInsertSort(T unsorted[], int size)
{
    for(int i=1; i < size; ++i)
    {
        if(unsorted[i] < unsorted[i-1])//大于，无需操作；小于，需后移
        {
            int j = i-1;
            int temp = unsorted[i];//复制为哨兵，即存储为待排序元素
            while(j >= 0 && temp < unsorted[j])//查找在有序表中的插入位置
            {
                unsorted[j+1] = unsorted[j];//右移
                j--;
            }
            //找到位置，将temp插入
            unsorted[j+1] = temp;
        }
    }
}

int main(int argc, char *argv[])
{
    int data[] = {12,4,1,6,3,9,10};
    DirectInsertSort(data,7);
    for(int i=0;i<7;i++)
        cout << data[i] << " ";
    return 0;
}

希尔排序：

　　Shell排序的基本思想是：将整个序列分割为若干个子序列分别进行插入排序，然后改变分组，再进行插入；增量序列可为d={n/2, n/4, n/8, … , 1}。直接插入排序其实是d=1的希尔排序。

算法代码：

#include "stdafx.h"
#include <iostream>
using namespace std;

template<typename T>
void ShellInsert(T unsorted[], int size ,int dk)
{//dk为增量;与直接插入排序对比记忆
    for(int i = dk; i < size; ++i)
    {
        if(unsorted[i] < unsorted[i-dk])
        {
            int j = i - dk;
            int temp = unsorted[i];
            while(j >= 0 && temp < unsorted[j])
            {
                unsorted[j+dk] = unsorted[j];
                j -= dk;
            }
            unsorted[j+dk] = temp;
        }
    }
}

template<typename T>
void ShellSort(T unsorted[], int size)
{
    int dk = size/2;
    while(dk >=1)
    {
        ShellInsert(unsorted, size ,dk);
        dk = dk/2;
    }
}
int main(int argc, char *argv[])
{
    int data[] = {12,4,1,6,3,9,10};
    ShellSort(data,7);
    for(int i=0;i<7;i++)
        cout << data[i] << " ";
    return 0;
}