04. 插入类排序（直接插入排序、折半插入排序、希尔排序

一 、插入类排序

基本思想：

在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。

插入排序有多种具体实现算法：

   （1）  直接插入排序

   （2）  折半插入排序

   （3）  表插入排序

   （4）  希尔排序

二、 直接插入排序

基本操作：将第i个记录插入到前面i-1个已排好序的记录中。

具体过程：将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1，Ki-2，…K1进行比较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将第i个记录插入空位置即可。

关键字序列T=（48,62,35,77,55,14,35,98），

请写出直接插入排序的中间过程序列。

{ 48 } 62 35 77 55 14 35 98

{ 48 62 } 35 77 55 14 35 98

{ 35 48 62 } 77 55 14 35 98

{ 35 48 62 77 } 55 14 35 98

{ 35 48 55 62 77 } 14 35 98

{ 14 35 48 55 62 77 } 35 98

{ 14 35 35 48 55 62 77 } 98

{ 14 35 35 48 55 62 77 98}

平均时间复杂度：T(n)=O(n*n)

空间：只需要一个辅助空间r[0]。

算法的稳定性：稳定

代码：

//假设待排序记录存放在r[1..n]之中，
//附设一个监视哨r[0]，使得r[0]始终存放待插入的记录
public void insSort(Node[] r) {
        int j = 0;
        for (int i = 2; i < r.length; i++) {
            r[0] = r[i];
            j = i - 1;
            while(r[0].key < r[j].key) {
                r[j + 1] = r[j];
                j = j -1;
            }
            r[j + 1] = r[0];
        }
    }

三、 折半插入排序

算法分析：

 虽然折半插入排序法与直接插入排序法相比较，改善了算法中比较次数的数量级，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n2)。 较，因此插入n-1个元素的平均关键字的比较次数为O(nlog2n)。 

  虽然折半插入排序法与直接插入排序法相比较，改善了算法中比较次数的数量级，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n2)。 

    void sort(Node[] nodes) {
        Node x;
        int low, mid, high = 0;
        for (int i = 1; i < nodes.length; i++) {
            x = nodes[i]; 
            low = 0;
            high = i - 1;
            while (low <= high) {
                mid = (low + high) / 2;
                if (x.key < nodes[mid].key) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            for (int j = i - 1; j >= low; j--) {
                nodes[j + 1] = nodes[j];
            }
            nodes[low] = x;
        }
    }

四、 希尔插入排序

希尔插入排序 (Shell's Sort)

是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

具体步骤：

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序， 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

时间复杂度：O(n^1.3~2)

空间复杂度：O(1)

稳定性：不稳定

void hillSort(Node[] nodes) {
        int len = nodes.length / 2;
        Node node;
        while (len != 0) {
            for (int i = len; i < nodes.length; i++) {          
                for(int j = len ; j<nodes.length ;j+= len) {
                    if (nodes[j].key < nodes[j - len].key) {
                        node = nodes[j];
                        nodes[j] = nodes[j - len];
                        nodes[j - len] = node;
                    }
                }
            }
            len = len / 2;
        }
    }