经典算法——折半插入排序

文章目录

• 1. 什么是算法？
• 2. 算法的效率
• 3. 折半插入排序
  • 3.1 折半插入排序介绍
  • 3.2 代码实践
  • 3.3 算法效率

1. 什么是算法？

任何被明确定义的计算过程都可以称作 算法 ，它将某个值或一组值作为输入，并产生某个值或一组值作为输出。所以 算法可以被称作将输入转为输出的一系列的计算步骤 。

说白了就是步骤明确的解决问题的方法。由于是在计算机中执行，所以通常先用伪代码来表示，清晰的表达出思路和步骤，这样在真正执行的时候，就可以使用不同的语言来实现出相同的效果。

2. 算法的效率

算法效率是指算法 执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。在现在的计算机硬件环境中，比较少需要考虑这个问题了，特别是pc机的编程， 内存空间 越来越大，所以被考虑得也越来越少，不过一个好的程序员，都应该对自己的程序有要求，每一个for比别人少一次判断1000个for就能够少掉很多的运行时间。所以能够理解，能够大概的去运用"效率度量"还是有很大意义的。我们一般通过两个方面来衡量一个算法的效率

• 时间复杂度?

算法的时间复杂度是一个函数，它定性描述一个算法的运行时间。 一个算法的执行所需要的时间，从理论上来说是算不出来的，必须通过上机测试才能得到，但这并不是说我们对于每个算法都要上机测试，我们只需要知道哪个算法所花的时间多，哪个算法所花的时间少就行。 一个算法花费的时间与算法中的语句执行次数成正比，算法中的语句执行次数越多，它花费的时间就越多。一个算法中的语句执行次数成为语句频度或时间频度，记为T(n)，n为问题的规模。

• 空间复杂度?

空间复杂度是指执行这个算法所需要的内存空间。 空间复杂度需要考虑在运行过程中为 局部变量分配的存储空间的大小 ，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。 空间复杂度也就是对一个算法在运行过程中 临时占用存储空间大小 的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2)，空间复杂度是O(1) 。

• 稳定性?

算法稳定性指的是在一组待排序记录中，如果存在任意两个相等的记录R和S，且在待排序记录中R在S前，如果在排序后R依然在S前，即它们的前后位置在排序前后不发生改变，则称为排序算法为稳定的。

常见排序算法的稳定性：堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

3. 折半插入排序

3.1 折半插入排序介绍

折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

过程 把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素；排序过程即每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。

与直接插入算法的区别在于：在有序表中寻找待排序数据的正确位置时，使用了 折半查找/二分查找 。

3.2 代码实践

Java代码

 @Test
public void main3() {
    // input data
    int[] a = {11, 34, 20, 10, 12, 35, 41, 32, 43, 14};
    // 数组下标从0开始，j初始为1，指向第二个元素
    for (int i = 1; i < a.length; i++) {
        if (a[i] < a[i - 1]) {
            // 使用temp记录当前元素的值
            int tmp = a[i];
            // 初始化变量
            int left = 0;
            int right = i - 1;
            // while循环作用：使用二分查找确定元素位置，并串出对应的位置
            while (left <= right) {
                // 取中间元素，以下写法防止数据量较大时发生溢出
                int mid = (right - left) / 2 + left;
                if (a[mid] > tmp) {
                    // 待排元素较小，将搜索区间缩小至左一半
                    right = mid - 1;
                } else {
                    // 待排元素较大，将搜索区间缩小至右一半
                    left = mid + 1;
                }
            }
            // 将待排元素放在对应的位置
            for (int j = i - 1; j >= right + 1; j--) {
                a[j + 1] = a[j];
            }
            a[right + 1] = tmp;
        }
    }
    // 查看排序结果
    for (int data : a) {
        System.out.print(data + "\t");
    }
}

3.3 算法效率

时间复杂度

折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，折半插入排序和插入排序的时间复杂度相同都是O(N2)。 在减少了比较次数方面它确实相当优秀，所以该算法仍然比直接插入排序好。

空间复杂度

折半插入排序和插入排序一样只需要一个多余的缓存数据单元来放第 i 个元素，所以空间复杂度是O(1)，

稳定性

因为排序前2个相等的数在序列的前后位置顺序和排序后它们两个的前后位置顺序相同，所以它是一个稳定排序。