1. 排序算法

1.1. 稳定性

能保证排序前两个相等的数在排序后顺序不变, 则是稳定的

1.1.1. 好处

排序算法如果是稳定的, 那么从一个键上排序, 然后再从另一个键上排序, 第一个键的结果可以为第二个键排序所用.

1.1.2. 稳定性分析

冒泡排序: 稳定的
- 相邻两个数两两比较, 相同时一般不会交换, 所以稳定
选择排序: 不稳定
- 每次循环找到最小的数, 与当前循环次数下标交换位置, 会将原位置的数替换过来, 所以是不稳定的
插入排序: 稳定的
- 每个元素往前对比, 比左边小则交换, 否则停止, 遇到相同的数时不会交换, 所以稳定
快速排序: 不稳定
- 分为 left, right 时, 与指标相同的数可能被分到左边, 也可能分到右边, 导致顺序变更
- 优化
  1. 用于比较值的选取, 可以取开始, 中间, 结尾三个数进行比较, 然后取中间值作为比较值
  2. 处理重复元素问题: 可以将数据分为三块, 比p小, 等于p, 比p大
  3. 处理小数组效率, 小数组用选择排序来排序
  4. 用循环代替递归
  5. 并行计算
归并排序: 稳定的
希尔排序: 不稳定的
堆排序: 不稳定
- 初始化建堆时间复杂度: O(n)
- 更改元素后重建堆时间: O(nLogN)
- 原地排序空间复杂度: O(1)
- 插入删除元素的时间复杂度都是: O(logN)

1.2. 外排序有哪些

归并排序
桶排序
堆排序

1.2.1. 常见外排序用途

学生成绩, 年龄等小范围数量有限的: 使用计数排序
随机数: 归并排序
d位数, 每个数位有k个取值: 基数排序
被排序数在某个范围内, 且服从均匀分布: 桶排序

1.2.2. 流程

假设: 1G数据, 100m内存

读入 100m 至数据内, 使用外排序在内存中完成排序
将排序完成的数据写入磁盘
重复步骤1, 2直到所有数据都存入了不同的 100m 的块 (临时文件中)
读入每个临时文件(顺串)的前 10m 的数据放到内存中的输入缓冲取, 最后的 10m 作为输出缓冲区.
[多路合并, 提高效率]执行10路归并算法, 将结果输出到缓冲区中, 一旦缓冲区满, 将缓冲区中的数据写到目标文件, 清空缓冲区, 一旦10个输入缓冲区中的一个变空, 就从这个缓冲区关联的文件中读入下一个10m数据,除非这个文件已经读完.

1.2.3. 优化

并行计算
- 多磁盘处理数据, 加快磁盘读写速度
- 使用多线程处理, 利用多核心
- 异步输入输出, 可以同时排序和归并, 同时是读写
- 多台计算机分担计算任务
提高硬件速度
- 增加内存, 减小磁盘读写速度, 减小归并次数
- 使用快速的外存设备, 比如固态
- 使用更多核心 CPU
提高软件速度
- 对于特殊的数据, 在第一步中使用特定的排序算法
- 压缩输入输出文件和临时文件

1.3. 排序算法

1.3.1. 快排

思路: 在数组中选择一个数作为比较数p, 然后双指针指向数组左右 l, r, r从右向左遍历, 找到第一个比 p 小的数, l 从左向右遍历, 找到第一个比 p 大的数, 找到后交换 l, r 的值. 当 l >= r 时, 交换 p 和 l, 一趟排序完成. 然后递归排序 [start, l-1), (l+1, end]. 递归完成则排序完成.

代码:

func quickSort(arr []int, start, end int) {
    if start >= end {
        return
    }
    // 取比较点
    p := arr[start]
    l, r := start, end
    for l < r {
        // 先从右侧找小于p的数, 
        for l < r && arr[r] >= p {
            r--
        }
        for l < r && arr[l] <= p {
            l++
        }
        if l < r {
            arr[l], arr[r] = arr[r], arr[l]
        }
    }
    arr[l], arr[start] = arr[start], arr[l]
    quickSort(arr, start, l-1)
    quickSort(arr, l+1, end)
}

排序