排序算法

分类

1. 比较类排序

   通过比较来决定元素间 的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。

2. 非比较类排序

   不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称线性时间非比较类排序。

image.png

复杂度

image.png

相关概念

• 稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。

• 不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。

• 时间复杂度：对排序数据的总的操作次数。当 n 变化时，操作次数呈现什么规律。

• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。

初级排序 - O(n^2)

• 选择排序（Selection Sort）

  每次找最小值，然后放到待排序数组的起始位置。

• 插入排序 （Insertion Sort）

  从前到后逐步构建有序序列；对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 冒泡排序（Bubble Sort）

  嵌套循环，每次查看相邻的元素如果逆序，则交换。

高级排序

• 快速排序（Quick Sort）

  数组取标杆 pivot，将小元素放 pivot 左边，大元素放右侧，然后依次对右边和右边的子数组继续快排；以达到整个序列有序。

• 归并排序（Merge Sort）- 分治

  1. 把长度为 n 的输入序列分为两个长度为 n/2 的子序列；

  2. 对这两个字序列分别采用归并排序；

  3. 将两个排序好的子序列合并成一个最终的排序序列。

• 堆排序

  1. 数组元素依次建立小顶堆；

  2. 依次取堆顶元素，并删除。

特殊排序

1. 计数排序（Counting Sort）

   计数排序要求输入的数据必须是有确定范围的整数。将输入的数据值转化为键存储在额外开辟的数组空间中；然后依次把计数大于 1 的填充回原数组。

2. 桶排序（Bucket Sort）

   桶排序（Bucket sort）的工作原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再 分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

3. 基数排序

   基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先 按低优先级排序，再按高优先级排序。

排序动画

• https://www.cnblogs.com/onepixel/p/7674659.html

• https://www.bilibili.com/video/av25136272

• https://www.bilibili.com/video/av63851336

实战题目

• https://leetcode-cn.com/problems/relative-sort-array/

• https://leetcode-cn.com/problems/valid-anagram/

• https://leetcode-cn.com/problems/design-a-leaderboard/

• https://leetcode-cn.com/problems/merge-intervals/

• https://leetcode-cn.com/problems/reverse-pairs/