数学系C++ 排序算法简述（八）

目录

排序

选择排序 O(n2)

不稳定：48429

归并排序 O(n log n) 稳定

插入排序 O(n2)

堆排序 O(n log n)

希尔排序 O(n log2 n)

图书馆排序 O(n log n)

冒泡排序 O(n2)

优化：

基数排序 O(n · k)

快速排序 O(n log n)【分治】 不稳定

桶排序 O(n + k)

计数排序 O(n + k)

鸽巢排序 O(n + D)

---

排序

什么是稳定排序算法：数据先后次序不变

选择排序 O(n2) 归并排序 O(n log n)插入排序 O(n2) 堆排序 O(n log n)希尔排序 O(n log2 n) 图书馆排序 O(n log n)冒泡排序 O(n2) 基数排序 O(n · k)快速排序 O(n log n) 桶排序 O(n + k)计数排序 O(n + k)鸽巢排序 O(n + D)：

选择排序 O(n2)

► 先找出最小值，将其与第一个位置的元素进行交换

► 对剩余的数据重复以上过程，直至排序结束

不稳定：48429

归并排序 O(n log n) 稳定

归并：如果有两个分别有序的数组，可以用双指针合并成一个完全有序的数组

可以递归写

也可以从0开始

归并1-1  1-1  1-1  1-1

归并   2-2          2-2

归并         4-4

完成！

插入排序 O(n2)

假设前面 k 个元素已经按顺序排好了，在排第 k+1个元素时，将其插入到前面已排好的 k 个元素中，使得插入后得到的 k+1 个元素组成的序列仍按值有序。

堆排序 O(n log n)

希尔排序 O(n log2 n)

基本过程描述如下：

① 把序列按照某个增量（gap）分成几个子序列，对这几个子序列进行插入排序。

② 不断缩小增量，扩大每个子序列的元素数量，并对每个子序列进行插入排序。

③ 当增量为 1 时，子序列就是整个序列，而此时序列已经基本有序了，因此只需做少量的比较和移动就可以完成对整个序列的排序

出发点：插入排序在元素基本有序的情况下，效率很高。

gap：初始值设为 n/2，然后不断减半。

图书馆排序 O(n log n)

冒泡排序 O(n2)

► 走访需要排序的序列，比较相邻的两个元素，如果他们的顺序错误就把他们交换过来。

► 不断重复上述过程，直到没有元素需要交换

具体过程：

► 将第 1 个和第 2 个元素进行比较，如果前者大于后者，则交换两者 的位置，否则位置不变；然后将第 2 个元素与第 3 个元素进行比较， 如果前者大于后者，则交换两者的位置，否则位置不变；依此类推， 直到最后两个元素比较完毕为止。这就是第一轮冒泡过程，这个过程 结束后，最大的元素就“浮”到了最后一个位置上。

► 对前面 n-1 个元素进行第二轮冒泡排序，结束后，这 n-1 个元素中 的最大值就被安放在了第 n-1个位置上。

……执行n-1轮

优化：

简单优化：

如果在某轮冒泡过程中没有发生元素交换，这说明整个序列已经排好序了，这时就不用再进行后面的冒泡过程，可以直接结束程序

进一步优化：

假设有 100 个数组成的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一轮冒泡过程后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二轮遍历是只要到这个位置就可以了。记录每轮遍历最后发生交换的位置，下次遍历只需到此位置为止

基数排序 O(n · k)

先排个位，再排十位，再排百味（30次）

快速排序 O(n log n)【分治】 不稳定

快速排序采用的是分而治之思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题，然后递归求解这些子问题，最后将这些子问题的解组合为原问题的解

1.以第一个元素为基准书，使得基准书左边只有比他小的，右边只有比他大的

2.然后对基准书两边的数组分别进行操作1

分治：分成相同的子问题，用递归求解；子问题相互独立

dp：子问题不一定相同，具有最优子结构；子问题相互依赖

桶排序 O(n + k)

计数排序 O(n + k)

鸽巢排序 O(n + D)