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

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

• 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)

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

# 其中 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)。