Sort

BubbleSort&SelectionSort

InsertionSort

MergeSort

quickSort

基数排序

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）	О（ $n^{2}$ ）	О（ $n^{2}$ ）		稳定
选择排序	О（ $n^{2}$ ）	О（ $n^{2}$ ）	О（ $n^{2}$ ）
堆排序			О（ nlogn ）	就地算法
插入排序	О（n）	О（ $n^{2}$ ）		就地算法	稳定	减而治之
归并排序					稳定	分治策略
快速排序	О（ nlogn ）	О（ $n^{2}$ ）	О（ 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:
抓扑克牌时人们常用的排序方法：____