几种最经典、最常用的排序方法：

冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

对于排序算法执行效率的分析，我们一般会从这几个方面来衡量：

1. 最好情况、最坏情况、平均情况时间复杂度

2. 时间复杂度的系数、常数 、低阶

3. 比较次数和交换（或移动）次数

排序算法的稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

【冒泡排序（Bubble Sort）】

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

• Q:第一，冒泡排序是原地排序算法吗？

A:冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。

• Q:第二，冒泡排序是稳定的排序算法吗？

A:在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

• Q:第三，冒泡排序的时间复杂度是多少？

最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n²)。

【插入排序（Insertion Sort）】

我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

• 空间复杂度：插入排序是原地排序算法。

• 时间复杂度：1. 最好情况：O(n)。2. 最坏情况：O(n^2)。3. 平均情况：O(n^2)

• 稳定性：插入排序是稳定的排序算法。

【选择排序（Selection Sort）】

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

• 选择排序空间复杂度为 O(1)，是一种原地排序算法。

• 选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n²)。

• 选择排序是一种不稳定的排序算法。

冒泡排序和插入排序的时间复杂度都是 O(n²)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3 个赋值操作，而插入排序只需要 1 个。

如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素？需要用到两种时间复杂度为 O(nlogn) 的排序算法：归并排序和快速排序。这两种排序算法适合大规模的数据排序。

【归并排序（Merge Sort）】

如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序使用的就是分治思想。分治算法一般都是用递归来实现的。（分治是一种解决问题的处理思想，递归是一种编程技巧）

• 归并排序是一个稳定的排序算法。

• 归并排序的时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。

• 但是，归并排序不是原地排序算法，归并排序的空间复杂度是 O(n)。（因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间）

【快速排序（Quicksort）】

快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

• 快排是一种原地、不稳定的排序算法。

• 快排的时间复杂度也是 O(nlogn)

        归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是 O(n)。正因为此，它也没有快排应用广泛。

快速排序算法虽然最坏情况下的时间复杂度是 O(n )，但是平均情况下时间复杂度都是O(nlogn)。不仅如此，快速排序算法时间复杂度退化到 O(n ) 的概率非常小，我们可以通过合理地选择 pivot 来避免这种情况。

        三种时间复杂度是 O(n) 的排序算法：桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。

【桶排序（Bucket sort）】

        将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

        桶排序对要排序数据的要求是非常苛刻的。首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

        桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

【计数排序（Counting sort）—— 其实是桶排序的一种特殊情况】

        当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间

        计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

问题：如何根据年龄给100万用户数据排序？

我们假设年龄的范围最小 1 岁，最大不超过 120 岁。我们可以遍历这 100 万用户，根据年龄将其划分到这 120个桶里，然后依次顺序遍历这 120 个桶中的元素。这样就得到了按照年龄排序的 100 万用户数据。

【基数排序（Radix sort）】

        假设有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢？

有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a手机号码已经比 b 手机号码大了，那后面的几位就不用看了。

        基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

如何实现一个通用的、高性能的排序函数？

快速排序比较适合来实现排序函数，如何优化快速排序？最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。为了提高排序算法的性能，要尽可能地让每次分区都比较平均。

• 1. 三数取中法

①从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。

②如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“5数取中”或者“10数取中”。

• 2.随机法：每次从要排序的区间中，随机选择一个元素作为分区点。

• 3.警惕快排的递归发生堆栈溢出，有2种解决方法，如下：

①限制递归深度，一旦递归超过了设置的阈值就停止递归。

②在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制。

【通用排序函数实现技巧】

1.数据量不大时，可以采取用时间换空间的思路

2.数据量大时，优化快排分区点的选择

3.防止堆栈溢出，可以选择在堆上手动模拟调用栈解决

4.在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序

5.用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致