排序问题

讲讲排序问题.

常见的排序算法有冒泡排序, 归并排序, 快速排序, 桶排序等. 这里都不会讲因为到处都有. 大致掌握排序算法后, 只要定义元素的大小比较方式, 不管什么高级编程语言基本上都可以直接调用sort函数求解.

基数排序和桶排序

基数排序是对传统桶排序的扩展, 速度很快.
基数排序也是搞一堆的桶, 从低位开始每次根据这轮的比较位放到相应的桶里面然后按顺序拿出来, 这一位就排好了.

时间复杂度是 O(M+N) 空间复杂度 O(MN) m是保存桶的元素个数数组占的空间, n是保存桶的二维数组占的空间.

稳定排序

如果相同的元素排序之后顺序保证不变, 则排序算法是稳定的.

冒泡排序, 插入排序, 基数排序, 归并排序等都是稳定排序.

快速排序是稳定的吗?原始的快速排序算法是不稳定的. 因为如果选定的轴(pivot)有相同元素, 按照规则 把大于等于轴的元素放到右边小于轴的元素放到左边 那相同的其余元素都得到右边去了, 因此快速排序不是稳定的.

我们讨论快速排序, 往往就想到分治法且每一步把大于等于轴的元素放到右边小于轴的元素放到左边就完事了. 但是至于怎么把元素放到对应的左右, 值得注意. 在分治的一个区间 [i,j] 中, 我们随便找个轴(不妨就拿最后一个元素), 然后考虑剩下的元素. 我们有两个cursor分别指向剩余元素的头尾, 相向移动知道相遇. 我们希望左边的元素总比轴小, 右边总比轴大. 遇到违背规则的位置时我们就停下, 等到另一个光标检测到违背的数. 此时我们交换两个cursor指向的元素, 则此时两边都不违背规则, 指针可以继续移动了. 最后我们把轴放到中间正确的位置, 一次整理就完成了.

我们一开始想着或许可以修改规则来维持稳定, 比如我让左边执行小于等于规则, 右边执行小于规则, 是不是轴就稳定了呢?非也!这样的思路没考虑到元素互换这一步, 以及元素互换也会搞乱相同值的顺序.

有人说那我不要互换了开个新的数组存元素是不是就稳定了呢?是的!但是没有意义!快速排序要的就是单倍空间, 开新数组就成了双倍空间了, 我为什么不用归并排序?所以分析算法要考虑到原始的意义.

快速排序和归并排序最差情况下时间复杂的是 O(n^2).

原地重排(in-situ permutation)

原地(原址、就地)排序是指:基本上不需要额外辅助的的空间, 允许少量额外的辅助变量进行的排序. 就是在原来的排序数组中比较和交换的排序. 像选择排序, 插入排序, 希尔排序, 快速排序, 堆排序等都会有一项比较且交换操作(swap(i,j))的逻辑在其中, 因此他们都是属于原地(原址、就地)排序, 而合并排序, 计数排序, 基数排序等不是原地排序.

第二个问题叫做排序索引(argsort)

如果我不是要得到原先数据排好序的结果, 而是只要获得原先数据大小顺序的索引, 这个问题就是 argsort. 最终返回的数组是 A = [0,1,2,...,len(arr)-1], 表示 arr 中第i小的数在A[i]位置上. 如果只是为了实现这样的功能, 算法上不是特别复杂. 考虑到 indirection 的想法, 只要对原先的排序算法略加修改, 在排序时并不真正移动数据, 而是记录索引的改变, 并在取数据时增加用索引取得, 则大体上时间复杂度应该是一致的.

python 中可以使用 numpy.argsort()函数

排名问题 (rank)

这个问题要求的是数组的排名, 即数组中第i个元素是第几大的. 考虑到索引排序已经得到了第i大的元素是第几个, 其实这个问题就是 argsort 的 K-V 互换.

记一次argsort的结果为A, 两次argsort的结果为B. 则A[i]表示 原数组中第i小的元素的索引是A[i], 原先索引为 A[i] 的数应当是第 i 小的.

所求的sort数组中, 应该把 j 放在 A[j] 位置上.

由于A数组中的元素就是 [0,1,2,...,len(arr)-1], 所以第 j 小的元素值就是 j, B[j] 表示 A 第 j 小的数的位置, 也就是 A 中数值 j 的位置. 这样恰好满足 K-V 互换, 于是两次 argsort 得到的就是 sort 的结果.

这里的巧妙之处在于 所以第 j 小的元素值就是 j, 多做了一次于是又回来了. 看着有点绕其实也真的有点绕.

分析一下复杂度

每个元素通过索引取得的时间假设为 O(1). 第一次索引排序的时间做到 O(nlogn) 是没问题的, 因为增加一次间接的时间都可以看作常数.

第二次是在一个给定范围的数组上做原地排序(感觉是没仔细想)

如果不考虑空间复杂度, K-V互换的时间可以是 O(n) 的, 搞个桶排序直接塞回去就好了.

若是一定要原地, 不能占用双倍空间, 我还没想好, 但是反正总体复杂度肯定是 O(nlogn).