数据结构-排序思想

直接插入排序

将后面的无序区中的元素挨个向前面的有序区中插入。
1.将顺序表中R[0]用作哨兵，按索引i=2...n的次序，将R[i]向有序区R[1...i-1]中执行插入操作。
2.插入操作可采取在有序区中从后向前的查找比较和移动的方法。
3.此操作中比较的次数与原序列的排列状态有关：
原序列为正序时在插入操作中插入位置为尾部即只需要比较一次；
原序列为反序时插入位置为头部则需要和有序序列中的每个元素比较一次。

时间复杂度：正序时O(n)，反序时 O(n²)，平均时间复杂度 O(n²)
空间复杂度：O(1)，就地排序
直接插入排序是稳定的。

希尔排序（分组插入排序）

1.把序列分为d个组，分组方法为所有距离为d的元素划到一个组内。
2.各组内进行直接插入排序。
3.按照避免增量序列中的值互为倍数，及最后一个增量必须为1的原则，设定增量序列d。

希尔排序是不稳定的。

冒泡（交换）排序

1.从下面无序区的最底部元素开始向上两两比较，最小者交换到无序区的最顶部，它同时也处了在有序区的最底部。
2.当某一趟扫描中的两两比较未出现交换，则说明无序区已全部有序，排序结束。

时间复杂度：正序时O(n)，反序时 O(n²)，平均时间复杂度 O(n²)
空间复杂度：属于就地排序
冒泡排序是稳定的。性能低于直接插入排序。

快速（交换）排序（基准分冶）

1.确定基准
在区间R中可随机选择一个元素作为基准，和R[0]交换位置。
2.对比划分
以R[0]作为基准做一趟划分操作：从区间两端开始向中间依次交替与基准比较大，根据小在左侧、大在右侧的规则与基准交换位置，最终生成比基准值小和大的左右两个无序的子区间。
3.递归
对每个子区间递归定基准-划分过程。

划分操作结果中有一个子区间为空，及两个子区间都不为空，这两种情况比较，前者整体排序中做的比较次数更多。

时间复杂度：最好 O(nlgn)，最坏 O(n²)，平均 O(nlgn)
空间复杂度：O(lgn)
快速排序是不稳定的。

直接选择排序

1.从后面的无序区中选择最小的元素，与无序区头部元素交换，即有序区末尾增加一个元素。
2.对新的有序区和无序区执行上一步操作。

时间复杂度：O(n²)
空间复杂度：O(1)，就地排序
直接选择排序是不稳定的。

插入排序是先在指定位置取元素，然后再找合适的位置插入，重心在第二步的插入。
选择排序是先找最小的元素，然后交换到指定位置，重心在第一步的选择。

堆排序（树形选择排序）

调整堆（筛选）：判断调整根子树，将根与两个孩子中较大者（大根堆）交换，继而判断调整有变动的子子树。

1.构造堆
从下往上依次对位置为[n/2]...1为根的子树做调整堆操作。
结果构造出了堆，此时只是符合堆性质，但并不有序。
2.将堆根元素交换到无序区尾部。
i为本次调整的序号，将堆顶元素R[1]和最后一个元素R[n-i+1]交换，则新的无序区变为R[1...n-i]，有序区为R[n-i+1,n]。
3.重建堆
对新的无序区判断调整堆。
4.重复2、3步骤共n-1次。

时间复杂度：O(nlgn)
空间复杂度：O(1)，就地排序
堆排序是不稳定的。

归并排序（二路归并排序）

1.将区间内的元素两两做二路归并。
2.将上一步形成的各个有序组两两做二路归并。
3.直至全部元素进入同一个有序组。
4.二路归并需要同等的辅助空间。

时间复杂度：O(nlgn)
空间复杂度：O(n)，
归并排序是稳定的。

以上基于关键字比较的排序时间下限是O(nlgn)，而分配排序无须比较关键字，通过分配和收集过来实现排序，它们的时间复杂度可以下破到线性阶O(n)。

箱排序（桶排序）

分配排序不基于关键字比较，而是通过分配和收集过程实现排序。时间复杂度可达线性阶。
第一种箱排序是设置箱子个数和关键字的种类的个数相同；
第二种桶排序是关键字映射到某个桶中，桶中的所有元素再单独做关键字比较排序

基数排序

基数排序要求分析关键字的结构，分为多关键字和单关键字，每个关键字又由多个位组成。
单关键字的每位即每个分量可能取值个数称为基数，
基数排序是按基数的个数次数从低位到高位对序列元素进行箱排序，每箱排序的结果作为下一趟排序的输入。

基数排序是稳定的。