八大排序例程+讲解——插入类排序

八大排序例程+讲解——插入类排序

插入排序

插入排序由N-1趟排序组成。插入排序假定位置0到位置p-1上的元素是有序的，然后通过将位置p上的元素插入到正确的位置，第p趟排序使位置0到位置p上的元素是有序的。

简单说就是，序列的前部分是有序的，要把无序部分的第一个元素插到前部分中，使得有序的序列长度+1，直到整个序列都是有序的。

/**
 *Simple insertion sort.
 *@param a an array of Comparable items.
 */
public static <AnyType extends Comparable<? super AnyType>>
    void insertionSort(AnyType[] a){
    int j;
    //插入的过程是从有序部分的最后一个元素开始，往前比较。
    //p指向即将被插入到有序序列的那个元素
    //一旦j-1指向的元素比j的要小，那么j就是元素应在的正确位置
    for(int p = 1; p < a.length; p ++){
        AnyType temp = a[p];
        for(j = p; j > 0 && temp.compareTo(a[j - 1]) < 0; j --)
            a[j] = a[j - 1];
        a[j] = temp;
    }
}

复杂度分析：

插入排序的嵌套循环每一侧都花费N次迭代，因此平均时间复杂度为O(N^2)。

稳定性分析：

由于不满足temp.compareTo(a[j - 1])<0时跳出循环，也就是temp大于等于a[j - 1]时，跳出循环，因此原本在前的数还是在前，插入排序是稳定的。

希尔排序（缩减增量排序）

希尔排序通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

对于某一趟排序，就是对相距一定间隔的元素进行插入排序。

我个人的理解，因为插入排序的复杂度是N的平方，通过缩短序列的长度，可以降低时间消耗吧。

/**
 *Shellsort, using Shell's(poor) increments
 *@param a an array of Comparable items.
 */
public static <AnyType extends Comparable<? super AnyType>>
    void shellSort(AnyType[] a){
    int j;
    //增量gap,每轮循环缩小步长
    for(int gap = a.length/2; gap > 0; gap /= 2){
        //从第gap个元素，逐个对其所在的组进行插入排序
        for(int i = gap; i <a.length; i ++){
            AnyType temp = a[i];
            for(j = i; j > 0 && temp.compareTo(a[j - gap]) < 0; j -= gap)
               a[j] = a[j - gap];
            a[j] = temp;
        }
    }
    
}

复杂度分析：

不同的增量序列对排序的性能有影响。

使用希尔增量时，最坏情况的运行时间为O(N^2)。

使用Hibbard增量时，最坏情况的运行时间为O(N^1.5)。

稳定性分析：

虽然希尔排序的内核是插入排序，但是因为间隔gap的原因，相同的两个数可能会分到不同组中，再经过插入排序，相对顺序是可能变化的，希尔排序是不稳定的。

八大排序例程+讲解——插入类排序

原文：https://www.cnblogs.com/peekapoo/p/12157886.html