数据结构与算法之美笔记——排序（上）

作者: Cloneable | 来源:发表于2019-05-19 22:54 被阅读0次

摘要:

排序是算法中基础的算法，对于一个排序算法的评价需要从「时间复杂度」、「空间复杂度」和「是否稳定」三个方面综合分析。这章节主要讲解「冒泡排序」、「插入排序」和「选择排序」，这三个排序都是时间复杂度为 $O(n^2)$ 的算法，但在实际使用中更加偏向插入排序。

排序算法的执行效率

分析一个排序算法的执行效率需要从时间复杂度、空间复杂度和是否稳定三个维度进行。

时间复杂度

最好、最坏、平均时间复杂度

排序算法不仅要分析平均时间复杂度，最好和最坏时间复杂度也需要分析，因为一组完全有序的数据和一组完全无序的数据对排序算法的时间影响很大，所以这三种时间复杂度都需要分析。

时间复杂度的低阶、系数和常数

一般情况时间复杂度的表示会忽略低阶、系数和常数，因为时间复杂度只是描述一个执行时间随数据规模 $n$ 变化的趋势，但实际开发中排序会遇到很多数据规模较小的情况，同阶时间复杂度的对比中需要把低阶、系数和常数考虑进来。

比较次数和交换次数

这节讲解的排序算法主要是基于比较的排序算法，基于比较的排序算法主要操作就是数据的比较和交换，所以对于排序算法需要把比较次数和交换次数作为一个比较标准。

空间复杂度

空间复杂度可以衡量排序算法的内存占用情况，基于空间复杂度的分析排序算法还引入了一个概念「原地排序」，原地排序就是指空间复杂度为 $O(1)$ 的排序算法。

稳定性

如果两个相同的数据经过排序之后位置的前后顺序不会改变，这样的排序算法就是稳定的排序算法，排序算法的稳定性有什么作用？

实际开发中排序不只用于单纯的数字排序，有可能会根据某个对象的 key 值对对象进行排序。举个例子，比如需要对一组订单数据进行排序，按订单金额从小到大排序，相同金额的订单按下单时间先后排序。面对这样的需求可能最开始想到的方案是先按照订单金额排序，再对相同金额区间的数据进行时间排序，但这样实现会相对复杂；另一种方案就是先把数据按下单时间顺序排序，再将数据以稳定的排序算法进行金额的排序，稳定的排序算法在对金额进行排序的同时不会影响已经排序好的下单时间顺序，这样也可以完成需求，并且只是对数据简单地进行了两次排序，实现起来难度较低一些。

冒泡排序

冒泡排序会遍历需要排序的数据，被遍历到的当前数据与后一位比较，如果当前数据大于后一位就进行交换，遍历到结束后末尾数据必然为当前遍历数据中最大的一个，除去最后一位其他数据还需要进行排序，可以再以相同的方式对其他数据进行排序，直到需要排序的数据个数为 0时排序完成，冒泡排序的操作如下图。

冒泡排序

代码实现

public static void sort(int[] values, int len) {
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < len - i - 1; j++) {
            if(values[j] > values[j + 1]) {
                int temp = values[j + 1];
                values[j + 1] = values[j];
                values[j] = temp;
            }
        }
    }
}

虽然这个段代码实现了冒泡排序，但是当一组数据有序时还是需要不断重复遍历比较，其实数据有序之后的重复遍历都是没有必要的，当一次遍历排序中没有数据交换我们就可以认为这组数据已经完全有序，并且结束整个排序，代码如下。

public static void sort(int[] values, int len) {
    for(int i = 0; i < len; i++) {
        // mark weather value is exchanged when bubble sorting
        boolean isExc = false;
        for(int j = 0; j < len - i - 1; j++) {
            if(values[j] > values[j + 1]) {
                isExc = true;
                int temp = values[j + 1];
                values[j + 1] = values[j];
                values[j] = temp;
            }
        }

        if(!isExc) {break;}
    }
}

执行效率分析

最好时间复杂度

当数据完全有序时，只需要一次遍历，所以时间复杂度为 $O(n)$ 。

最坏时间复杂度

当一组数据完全无序时，每次排序需要遍历的次数分别为 $n,n-1,n-2,...,3,2,1$ 次，所以时间复杂度为 $O(n^2)$ 。

平均时间复杂度

冒泡排序的平均时间复杂度分析需要使用加权平均数，计算比较复杂，这里引入一种粗略估算平均时间复杂度的方式。这种方式主要有两个概念「有序度」「无序度」，有序度就是指一组数据中有序的数据对数，无序度就是正好相反，指一组数据中无序的数据对数，而完全有序的一组数据的有序度称为「满有序度」，这三个度量之间存在 无序度 = 满有序度 - 有序度 的数学关系。

例：一组数据为 $3,8,6$ ,这组数据的有序度为 2，有序对分别是(3,8)，(3,6)，满有序度满足公式 $n\times\frac{n-1}{2}$ (n 为数据量)，所以这组数据满有序度为 3，根据三者间的关系计算无序度为 1。

冒泡排序进行一次交换就会使数据的有序度增加 1，相应的就是无序度减少 1，冒泡排序结束的标志是无序度为 0 , 所以无序度就是冒泡排序要进行数据交换的次数，完全无序的一组数据交换次数为 $n\times\frac{n-1}{2}$ ，那我取无序度为一半的情况为平均情况，也就是交换次数为 $n\times\frac{n-1}{4}$ ，所以冒泡排序的平均时间复杂度为 $O(n^2)$ 。

是否原地排序

冒泡排序中只有在数据交换时额外申请了一个存储空间，所以空间复杂度为 $O(1)$ ，冒泡排序是原地排序算法。

稳定性

比较数据时可以控制只有大于的情况才进行交换，相等的情况不进行数据交换，相等的数据顺序就不会被改变，所以冒泡排序是稳定的排序算法。

插入排序

当把一个数据插入一个有序数组时要保持数据的有序，我们会将这个数据在数组中比对，找到这个数据合适的位置，将其他数据进行搬移，将这个数据插入相应的位置，这样就可以保证数据的有序性。

插入排序也是利用相同的思想，将一组数据分为「有序区」和「无序区」，遍历无序区的数据并将其插入有序区，而且需要保持有序区的数据完全有序。

代码实现

public void sort(int[] array, int len) {
    for(int i = 1; i < len; i++) {
        int value = array[i];
        for(int j = i -1; j >= 0; j--) {
            if(value < array[j]) {
                array[j + 1] = array[j];
                if(j == 0) {
                    array[j] = value;
                }
            } else {
                array[j + 1] = value;
                break;
            }
        }
    }
}

执行效率分析

最好时间复杂度

完全有序的数据中需要遍历一次就可以完成插入排序，所以最好时间复杂度为 $O(n)$ 。

最坏时间复杂度

完全无序的一组数据需要进行 n 次排序，每次排序进行的数据搬移的时间复杂度为 $O(n)$ ，所以最坏时间复杂度为 $O(n^2)$ 。

平均时间复杂度

与冒泡排序相似，完成一次数据交换使一组数据无序度减 1，完成插入排序就是使无序度为 0，平均情况下需要进行 $n\times\frac{n-1}{4}$ 次数据交换，所以插入排序的平均时间复杂度为 $O(n^2)$ 。

是否原地排序

插入排序没有申请额外的存储空间，空间复杂度为 $O(1)$ ，所以插入排序是原地排序。

稳定性

在插入排序将无序区数据向有序区进行插入时，比较数据可以控制为当插入数据小于有序区数据时才交换，相等的数据前后顺序可以保证，所以插入排序是稳定的排序算法。

选择排序

选择排序也是将一组数据分为有序区和无序区，不过与插入排序不同的是，选择排序会在无序区选择最小的一个数据，将其放置到有序区的末尾。

代码实现

public void sort(int[] array, int len) {
    for(int i = 0; i < len; i++) {
        int minValueIndex = i;
        for(int j = i; j < len - 1; j++) {
            if(array[j + 1] < array[j]) {
                minValueIndex = j + 1;
            }
        }

        int temp = array[i];
        array[i] = array[minValueIndex];
        array[minValueIndex] = temp;
    }
}

执行效率分析

时间复杂度

选择排序无论一组数据是完全有序还是完全无序都需要循环 n 次在无序区查找最小值并将最小值插入有序区末尾的操作，无序区查找最小值的平均时间复杂度为 $O(n)$ ，所以选择排序的最好、最坏时间复杂度都是 $O(n^2)$ 。

选择排序的平均时间复杂度分析与最好、最坏时间复杂度分析类似，所以选择排序的平均时间复杂度为 $O(n^2)$ 。

是否原地排序

选择排序只是在数据交换时申请了额外的一个空间存储，空间复杂度为 $O(1)$ ，所以选择排序是原地排序算法。

稳定性

选择排序会将无序区中最小数据与无序区第一个数据交换，这样的数据交换会影响相等数据的顺序，所以选择排序是不稳定的排序算法。

例：一组数据为 $5,3,5,2,1$ ，这组数据在选择排序的第一次操作中会将 1 与第一个 5 进行交换，这样两个 5 的顺序就产生了变化。

总结

算法名称	空间复杂度	稳定性	最好、最坏、平均时间复杂度
冒泡排序	原地排序	稳定	$O(n)$ $O(n^2)$ $O(n^2)$
插入排序	原地排序	稳定	$O(n)$ $O(n^2)$ $O(n^2)$
选择排序	原地排序	不稳定	$O(n^2)$ $O(n^2)$ $O(n^2)$

虽然冒泡排序和插入排序在执行效率的三个维度上的结果都是一样的，但是实际中更加偏向使用插入排序，原因是在数据交换的操作上冒泡排序会进行三步操作，但插入排序只需要进行一步操作就可以完成数据交换，这里会影响排序算法的执行效率。

文章中如有问题欢迎留言指正
此章节的冒泡排序、插入排序和选择排序代码已经上传GitHub点击跳转查看代码。
数据结构与算法之美笔记系列将会做为我对王争老师此专栏的学习笔记，如想了解更多王争老师专栏的详情请到极客时间自行搜索。

数据结构与算法之美笔记——排序（上）

排序算法的执行效率

时间复杂度

空间复杂度

稳定性

冒泡排序

代码实现

执行效率分析

最好时间复杂度

最坏时间复杂度

平均时间复杂度

是否原地排序

稳定性

插入排序

代码实现

执行效率分析

最好时间复杂度

最坏时间复杂度

平均时间复杂度

是否原地排序

稳定性

选择排序

代码实现

执行效率分析

时间复杂度

是否原地排序

稳定性

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读