排序算法(粗略总结,Java实现)

稳定性：如果相同元素的前后相对位置不变，就说这种排序算法是稳定的

插入排序

1. 直接插入排序算法

序列分为两部分，一部分有序，一部分无序，每一趟都从无序的中挑一个插入到有序的序列中，共执行n-1趟
每趟拿到的数一点一点交换往前移动，这样的话遇到相同的数就不移动，算法稳定

for(int i=1; i<keys.length; i++){
    int x = key[i], j;
    for(j=i-1; j>0 && x<key[j]; j--)
        key[j+1] = keys[j];//j元素后移
    keys[j+1] = x;
}

正序序列，时间复杂度O(n)；反序序列，时间复杂度O(n²)
随机排序，等概率情况下为O(n²)

• 改进 增加哨兵位而不是用通过j>0来比较，比较操作在汇编层面更耗时间

• 改进 可以通过二分查找查看有序的那一部分中应该插入到哪儿

• 稳定性 稳定

• 时间复杂度 最好正序O(n)，最坏倒序O(n²)

• 空间复杂度O(1)

希尔排序(缩小增量排序)

分组，增量delta=4，那就每隔4个位一组

38	55	65	97	27	76	27*	13	19
0	1	2	3	4	5	6	7	8
i				i+4				i+4+4

0号和4号和8号比，不符合顺序就交换，1号和5号比较
每一组都分别整理好组内的顺序

下一次delta=2，整理好
下一次delta=1，整理好
排序完成

for(int delta=key.length/2; delta>0; delta/=2){
    for(int i=delta; i<key.length; i++){//这里结束叫“一趟”，一趟过后的特点是，分组有序
        int x = key[i];
        for(int j=i-delta; j>=0 && x<key[j]; j-=delta)
            key[j+delta] = key[j];//后移
        key[j+delta] = x;
    }
}

凭啥这种方式能排序更快？
这种排序每个元素需要归位的话，他每一次能移动的更多，腿更长，变量能够“大跨步地向这更加正确的方向运动”

• 稳定性 算法不稳定， 跨步交换的过程可能会交换两个相同元素的相对位置
• 时间复杂度 比较复杂
• 空间复杂度O(1)

冒泡排序

从前到后，相邻两个比较，不符合顺序就交换，每一趟能归位一个

和插入排序的区别
插入排序是依次移动变量，冒泡是依次交换变量
插入的前面是排好序的序列，插入的后面是排好序的序列

• 改进 如果有一趟没有交换，那么就停止算法，序列已经满足顺序，使用一个布尔型变量标记这一趟有没有交换

• 稳定性 如果相等不交换，那么相对位置不变

• 时间复杂度 最好O(n)，最坏O(n²)

• 空间复杂度O(1)

快速排序（重点）

设置基准值，大于基准值的和小于基准值的各分一组，这两组分别找基准值，分组……
当一组只有一个就是排序成功

怎么分组？
通过两个指针前后相对运动来分两组，前后顺序不对就交换

切记前后两个指针，一趟过后判断序列的时候，两个指针分别走i先j后，所得序列和原序列完全无关

• 稳定性 不稳定，有跨越，可能导致跳过相同的值
• 时间复杂度 最好每一次都分成长度相近的两个子序列O(nlog₂n)，最坏每一趟都分成差异很大的两个子序列O(n²)相当于普通排序
• 空间复杂度 O(1)

选择排序

每一趟选择未被排序的序列中最大的元素放到最后，每趟归位一个
n-1趟

• 稳定性 不稳定，会跳跃
• 时间复杂度 O(n²)
• 空间复杂度O(1)

堆排序

第一次构建堆麻烦一些，但是构建好之后，取出堆首元素，堆尾元素放到堆首，然后往下滑(不止滑一步)，初次构建时候建议也搞成滑动操作，而不是简单的交换操作，每一个结点都往下滑动

完全二叉树，用数组模拟，索引从0开始的话，每一个结点index*2+1就是左孩子结点，array.length/2-1就是第一个非叶子结点

• 稳定性 不稳定，会跳跃
• 时间复杂度 O(nlog₂n)
• 空间复杂度O(1)

归并排序

基础操作是合并两个已经排序的序列(双指针)
两两一组，排序，每两个组合并…，最后只剩下一个组

• 时间复杂度一共排序合并log₂n次，每一次操作次数都是n，时间复杂度为O(nlog₂n)

做题总结

• 选择排序、冒泡排序、堆排序，每一趟都能够归位一个，插入排序不能归位，只能是一个有序的序列，最小的和最大的都可能开没出现。
• 排序趟数和原始排序有关：
• • 插入排序(要通过反复比较选择插入位置)
• • 冒泡排序(一次过后没有交换就说明排好了)
• • 快速排序(要是很有序的话，每一次全部序列都在一边，没法分成两半)