看了这篇文章,我发现排序算法好简单

来自:程序员共成长(微信号:finishbug),作者:程序员共成长

1

插入排序


插入排序是最简单的一种排序方式。这里就不去啰嗦绕口的概念了,通过图去解释什么是插入排序

假设一个数组内有如下5个元素,需要对其按照从小到大的顺序进行排列。



插入排序就是从未排序序列中,取出元素,在已排序序列中一次比较。插入到相应的位置。

在上面的五个数字中

  1. 我们假设有一个长度为一的有序系列为12。

  2. 而8、17、31、22为无序序列。

  3. 从无序序列中取出一个元素8,与有序序列中的12进行比较。比12小,则将其移动到12前面,反之放在后面

结果为



依次类推,最终得到一个有序序列。这个过程称为插入排序


代码实现如下 


public static void main(String[] args) {
        Integer[] arr = {128173122};
        // 第一个元素为有序,因此从i = 1开始
        for (int i = 1; i < arr.length; i++) {
            // 待插入元素 第一次循环arr[i] 就是8
            Integer temp = arr[i];
            int j;
            for (j = i - 1; j >= 0; j--) {
                // 数组中第二个元素与第一个元素比较,12>8
                if (temp < arr[j])
                /**
                 * 复制j位元素到j+1
                 * 循环一次是,结果为12、12、17、31、22
                 */

                    arr[j + 1] = arr[j];
                else
                    break;
            }
            /**
             * j + 1 位为要插入的最小元素
             * 循环一次结果为8、12、17、31、22
             */

            arr[j + 1] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }



2

二分排序


在说二分排序之前不得不提到二分查找这个基本的算法。那什么是二分查找呢?

举个例子,大家应该都玩过猜数字的游戏,如果从1~100这里面猜一个数字。我只需要对你猜的数字回答 “大了”、“小了”。直至猜出结果。

如果漫无目的的去猜,运气不好可能会猜100次。那怎么样才能更少次数的猜出结果呢。


假设我们的目标数字是 66


我猜数字是 50

小了

那75呢?

又大了

嗯,那我猜50和75的中间数63!

这次小了



那继续63和75的中间数 69 ~!

大啦大啦

那63和69的中间数 66呢?

哈哈,终于被你才出来了。

二分大法果然好,五次就猜出来了

●●●


对于N个元素的列表,我们要猜出其中一个数字最多只需要log 2 N次。如果列表中1024个数字,我们也只需要猜测10次就可以出来。2的十次方等于1024.


回到我们的二分插入,原理基本一样,从无序列表中取出一个元素,跟前面的有序列表的中间数进行比较,如果小了,再进行折半比较,直至找到合适的位置。


如图,6、9、12、18、20为有序列表,对15进行二分插入



  • 取出有序列表的中间元素12。12< 15。

  • 12、18、20取出中间元素,18。18 > 15

  • 在12、18中进行比较,12<15<18


public static void main(String[] args) {
        int i, j, right, left, mid, temp;
        Integer[] arr = {1281731224419976};
        // 依旧把第一个元素当成有序的,因此从i=1开始
        for (i = 1; i < arr.length; i++) {
            //如果后一个元素比前一个元素大,则continue,开始下一次循环
            if (arr[i] > arr[i - 1]) {
                continue;
            }
            temp = arr[i];
            //最左边为二分插入的起始位置
            left = 0;
            //左右定义有序列表的长度
            right = i-1;
            while (left <= right) {
                //mid为中间元素的下标
                mid = (left + right) / 2;
                // 中间元素和要插入的元素进行比较
                if (arr[mid] < temp)
                    //如果中间元素小,则起始位置为mid + 1
                    left = mid + 1;
                else
                    //同left
                    right = mid - 1;
            }
            // 移动元素到相应的位置
            for (j = i - 1; j >= left; j--) {
                arr[j + 1] = arr[j];
            }
            arr[left] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }



3

希尔排序 


希尔排序又成为缩小增量排序。假设有一个长度为N的数组,他的增量设为X(X<N),将数组拆分为多个子序列,在每个子序列中进行直接插入排序。然后减少增量的值,重复以上操作,直至X=1(即一个子序列中只有一个元素)。这样理解可能比较混乱,看图说话吧。

如图,一个长度为8的无序数组



增量通常取长度的一般,所以增量为 8/2 = 4。意味着此时被拆分为4个子序列。

[18 , 10], [22,1],[3,19],[51,55]

我用四种不同的颜色进行标识


然后子序列中的元素进行插入排序,即同一颜色的两个数进行排序,结果为


然后缩小增量,此时增量为4/2 = 2。被分为两个子序列

[10,3,18,19] ,[1,5 1,22,55]


再次对子序列进行排序,得到的结果如下


重复上述操作,再次缩小增量直至为1,经过增量递减的过程,其实就是元素排序的过程,当增量为1时,大部分元素其实已经排好顺序了,我们只需要对其进行微调即可。


代码实现如下

public static void main(String[] args) {
        Integer[] arr = {18223511011955};
        // 初始增量通常为总长度的一半
        int mid = arr.length / 2;
        int i;
        while (mid > 0) {
            for (i = mid; i < arr.length; i++) {
                // 起始下标
                int begin = i - mid;
                int tmp = arr[i];
                // 起始下标元素大 则调整位置,
                while (begin >= 0 && arr[begin] > arr[i]) {
                    arr[begin + mid] = arr[begin];
                    begin -= mid;
                }
                //并且调换位置
                arr[begin + mid] = tmp;
            }
            // 每次结束,增量缩小一半。也可以自定义
            mid = mid / 2;
            System.out.println(Arrays.toString(arr));
        }
    }



4

总结


插入排序适用于少量数据的排序,其时间复杂度为O(n^2)。

二分排序则是利用了数组能够快速定位的特点,时间复杂度也是O(n^2),适用于较大数据排序

希尔排序的实质是分组再进行直接插入,开始时增量较大时,插入排序的数量少,所以前期会很快。当增量变小时,数据也基本有序了。所以希尔排序的时间复杂度要比O(n^2)要好很多。

推荐↓↓↓
算法与数据结构
上一篇:30 张图弄懂「图的两种遍历方式」 下一篇:方法不对,看再多书你都学不会算法!