Sort
目录
BubbleSort&SelectionSort
起泡排序：
- 无序向量。位置毗邻，就像气泡，那选择最大值排序就是打水漂了。
- 给定n个可比较的元素，按非降序排列，依次比较每一对相邻的元素，第一趟扫描完成后最大的元素被交换到向量尾部，直到整趟扫描都没有发生交换，则排序完成。
- 如果每个元素都是逆序，那么一个元素最坏迭代n次，所以最坏时间复杂度是O（n^2）；如果每个元素都是顺序，那么只需要比较n-1次，故最好时间复杂度是O（n），平均时间复杂度是O（n^2）。
每趟扫描交换最坏情况下都会比较n次，交换n次，其实质是将找到当前最大元素M并排到尾部，而且交换后的向量还是无序的，所以为什么不直接在经过O（n）次比较后将M放到尾部。例如上滤操作，懒惰删除？
而选择排序是无序列表里的算法，选择最大的元素排到最后，selectMax（）算法执行一次复杂度是O（n），一共迭代n次，所以时间复杂度是O（n^2）,没有最好最坏之说。
InsertionSort
- 就地算法，稳定，将当前元素与前缀有序子序列里的元素挨个比较，最坏时间复杂度是O（n^2），最好时间复杂度是O（n），平均时间复杂度是O（n^2）。
- 选择排序是无序里面找出最大的元素放到有序的后面（这样就是从大到小?）；插入排序是从无序里面拿出最前面的元素，插入到有序里面还是有序。前者跟无序序列比较后插入，后者跟有序序列比较后再插入（再套一个二分查找？会不会更快）
MergeSort & quickSort
归并排序：
- 稳定,空间复杂度O(n),T(n)=O(log n)
- 有序子向量排序需要时间，而划分子向量只需О（ 1 ）；
快速排序
- 不稳定的。就地实现。O(nlogn)
- 划分子向量，找出pivot轴点需要时间，而有序子向量排序只需О（ 1 ）；
基数排序
稳定的
轴点：插值查找，快速排序。
堆排序
锦标赛树
|
| 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 | 算法思想 |
|---|---|---|---|---|---|---|
| 起泡排序 | О（n） | О（ | О（ | 稳定 | ||
| 选择排序 | О（ | О（ | О（ | |||
| 堆排序 | О（ nlogn ） | 就地算法 | ||||
| 插入排序 | О（n） | О（ | 就地算法 | 稳定 | 减而治之 | |
| 归并排序 | 稳定 | 分治策略 | ||||
| 快速排序 | О（ nlogn ） | О（ | О（ nlogn ） | 不稳定 | 分治策略 | |
| 基数排序 | 稳定 | |||||
| 锦标赛树 | О（ nlogn ） | |||||
-
排序里面又用到了查找。选择排序：二分查找、顺序查找
-
A,quicksort 快速排序
-
B,radixsort 基数排序
-
C,countsort 计数排序
-
D,heapsort 堆排序
-
E,mergesort 归并排序
-
F,insestsort 插入排序
-
G,shellsort 希尔排序
-
H,bubblesort 冒泡排序
Repeatedly compare adjacent elements, swapping them if they are in reverse order until ordered:
反复比较相邻元素，若为逆序则交换，直至有序：____
The original sequence is divided into two parts with the pivot as the boundary. Recursively sort them separately:
将原序列以轴点为界分为两部分，递归地对它们分别排序____
Sort the first half and the second half of the original sequence, and merge the two parts:
将原序列前半部分和后半部分，分别排序，再将这两部分合并：____
Constantly remove the smallest element from the original sequence:
不断从原序列中取出最小元素：____
The elements in the original sequence are a range of integers, the sorting result can be obtained by calculating the number of occurrences of each possible integer:
原序列中的元素是一定范围内的整数，计算每个可能的整数在其中出现的次数，便可得排序结果____
The sorting method people usually use when playing cards:
抓扑克牌时人们常用的排序方法：____
