《数据结构与算法-王争》学习笔记,记录备查

排序是我们最常用接触最早的算法,经典常用的排序算法有:

  • O(n^2): 冒泡排序、插入排序、选择排序
  • O(nlogn): 快速排序、归并排序
  • O(n): 桶排序、计数排序、基数排序

学习排序算法,我们除了学习算法原理、代码实现外,还要掌握如何评价、分析一个排序算法。

如何分析一个排序算法

排序算法的执行效率

1、三种时间复杂度:最好情况、最坏情况、平均情况时间复杂度。

  • 有些排序算法区分这三种时间复杂度。
  • 不同数据形式,有序无序对排序算法也是有影响的,要从三种时间复杂度去看。

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

  • 不同的数据规模对排序算法影响较大。

3、比较次数和交换(或移动)次数。

  • 排序算法,基于比较的算法较多,比较次数和交换移动次数,也会影响执行效率。

排序算法的内存消耗

内存消耗,可以使用空间复杂度来衡量。

空间复杂度底的排序算法,自然更好。我们把空间复杂度为O(1)的排序算法叫做 原地排序

排序算法的稳定性

稳定性是说,如果待排序的序列中存在值相等的元素,经过排序后,相等元素之间的先后顺序不变。

稳定的排序算法,常被用来在进行多次才能获取结果的排序中。这样就可以保持上次排序的关键词的顺序。

经典排序算法

冒泡排序(Bubble Sort)

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

冒泡排序针对有一定顺序的序列时,只要没有可以交换元素时,即说明排序完成。

  • 原地排序
  • 稳定的排序算法
  • 最好时间复杂度:O(n) 最坏时间复杂度:O(n^2) 平均时间复杂度:O(n^2)

我们可以使用有序度逆序度来推导平均时间复杂度。

有序度:数组中具有优先关系的元素对的个数。默认从小到大为有序。 逆序度:也是元素对,顺序与有序度正好相反。

对于一个倒叙排列的数组,有序度是0;对于一个完全有序的数组,有序度为 n*(n-1)/2。我们把这种完全有序的数据的有序度叫做**满有序度**。这几个概念有个公式:

逆序度=满有序度-有序度

有序度,是序列的初始状态,没交换一个元素,有序度加1,逆序度减1。最终达到满有序度,结束。换句话说,交换次数就等于逆序度,根据公式得出:

交换次数 = n(n-1)/2 - 有序度*

交换次数,最好的情况下为0 ,最坏的情况下为 n*(n-1)/2 。取平均值为 n*(n-1)/4。比较次数远大于交换次数,所以也是平方级别的,且上限为 O(n^2)。

冒泡排序的复杂度,主要取决于比较和交换的复杂度,根据平均情况,忽略系数我们得到平均复杂度为 O(n^2)。

插入排序(Insertion Sort)

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

  • 原地排序(空间复杂度为O(1))
  • 稳定排序(插入时,人为控制保持相同元素出现先后,插入前或后)
  • 最好时间复杂度:O(n) 最坏时间复杂度: O(n^2) 平均时间复杂度:O(n^2)

插入排序,是根据比较和移动元素的次数推断出来的时间复杂度,和冒泡排序相同。

选择排序(Selection Sort)

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

  • 原地排序(空间复杂度为O(1))
  • 不稳定排序(排序时,只能放到已排序区间的队尾,当相同元素在队尾时,就需要交换,前后顺序就变了, 如序列:5,8,5,2,9)
  • 最好时间复杂度:O(n) 最坏时间复杂度: O(n^2) 平均时间复杂度:O(n^2)

时间复杂度分析同冒泡、插入排序。

插入排序和选择排序,都分已排和未排区间。区别在于,插入排序是在插入已排区间时,进行比较,从而找到合适位置插入。选择排序,是在未排区域取数据时比较,从而找到最小值,且只能插入到已排区域的末尾。

归并排序(Merge Sort)

归并排序,把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

归并排序是使用了分治思想。分治是一种解决问题的处理思想,递归是一种编程技巧。

归并排序,拆分之后,在合并的同时进行排序。利用相同空间的暂存数组,依次从拆分的序列中取元素比较,小的入临时数组,直到一个拆分元素全部完成。

  • 非原地排序, 因为需要合并数组,使用了额外的存储空间。
  • 稳定排序。在合并数组时,我们可以人为的控制相同元素的顺序。
  • 归并排序,每次合并都需要申请,一个临时的数组空间。但是,任何时间在CPU中只有一个临时空间在用。所以,归并排序的空间复杂度是O(n)。
  • 归并排序和原始数组的有序程度无关,最好、最坏、平均时间复杂度都是 O(nlogn)

归并排序是使用递归方法来实现排序的,时间复杂度也可以使用递归的推导式来标识:

1
2
3
4
5
6
# 其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间
T(a) = T(b) + T(c) + K

# 递归得出
T(1) = C;   n=1时,只需要常量级的执行时间,所以表示为C。
T(n) = 2*T(n/2) + n; n>1

最后计算得出,时间复杂度为 O(nlogn)

快速排序(Quick Sort)

如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点,一般选择下标为r的元素)。我们通过游标 i 把 A[p…r-1]分成两部分。A[p…i-1]的元素都是小于 pivot 的,我们暂且叫它“已处理区间”,A[i…r-1]是“未处理区间”。我们每次都从未处理的区间 A[i…r-1]中取一个元素 A[j],与 pivot 对比,如果小于 pivot,则将其加入到已处理区间的尾部,也就是 A[i]的位置。一轮处理完成,再继续处理privot前后的区域。

快速排序和归并排序区别,快速排序是自上而下的处理顺序,归并排序是自下而上的处理顺序。

  • 原地排序
  • 非稳定排序
  • 空间复杂度为:O(1)
  • 时间复杂度:最好为 O(nlogn) 最坏 O(n^2) 平均 O(nlogn)~O(n^2)(极小概率)

分治思想应用

解决在一组数组中查找第K大的元素

普通解法:

依次比较,将最大元素放到数组最前边,第K个元素就是第K大的元素。时间复杂度为 O(K*n),当K 足够大的时候,退化为 O(n^2)。

分治思想解法:

我们选择数组区间 A[0…n-1]的最后一个元素 A[n-1]作为 pivot,对数组 A[0…n-1]原地分区,这样数组就分成了三部分,A[0…p-1]、A[p]、A[p+1…n-1]。如果 p+1=K,那 A[p]就是要求解的元素(排序是从大到小);如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1]区间,我们再按照上面的思路递归地在 A[p+1…n-1]这个区间内查找。同理,如果 K < P+1, 那么我们就在A[0…p-1]区间继续查找。

时间复杂度为O(nlogn)。