基本排序（二）插入排序(直接插入、Shell、折半)

时间：2021-06-13 23:14:34

　　插入排序是常见的内部排序之一。常见的插入排序包括直接插入排序、Shell排序、折半排序。本篇主要介绍这三个排序。

　　转载请注明出处——http://www.cnblogs.com/zrtqsk/p/3807611.html，谢谢！

一、直接插入排序

　　直接插入排序大概是我们最容易理解的一类排序了。

　　1、原理

　　对于n个元素的记录。

　　第一趟　　：　　把第2个元素拿出来跟第1个元素对比，小的在前面、大的在后面。

　　第二趟　　：　　把第3个元素拿出来插入到前2个元素中，使他们有序。

　　第三趟　　：　　把第4个元素拿出来插入到前3个元素中，使他们有序。

　　......

　　第n-1趟　：　　把第n个元素拿出来插入到前n-1个元素中，排序完成。

　　2、Java实现

package sort;

/**

 * 想法：如果要将数组集体后移，那么必须要从后往前遍历。

 *

 * @ClassName: InserSort

 * @Description: 插入排序

 * @author qsk

 * @date 2014年6月21日 下午4:06:04

 */

public class InsertSort {

    public static void sort(int[] source) {

        SortUtil.outputArray(source);

        int size = source.length;

        // 从第二个开始，遍历每一个数组元素

        for (int i = 1; i < size; i++) {

            // 取出来

            int temp = source[i];

            // 跟之前排序好的进行比较、插入

            for (int j = 0; j < i; j++) {

                // 如果比某一个小，

                if (temp < source[j]) {

                    // 那么原排序好的，集体后移

                    for (int k = i; k > j; k--) {

                        source[k] = source[k - 1];

                    }

                    source[j] = temp;

                    //输出

                    SortUtil.outputArray(source);

                    // 集体后移后，跳出循环

                    break;

                }

            }

        }

    }

    // 改进后的

    public static void sort1(int[] source) {

        SortUtil.outputArray(source);

        int size = source.length;

        // 从第二个开始，遍历每一个数组元素

        for (int i = 1; i < size; i++) {

            // 取出来

            int temp = source[i];

            // 从后往前遍历，找到插入位置

            int j;

            for (j = i - 1; j >= 0 && temp < source[j]; j--) {

                source[j + 1] = source[j];

            }

            // 由于上面的循环完毕之后执行了j--,所以这里给source[j+1]赋值

            source[j + 1] = temp;

            //输出

            SortUtil.outputArray(source);

        }

    }

    public static void main(String[] args) {

        sort1(SortUtil.getRandomArray());

    }

}

如上，有2个实现，sort()是我很快写出来的，很明显，3个嵌套循环非常麻烦。这里我们可以发现，遍历一个数组结构的时候，向前和向后遍历都很讲究，要想清楚处理逻辑再决定选择向前还是向后遍历。注释解释的很清楚了，不必多说。结果如下：

[6, 22, 71, 64, 33, 57, 38, 30, 42, 14]

[6, 22, 71, 64, 33, 57, 38, 30, 42, 14]

[6, 22, 71, 64, 33, 57, 38, 30, 42, 14]

[6, 22, 64, 71, 33, 57, 38, 30, 42, 14]

[6, 22, 33, 64, 71, 57, 38, 30, 42, 14]

[6, 22, 33, 57, 64, 71, 38, 30, 42, 14]

[6, 22, 33, 38, 57, 64, 71, 30, 42, 14]

[6, 22, 30, 33, 38, 57, 64, 71, 42, 14]

[6, 22, 30, 33, 38, 42, 57, 64, 71, 14]

[6, 14, 22, 30, 33, 38, 42, 57, 64, 71]

　　3、时间复杂度和稳定性
　　直接插入排序的时间复杂度是O(N2)。
　　假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，直接插入排序的时间复杂度是O(N2)。
　　直接插入排序是稳定的算法，它满足稳定算法的定义。

二、折半插入排序

　　1、原理

　　折半插入排序是对直接插入排序的改进。

　　我们看直接插入排序的步骤简单而言其实就2步，第1步是从已经排好序的数组中找到该插入的点，第2步是将数据插入，然后后面的数据整体后移。那么直接插入排序是如何找到该插入的点的呢？是无脑式的从头到尾的遍历。问题是被插入的数组是排好序的，根本没有必要从头到尾遍历。折半插入排序就是改进了第1步——从已经排好序的数组中找到该插入的点。

　　折半插入排序是怎么做的呢？非常简单。取已经排好序的数组的中间元素，与插入的数据进行比较，如果比插入的数据大，那么插入的数据肯定属于前半部分，否则属于后半部分。这样，不断遍历缩小范围，很快就能确定需要插入的位置。这就是所谓“折半”。

　　(Arrays类的binarySearch()方法就是折半查找的实现)

　　

　　2、Java实现

package sort;

public class HalfInsertSort {

    public static void sort(int[] source) {

        int size = source.length;

        for (int i = 1; i < size; i++) {

            // 拿出来

            int temp = source[i];

            int begin = 0; // 标记排好序的数组的头部

            int end = i - 1; // 标记排好序数组的尾部

            // 只要头部一直小于尾部，说明temp还在2个标记范围内

            while (begin <= end) {

                // 取2个标记的中间数据的值

                int mid = (begin + end) / 2;

                // 比较，若比中间值大，则范围缩小一半

                if (temp > source[mid]) {

                    begin = mid + 1;

                    // 否则，范围也是缩小一半

                } else {

                    end = mid - 1;

                }

                // 循环结束时，end<begin,即i应该插入到begin所在的索引

            }

            // 从begin到i，集体后移

            for (int j = i; j > begin; j--) {

                source[j] = source[j - 1];

            }

            // 插入i

            source[begin] = temp;

            SortUtil.outputArray(source);

        }

    }

    public static void main(String[] args) {

        sort(SortUtil.getRandomArray());

    }

}

如上，注释已经非常清楚了。结果如下：

[4, 11, 4, 41, 61, 83, 86, 81, 35, 90]

[4, 4, 11, 41, 61, 83, 86, 81, 35, 90]

[4, 4, 11, 41, 61, 83, 86, 81, 35, 90]

[4, 4, 11, 41, 61, 83, 86, 81, 35, 90]

[4, 4, 11, 41, 61, 83, 86, 81, 35, 90]

[4, 4, 11, 41, 61, 83, 86, 81, 35, 90]

[4, 4, 11, 41, 61, 81, 83, 86, 35, 90]

[4, 4, 11, 35, 41, 61, 81, 83, 86, 90]

[4, 4, 11, 35, 41, 61, 81, 83, 86, 90]

　　3、时间复杂度和稳定性
　　折半插入排序的时间复杂度是O(N2)。
　　折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。
　　折半插入排序是稳定的算法，它满足稳定算法的定义。

三、Shell排序

　　1、原理

　　Shell排序也是对直接插入排序的改进。它实质上是一种分组插入方法。可以这么简单理解：

　　对于n个元素的数组，假设增量为 h：

　　第一趟　　：　　从第1个元素开始，每隔h取一个元素，那么最后可以得到n/h个元素，一边取，一边通过直接插入将这h个元素排序

　　第二趟　　：　　从第2个元素开始，每隔h取一个元素，跟第一趟一样。　　

　　...

　　第h趟　　 ：　　从第h个元素开始，每隔h取一个元素，跟第一趟一样。

　　（此时，整个数组还不是有序的）

　　然后，减少h的值，重复上面的操作，直到h减小为1，排序完成。

　　2、Java实现

package sort;

/**

 * @ClassName: ShellSort

 * @Description: 折半排序

 * @author qsk

 * @date 2014年6月22日 下午3:48:01

 */

public class ShellSort {

    public static void sort(int[] source) {

        // 排序前先输出

        SortUtil.outputArray(source);

        int size = source.length;

        // 增量

        int h = 1;

        // 得到增量的最大值

        while (h <= size / 3) {

            h = h * 3 + 1;

        }

        while (h > 0) {

            System.out.println("h的值为" + h);

            // 因为每个i都要跟i-h比较，所以从h到size遍历了每个数组元素

            for (int i = h; i < size; i++) {

                // 取值

                int temp = source[i];

                // 取i之前h距离的索引为j

                int j = i - h;

                // 如果temp比j对应的值小

                if (temp < source[j]) {

                    // 从j开始往前每隔h取一个值，如果这个值比temp要大，那么把这个值后移h个单位。

                    for (; j >= 0 && source[j] > temp; j -= h) {

                        source[j + h] = source[j];

                    }

                    // 最后将temp的值插入合适位置

                    source[j + h] = temp;

                    SortUtil.outputArray(source);

                }

            }

            h = (h - 1) / 3;

        }

    }

    public static void sort1(int[] source) {

        // 排序前先输出

        SortUtil.outputArray(source);

        int size = source.length;

        // 增量

        int h = 1;

        // 得到增量的最大值

        while (h <= size / 3) {

            h = h * 3 + 1;

        }

        while (h > 0) {

            System.out.println("h的值是" + h);

            // 0到h的遍历

            for (int x = 0; x < h; x++) {

                // i每次递增h，这两个for循环，遍历了所有数组元素

                for (int i = x + h; i < source.length; i = i + h) {

                    // 用temp记录i的值

                    int temp = source[i];

                    int j;

                    // 从j开始往前，每隔h取一个值与temp进行比较，若比temp大则向后移动h个单位

                    for (j = i - h; j >= 0 && source[j] > temp; j = j - h) {

                        source[j + h] = source[j];

                    }

                    source[j + h] = temp;

                }

                // 每一趟排序后输出

                SortUtil.outputArray(source);

            }

            h = (h - 1) / 3;

        }

    }

    public static void main(String[] args) {

        sort1(SortUtil.getRandomArray());

    }

}

这里有2个算法实现，第二个sort1()方法，用了3个for循环嵌套，比较容易理解，不过实在不够优雅。而sort1()将其进行了改进，使用2个for循环实现。

我们知道，Shell排序的关键是确定增量 h 的值，以及 h 如何减少。上文的 h 值算法由Knuth提出，是比较常用的取h值的算法。经常可以看到许多人实现shell排序，取h的时候，直接减半，这样，数组项移动的距离很长，不过移动元素的个数较少，相对而言没有Knuth的算法有效率。

上面的结果如下：

h的值是4

[4, 9, 89, 85, 36, 5, 85, 44, 96, 96]

[4, 5, 89, 85, 36, 9, 85, 44, 96, 96]

[4, 5, 85, 85, 36, 9, 89, 44, 96, 96]

[4, 5, 85, 44, 36, 9, 89, 85, 96, 96]

h的值是1

[4, 5, 9, 36, 44, 85, 85, 89, 96, 96]

　　3、时间复杂度和稳定性
　　Shell排序的时间复杂度是根据增量h的不同而不同，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)。Shell排序的时间复杂度在O(n3/2)-O(n7/6)之间。
　　Shell排序算法是一种不稳定的排序算法。

参考：《Java程序员的基本修养》

　　http://www.cnblogs.com/skywang12345/p/3597597.html

相关文章