数据结构与算法整理总结---排序 1

排序

数据结构与算法整理总结---排序

如何分析⼀个“排序算法”?

1.排序算法的执⾏效率

对于排序算法执⾏效率的分析,我们⼀般会从这⼏个⽅⾯来衡量:

1.最好情况、最坏情况、平均情况时间复杂度

我们在分析排序算法的时间复杂度时,要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外,你还要说出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。

为什么要区分这三种时间复杂度呢?第⼀,有些排序算法会区分,为了好对⽐,所以我们最好都做⼀下区分。第⼆,对于要排序的数据,有的接近有序,有的完全⽆序。有序度不同的数据,对于排序的执⾏时间肯定是有影响的,我们要知道排序算法在不同数据下的性能表现。

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

我们知道,时间复杂度反应的是数据规模n很⼤的时候的⼀个增⻓趋势,所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中,我们排序的可能是10个、100个、1000个这样规模很⼩的数据,所以,在对同⼀阶时间复杂度的排序算法性能对⽐的时候,我们就要把系数、常数、低阶也考虑进来。

3.⽐较次数和交换(或移动)次数

基于⽐较的排序算法的执⾏过程,会涉及两种操作,⼀种是元素⽐较⼤⼩,另⼀种是元素交换或移动。所以,如果我们在分析排序算法的执⾏效率的时候,应该把⽐较次数和交换(或移动)次数也考虑进去。

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外。

排序算法的稳定性

仅仅⽤执⾏效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法,我们还有⼀个重要的度量指标,稳定性。这个概念是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

我通过⼀个例⼦来解释⼀下。⽐如我们有⼀组数据2,9,3,4,8,3,按照⼤⼩排序之后就是2,3,3,4,8,9。

这组数据⾥有两个3。经过某种排序算法排序之后,如果两个3的前后顺序没有改变,那我们就把这种排序算法叫作稳定的排序算法;如果前后顺序发⽣变化,那对应的排序算法就叫作不稳定的排序算法。

冒泡排序(Bubble Sort)

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进⾏⽐较,看是否满⾜⼤⼩关系要求。如果不满⾜就让它俩互换。⼀次冒泡会让⾄少⼀个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序⼯作。

我⽤⼀个例⼦,带你看下冒泡排序的整个过程。我们要对⼀组数据4,5,6,3,2,1,从⼩到到⼤进⾏排序。第⼀次冒泡操作的详细过程就是这样:

数据结构与算法整理总结---排序

可以看出,经过⼀次冒泡操作之后,6这个元素已经存储在正确的位置上。要想完成所有数据的排序,我们只要进⾏6次这样的冒泡操作就⾏了。

数据结构与算法整理总结---排序

实际上,刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时,说明已经达到完全有序,不⽤再继续执⾏后续的冒泡操作。我这⾥还有另外⼀个例⼦,这⾥⾯给6个元素排序,只需要4次冒泡操作就可以了。

数据结构与算法整理总结---排序

//冒泡排序,$arr表示数组,$n表示数组大小
function bubbleSort($arr,$n){
    if($n<1){
        return false;          
    }
    for($i=0;$i<$n;$i++){
        // 提前退出冒泡循环的标志位 
        $flag = false;
        for($j=0;$j<$n-$i-1;$j++){
            if($arr[$j]>$arr[$j+1]){
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
                $flag = true;
            }
        }
        if(!$flag){
            break;
        }
    }
}

冒泡排序是原地排序算法吗?

冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为O(1),是⼀个原地排序算法。

冒泡排序是稳定的排序算法吗?

在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素⼤⼩相等的时候,我们不做交换,相同⼤⼩的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。

冒泡排序的时间复杂度是多少?

最好情况下,要排序的数据已经是有序的了,我们只需要进⾏⼀次冒泡操作,就可以结束了,所以最好情况时间复杂度是O(n)。⽽最坏的情况是,要排序的数据刚好是倒序排列的,我们需要进⾏n次冒泡操作,所以最坏情况时间复杂度为O(n)。

数据结构与算法整理总结---排序

插⼊排序(Insertion Sort)

我们先来看⼀个问题。⼀个有序的数组,我们往⾥⾯添加⼀个新的数据后,如何继续保持数据有序呢?很简单,我们只要遍历数组,找到数据应该插⼊的位置将其插⼊即可。

数据结构与算法整理总结---排序

这是⼀个动态排序的过程,即动态地往有序集合中添加数据,我们可以通过这种⽅法保持集合中的数据⼀直有序。⽽对于⼀组静态数据,我们也可以借鉴上⾯讲的插⼊⽅法,来进⾏排序,于是就有了插⼊排序算法。

那插⼊排序具体是如何借助上⾯的思想来实现排序的呢?

⾸先,我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有⼀个元素,就是数组的第⼀个元素。插⼊算法的核⼼思想是取未排序区间中的元素,在已排序区间中找到合适的插⼊位置将其插⼊,并保证已排序区间数据⼀直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

如图所示,要排序的数据是4,5,6,1,3,2,其中左侧为已排序区间,右侧是未排序区间。

数据结构与算法整理总结---排序

插⼊排序也包含两种操作,⼀种是元素的⽐较,⼀种是元素的移动。当我们需要将⼀个数据a插⼊到已排序区间时,需要拿a与已排序区间的元素依次⽐较⼤⼩,找到合适的插⼊位置。找到插⼊点之后,我们还需要将插⼊点之后的元素顺序往后移动⼀位,这样才能腾出位置给元素a插⼊。

// 插⼊排序,arr表示数组,n表示数组⼤⼩
function insertionSort($arr,$n){
    if($n<1){
        return false;
    }
    for($i=1;$i<$n;++$i){
        $value = $arr[$i];
        $j=$i-1;
        // 查找插⼊的位置
        for($j=$i-1;$j>=0;--$j){
            if($arr[$j]>$value){
                $arr[$j+1]=$arr[$j];// 数据移动
            }else{
                break;
            }
        }
        $arr[$j+1] = $value; // 插⼊数据
    }
}

插⼊排序是原地排序算法吗?

从实现过程可以很明显地看出,插⼊排序算法的运⾏并不需要额外的存储空间,所以空间复杂度是O(1),也就是说,这是⼀个原地排序算法。

插⼊排序是稳定的排序算法吗?

在插⼊排序中,对于值相同的元素,我们可以选择将后⾯出现的元素,插⼊到前⾯出现元素的后⾯,这样就可以保持原有的前后顺序不变,所以插⼊排序是稳定的排序算法。

插⼊排序的时间复杂度是多少?

如果要排序的数据已经是有序的,我们并不需要搬移任何数据。如果我们从尾到头在有序数据组⾥⾯查找插⼊位置,每次只需要⽐较⼀个数据就能确定插⼊的位置。所以这种情况下,最好是时间复杂度为O(n)。注意,这⾥是从尾到头遍历已经有序的数据。

如果数组是倒序的,每次插⼊都相当于在数组的第⼀个位置插⼊新的数据,所以需要移动⼤量的数据,所以最坏情况时间复杂度为O(n2)。

选择排序(Selection Sort)

选择排序算法的实现思路有点类似插⼊排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最⼩的元素,将其放到已排序区间的末尾。

数据结构与算法整理总结---排序

选择排序空间复杂度为O(1),是⼀种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n2)。

// 插⼊排序,arr表示数组,n表示数组⼤⼩
function SelectionSort($arr,$n){
    if($n<=1){
        return false;
    }
    for($i=0;$i<$n;$i++){
        $value = $arr[$i];
        for($j=$i+1;$j<$n;$j++){
            if($value>$arr[$j]){
                $tmp = $arr[$j];
                $arr[$i] = $arr[$j];
                $arr[$j] = $tmp;
            }
        }
    }
}

选择排序是⼀种不稳定的排序算法。从我前⾯画的那张图中,你可以看出来,选择排序每次都要找剩余未排序元素中的最⼩值,并和前⾯的元素交换位置,这样破坏了稳定性。

⽐如5,8,5,2,9这样⼀组数据,使⽤选择排序算法来排序的话,第⼀次找到最⼩元素2,与第⼀个5交换位置,那第⼀个5和中间的5顺序就变了,所以就不稳定了。正是因此,相对于冒泡排序和插⼊排序,选择排序就稍微逊⾊了。

总结

数据结构与算法整理总结---排序

这三种排序算法,实现代码都⾮常简单,对于⼩规模数据的排序,⽤起来⾮常⾼效。但是在⼤规模数据排序的时候,这个时间复杂度还是稍微有点⾼,所以我们更倾向于⽤下⼀节要讲的时间复杂度为O(nlogn)的排序算法。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!