toukii.github.io

排序算法总结

常用的排序算法有：

选择排序
插入排序
冒泡排序

归并排序
快速排序
希尔排序
堆排序

计数排序
桶排序
基数排序

不稳定排序算法有：选择排序，快速排序，希尔排序，堆排序。

排序算法实现见base-sortcode

选择排序

每次从未排序数组元素中选择最值，最值与未排序数组的首个元素交互位置。因其会导致数组元素位置错乱（相同元素不能保证顺序），故是不稳定排序。 算法复杂度：O(n*n)

插入排序

将待排序元素插入到已排序的数组中，一般从已排序元素的末尾开始比较，直到将其移动到前后值大小合适的位置。

1. 查找在已排序中的位置，可以使用二分法快速查找；
2. 移动元素可以批量移动 copy(dst, src) 算法复杂度：O(n*n)

冒泡排序

比较相邻元素的大小，并交换位置。数组将逐渐趋于有序。当在一次比较过程中没有发生交换，则排序结束。 算法复杂度：O(n*n)

归并排序

分而治之。将待排序部分分为若干个待排序的小部分，对每一部分采用一种排序算法，最后合并已排序的部分。 快速排序、希尔排序、桶排序都使用了分而治之的思想。 算法复杂度：O(n*logn)

快速排序

选择一个轴(pivot)元素，将待排序数组分为左右两部分，使得左边元素都不大于pivot，右边元素都不小于pivot，这样一轮排序结束； 继续重复以上步骤，分别对左侧和右侧数据排序。

1. 如果重复元素较多，可以将数组分为左、中、右三部分，中间部分的元素值等于pivot。
2. pivot的选择是可以优化的地方，可以是待排序部分的首个元素，或取中间位置的元素，或取随机位置元素；一般而言，随机位置更好。快排对随机数据效果较好。 算法复杂度：O(n*logn) 基本有序的数组用快排，算法复杂度退化为O(n*n)。

希尔排序

分而治之，每一次排序将待排序部分按照步长划分为n个待排序部分，待排序部分可以按照插入排序或其他排序算法。 步长最好为 7，5，3，1这种。最后的步长是1就完成了排序。

1. 基本有序，插入排序和冒泡排序是高效的，一般希尔排序底层使用插入排序。
2. 希尔排序是逐渐让数组趋于有序。 跳跃式的插入，使得该算法为不稳定排序。

堆排序

堆排序中的堆可分为大顶堆、小顶堆。 大顶堆的特性是: a[i]>=a[2*i+1] 并且 a[i]>=a[2*i+2]，即 我们虚构了一颗二叉树，所有非叶子节点的值不小于其左右子树中元素值；反之为小顶堆。 每次把堆顶元素移走（移到已排序队列），需要调整堆，调整后满足这个特性。

1. 将堆顶元素移走是和待排序数组的最后一位元素交换，交换后调整堆。
2. 升序使用大顶堆，降序使用小顶堆。

计数排序

以空间换时间，申请 max-min个int内存，每个int存储数组元素重复次数，内存块下标就是数组元素。 算法复杂度：O(n)，但是数组元素个数被放大了，可能是n的好多倍！

桶排序

改进计数排序，不申请大量内存，将数组元素哈希分配到x个桶，对桶内的元素进行其他排序算法。

基数排序

把数组元素依次对个位放到10*n的二维数组中，如28放到下标为8的数组里 a[8][...];然后依次处理十位、百位...，直到所有的元素都放到a[0][...]里。 算法复杂度：O(kn)

维护排序空间

选择排序、插入排序、堆排序都是维护了一个排序空间（到排序结束也不会改变），逐渐扩大这个排序空间。所以对选取最大k个数可以考虑这种算法。 选取最大k个数，可以维护一个k个元素的空间，尝试将数组元素放入到k个元素中。