数学系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：子问题不一定相同，具有最优子结构；子问题相互依赖