理解插入排序,希尔排序,选择排序的算法原理

在前面的文章中,其实已经把效率比较高的排序算法给分析过了,比如比较通用的快排,归并排序和堆排,还有用于特定场景的计数排序等。本篇我们把剩下的几种效率一般的排序算法给介绍一下,分别是插入排序,希尔排序和选择排序。

插入排序(Insert Sort)

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

这里我们假如有个无序数组如下,这里为了突出其排序规律,我们故意采用了一组降序的数字:

10,9,8,7,6

排序的过程如下:

[9, 10, 8, 7, 6]
[8, 9, 10, 7, 6]
[7, 8, 9, 10, 6]
[6, 7, 8, 9, 10]

从上面可以看到,每个元素会被依次加入上前面的有序序列,反复如此,直到全部排完序。

代码如下:

public static void sort(int[] numbers){
        for (int i = 1; i < numbers.length; i++) {
            //取遍历的每一个元素
            int currentNumber = numbers[i];
            int j = i - 1;
            //每一个元素,都会与前面所有的有序元素集合进行比较
            //从而交换自己的位置
            while (j >= 0 && numbers[j] > currentNumber) {
                numbers[j + 1] = numbers[j];
                j--;
            }
            //找到当前元素的位置,然后交换。
            numbers[j + 1] = currentNumber;
            System.out.println(Arrays.toString(numbers));
        }
    }

不难发现,对于n个元素的排序,插入排序是需要n*(n-1)次比较和交换的,所以其平均的时间复杂度为О(n²),空间复杂度属于原地排序,只需要一个额外的变量,所以是O(1),此外这种算法属于稳定性算法,不会改变相等元素的相对位置。

希尔排序 (Shell Sort)

希尔排序也称递减增量排序算法或,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

在插入排序中,每个排序一个元素,需要经过若干次交换才能归位,所以在希尔排序中,采用了步长来优化,这中方法每次可以交换两个元素,在最后步长等于1的时候,会退化成插入排序,但这个时候元素的位置基本有序,只需要执行少量的移动和交换即可完成排序,所以算是对插入排序的一种优化。

给定一个无序数组:

10,9,8,7,6

这里我们按数组的长度除以2来获取步长,则等于5/2=2;

那么则先进行

8 比 10 交换

7 比 9 交换

6 比 8 交换

最终必定会执行一次步长为1,也就是退化成插入排序,步骤如下:

[8, 9, 10, 7, 6]
[8, 7, 10, 9, 6]
[6, 7, 8, 9, 10]
[6, 7, 8, 9, 10]

上面的是根据步长进行的比较交换,我们可以发现规律,这两个比较的数字的索引间距是2。

第一轮交换后,数组一部分已经有序,然后步长继续缩减=2/2=1,这个时候,希尔排序彻底退化为插入排序,这个时候虽然也需要量量比较,但是移动次数却大大减少,所以效率相比原生的插入排序要高,但是这个效率与步长的间隔是有关系的,所以希尔排序的平均时间复杂度为:O(nlog^2 n) 平均空间复杂度是O(1),由于需要跨越交换,所以不属于稳定排序。

下面我们看下Java代码如何实现:

public static void sort(int array[]){
        //初始化步长
        int number = array.length / 2;
        //只要步长大于1,就继续排序
        while (number >= 1) {
            //遍历从步长开始的位置元素
            for (int i = number; i < array.length; i++) {
                //取出来当前遍历的元素
                int temp = array[i];
                //得到当前位置减去步长后的下标
                int j = i - number;
                //比较当前值与步长值的大小
                while (j >= 0 && array[j] > temp) {
                    array[j + number] = array[j];
                    j = j - number;
                }
                //赋值交换
                array[j + number] = temp;
                System.out.println(Arrays.toString(array));
            }
            //步长继续缩小,最终一定是1,整个算法退化成插入排序
            number = number / 2;
        }



    }

选择排序(Select Sort)

选择排序是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

选择排序的思想我认为非常容易理解,简单的说就是,每次找到数组中的最小值,然后放入对应的位置,因为条件是最小值,所以元素本身就在正确的位置,就不会移动,减少了移动的次数。

给定无序数组:

10,19,8,7,1

其排序步骤如下:

[1, 19, 8, 7, 10]
[1, 7, 8, 19, 10]
[1, 7, 8, 19, 10]
[1, 7, 8, 10, 19]

这里面可以看到第一次找到最小值1,然后与数组开始的10交换,第二次在剩下的数组中找到了7是最小值,然后与第2位置的19交换,第三次发现8在剩下元素中就是正确的位置,最后19与10交换,至此就完成了整个排序。

这里面的平均时间复杂度为О(n²),因为每一次查询最小值,都需要在剩下的数组中遍历一次,对于n个元素,需要n-1轮的比较查找。

其平均空间复杂度为O(1),这里面仅仅需要一个辅助元素即可。

选择排序采用数组实现的方式为非稳定排序方式。

代码如下:

public static  void sort(int arr[]){

        int min;//存储每次遍历得到的最小元素的数组下标值.
        int swap;//存储代待交换元素的值.
        for (int i = 0; i < arr.length; i++) {
            //依次数组的下标赋值.
            min = i;
            //遍历剩余部分的元素,找到最小值的下标.
            for (int j = i; j < arr.length; j++) {
                // 比较元素值.
                if (arr[j] < arr[min]) {
                    min = j;//下标赋值.
                }
            }
            //每次把最小值提前.
            swap = arr[min];
            arr[min] = arr[i];
            arr[i] = swap;

            System.out.println(Arrays.toString(arr));
        }

    }

总结:

本文主要了介绍了插入排序,希尔排序,选择排序的算法原理和思想,尽管这些排序算法并不是最优的选择,并不适合大数据量集下的排序,但是了解这些算法的基本思想还是很有必要的。

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2018-11-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

排序算法-插入排序

算法简介 插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应...

2754
来自专栏从流域到海域

《笨办法学Python》 第19课手记

《笨办法学Python》 第19课手记 本节课讲函数和变量(变量和函数的关系是变量作为做函数的参数,定义时是形参,使用时是实参),内容比较简单。 源代码如下: ...

23710
来自专栏轮子工厂

6. 简单又复杂的“运算符”,建议你看一哈

昨天的《5. 很“迷”的字符与字符串》初稿本来很短的,但是我觉得内容太少了,就加了一些,结果好像就变得特别多〒▽〒。

853
来自专栏老九学堂

【必读】C语言基础知识大全

C语言程序的结构认识 用一个简单的c程序例子,介绍c语言的基本构成、格式、以及良好的书写风格,使小伙伴对c语言有个初步认识。 例1:计算两个整数之和的c程...

5428
来自专栏IT可乐

Java数据结构和算法(六)——前缀、中缀、后缀表达式

  前面我们介绍了三种数据结构,第一种数组主要用作数据存储,但是后面的两种栈和队列我们说主要作为程序功能实现的辅助工具,其中在介绍栈时我们知道栈可以用来做单词逆...

2509
来自专栏nummy

python堆排序heapq

堆是一种树形数据结构,其中子节点与父节点之间是一种有序关系。最大堆中父节点大于或等于两个子节点,最小堆父节点小于或等于两个子节点。Python的heapq模块实...

1903
来自专栏PPV课数据科学社区

走近 Python (类比 JS)

Python 是一门运用很广泛的语言,自动化脚本、爬虫,甚至在深度学习领域也都有 Python 的身影。作为一名前端开发者,也了解 ES6 中的很多特性借鉴自 ...

40810
来自专栏HTML5学堂

操作符与数据类型转换

上一期堡堡给大家讲解了关于JS的基础语法,虽然是一些非常基础的知识,但是它对大家的后期学习奠定了一定的基础。知识像一张网,基础越扎实,网住的鱼就越多,要告诉大家...

3068
来自专栏决胜机器学习

从机器学习学python(三) ——数组冒号取值与extend

从机器学习学python(三)——数组冒号取值与extend (原创内容,转载请注明来源,谢谢) 一、数组冒号取值 1、 小白级别 python的特有取值方式...

3444
来自专栏程序员互动联盟

【编程基础】C++ Primer快速入门之七:运算符

一、表达式的定义 什么是表达式?表达式,是由数字、运算符、数字分组符号(括号)、自由变量和约束变量等以能求得数值的有意义排列方法所得的组合(1)。1 + 2是个...

3104

扫码关注云+社区

领取腾讯云代金券