排序是最基础的算法，也是应用最广泛的算法。对排序算法的掌握程度很能体现算法与数据结构的基本功，所以也是面试中最常问到的算法。这一节对十大常见排序算法做一个全面总结。十大排序算法可以按照时间复杂度分为三类：
时间复杂度为 $O(n^2)$ 的排序：冒泡排序、选择排序、插入排序
时间复杂度为 $O(nlogn)$ 的排序：快速排序、归并排序、希尔排序、堆排序
时间复杂度为 $O(n)$ 的排序：桶排序、计数排序、基数排序
可以通过排序数组 题目实践这些算法。在最后，学习 C++ STL 的排序算法 sort()的具体实现。
1 时间复杂度为 $O(n^2)$ 的排序 这一类排序算法属于入门算法，性能较差，在实际工程中几乎不会用到，但他们的思想对解决一些特定问题还是很有启发的。
1.1 冒泡排序 1.1.1 算法思想 冒泡排序是入门级排序算法，但也有一些优化的写法，首先来看最简单的冒泡排序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void bubbleSort (vector<int > arr) for (int i = 0 ; i < arr.size () - 1 ; i++) { for (int j = 0 ; j < arr.size () - 1 - i; j++) { if (arr[j] > arr[j + 1 ]) { swap (arr, j, j + 1 ); } } } } void swap (vector<int > arr, int i, int j) int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
1.1.2 算法优化 稍微优化一下，因为在每一次冒泡的过程中，多次交换不仅会把最大/最小的数放到末尾，还会使中间一部分变得有序，这样会导致在后面的冒泡过程中没有任何交换，但还是进行了遍历，从而造成性能的浪费。因此使用一个变量记录当前轮次的比较是否发生过交换，如果没有发生交换表示已经有序，不再继续排序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void bubbleSort (vector<int > arr) bool swapped = true ; for (int i = 0 ; i < arr.size () - 1 ; i++) { if (!swapped) break ; swapped = false ; for (int j = 0 ; j < arr.size () - 1 - i; j++) { if (arr[j] > arr[j + 1 ]) { swap (arr, j, j + 1 ); swapped = true ; } } } } void swap (vector<int > arr, int i, int j) int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
再进一步进行优化，除了记录当前轮次是否发生过交换外，再用一个变量记录最后一次发生交换的位置，下一次遍历只要到该位置即可，因为该位置之后必然都已经有序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 void bubbleSort (vector<int > arr) bool swapped = true ; int indexOfLastUnsortedElement = arr.size () - 1 ; int swappedIndex = -1 ; while (swapped) { swapped = false ; for (int i = 0 ; i < indexOfLastUnsortedElement; i++) { if (arr[i] > arr[i + 1 ]) { swap (arr, i, i + 1 ); swapped = true ; swappedIndex = i; } } indexOfLastUnsortedElement = swappedIndex; } } void swap (vector<int > arr, int i, int j) int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
1.1.3 swap 函数 优化后的冒泡排序的平均时间复杂度实际上还是 $O(n^2)$，所以这些优化对算法的性能并没有质的提升，因此冒泡排序也并不会在实际工程中使用，面试中也几乎不可能会问到，但是现在学习冒泡排序的另一个价值是关于上面的 swap 函数，这是面试中一个经典的问题：不使用额外空间交换数组中的两个数 。做法非常简单：
1 2 3 nums[i+1 ] += nums[i]; nums[i] = nums[i+1 ] - nums[i]; nums[i+1 ] = nums[i+1 ] - nums[i];
另一种实现，先减后加，原理一样：
1 2 3 nums[i+1 ] -= nums[i]; nums[i] = nums[i+1 ] + nums[i]; nums[i+1 ] = nums[i] - nums[i+1 ];
上面两种方法都可能会数字越界，最好的方法是位运算：
1 2 3 arr[i] = arr[i] ^ arr[j]; arr[j] = arr[j] ^ arr[i]; arr[i] = arr[i] ^ arr[j];
1.1.4 相关练习
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
自己定义一个比较函数即可，如果两个数字的字符串拼接 sx + xy < sy + sx，则可以认为 sx 小于 sy ，即 sx 应该排在前面。
至于排序算法的选择，可以用任意排序，冒泡就不再重新写了，这里直接用 c++ 的 sort 函数，如果不用 sort 函数可以不使用额外空间。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : string minNumber (vector<int >& nums) { vector<string> strs; string res; for (int i = 0 ; i < nums.size (); i++) strs.push_back (to_string (nums[i])); sort (strs.begin (), strs.end (), [](string& x, string& y){ return x + y < y + x; }); for (int i = 0 ; i < strs.size (); i++) res += strs[i]; return res; } };
在双指针时做过，双指针自然是最好的解法，不过显然用冒泡的思想更加直观。
1.2 选择排序 1.2.1 算法思想 选择排序的思想是，双重遍历数组，每一轮遍历都将数组中最小/最大的值交换到数组首位。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void selectionSort (vector<int > arr) int minIndex; for (int i = 0 ; i < arr.size () - 1 ; ++i) { minIndex = i; for (int j = i + 1 ; j < arr.size (); ++j) { if (arr[minIndex] > arr[j]) { minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }
选择排序与冒泡排序时间复杂度和空间复杂度完全一致，但二者有一个非常大的差异就是冒泡排序是稳定的，而选择排序是不稳定的。
1.2.2 排序的稳定性 对于排序算法来说，稳定 是指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
在冒泡排序中，只有左边的数字大于右边的数字时才会发生交换，相等的数字之间不会发生交换，所以它是稳定的。而选择排序中，最小值和首位交换的过程可能会破坏稳定性。比如数列：[2, 2, 1]，在选择排序中第一次进行交换时，原数列中的两个 2 的相对顺序就被改变了，因此，我们说选择排序是不稳定的。
那么排序算法的稳定性有什么意义呢？其实它只在一种情况下有意义：当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。
举个例子，如果我们要对一组商品排序，商品存在两个属性：价格和销量。当我们按照价格从高到低排序后，要再按照销量对其排序，这时，如果要保证销量相同的商品仍保持价格从高到低的顺序，就必须使用稳定性算法。
当然，算法的稳定性与具体的实现有关。在修改比较的条件后，稳定性排序算法可能会变成不稳定的。如冒泡算法中，如果将「左边的数大于右边的数，则交换」这个条件修改为「左边的数大于或等于右边的数，则交换」，冒泡算法就变得不稳定了。同样地，不稳定排序算法也可以经过修改，达到稳定的效果。比如选择排序算法实现稳定排序一种最简单的思路是：新开一个数组，将每轮找出的最小值依次添加到新数组中，这样选择排序算法就变成稳定的了。
但如果将寻找最小值的比较条件由 arr[minIndex] > arr[j] 修改为 arr[minIndex] >= arr[j]，即使新开一个数组，选择排序算法依旧是不稳定的。所以分析算法的稳定性时，需要结合具体的实现逻辑才能得出结论，我们通常所说的算法稳定性是基于一般实现而言的。
1.2.3 算法优化 选择排序算法也是可以优化的，既然每轮遍历时找出了最小值，何不把最大值也顺便找出来呢？这就是二元选择排序的思想，每轮选择时记录最小值和最大值，这样可以把数组需要遍历的范围缩小一倍。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 void selectionSort2 (vector<int > arr) int minIndex, maxIndex; for (int i = 0 ; i < arr.size () / 2 ; i++) { minIndex = i; maxIndex = i; for (int j = i + 1 ; j < arr.size () - i; j++) { if (arr[minIndex] > arr[j]) { minIndex = j; } if (arr[maxIndex] < arr[j]) { maxIndex = j; } } if (minIndex == maxIndex) break ; int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; if (maxIndex == i) maxIndex = minIndex; int lastIndex = arr.size () - 1 - i; temp = arr[lastIndex]; arr[lastIndex] = arr[maxIndex]; arr[maxIndex] = temp; } }
在二元选择排序中，需要遍历的数组范围缩小了一倍，但效率并不能提高一倍，这是因为在内层循环中普通选择排序只要做一次比较，而二元选择循环需要做两次比较，因此提升的效率并不是线性的。不过由于在上面的二元选择排序中，我们使用了：
1 if (minIndex == maxIndex) break ;
来做优化，因此当数组中重复元素很多时，二元选择排序效率将远高于选择排序。
1.3 插入排序 1.3.1 算法思想 插入排序的思想非常简单，生活中有一个很常见的场景：在打扑克牌时，我们一边抓牌一边给扑克牌排序，每次摸一张牌，就将它插入手上已有的牌中合适的位置，逐渐完成整个排序。
插入排序的基本思想就是：在新数字插入过程中，不断与前面的数字交换，直到找到自己合适的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void insertSort (vector<int > arr) for (int i = 1 ; i < arr.size (); i++) { int j = i; while (j >= 1 && arr[j] < arr[j - 1 ]) { swap (arr, j, j - 1 ); j--; } } } void swap (vector<int >& arr, int i, int j) int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
1.3.2 算法优化 我们发现，在上面的插入排序中，每次交换数字时，swap 函数都会进行三次赋值操作。但实际上，新插入的这个数字并不一定适合与它交换的数字所在的位置。也就是说，它刚换到新的位置上不久，下一次比较后，如果又需要交换，它马上又会被换到前一个数字的位置。
由此，我们可以想到一种优化方案：让新插入的数字先进行比较，前面比它大的数字不断向后移动，直到找到适合这个新数字的位置后，新数字只做一次插入操作即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void insertSort (vector<int > arr) for (int i = 1 ; i < arr.size (); i++) { int cur = arr[i]; int j = i - 1 ; while (j >=0 && arr[j] > cur) { arr[j+1 ] = arr[j]; --j; } arr[j+1 ] = cur; } }
插入排序时间复杂度同样是 $O(n^2)$，空间复杂度为 $O(1)$，且插入排序是稳定的排序算法。
1.3.3 相关练习
给定单个链表的头 head ，使用插入排序 对链表进行排序，并返回排序后链表的头。
单向链表的插入排序比数组困难一些，我们无法从插入的新元素的位置向前遍历寻找插入位置，只能从头开始寻找插入位置，为此我们需要记录链表有序部分的最后一个节点，先判断该节点和当前待插入节点的大小，如果待插入节点比链表有序部分的最后一个节点的值大，那么无需插入，直接向后继续即可，否则从头结点开始寻找插入位置。
为了方便在头节点前插入节点，事先定义一个哑节点，这是链表题目的常规操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution {public : ListNode* insertionSortList (ListNode* head) { if (!head) return head; ListNode* dummy = new ListNode (INT_MIN, head); ListNode* last_sorted = head; ListNode* cur = head->next; while (cur) { if (cur->val >= last_sorted->val) { last_sorted = last_sorted->next; cur = last_sorted->next; } else { ListNode *pre = dummy, *t = pre->next; while (t->val <= cur->val) { pre = t; t = t->next; } last_sorted->next = cur->next; cur->next = pre->next; pre->next = cur; cur = last_sorted->next; } } return dummy->next; } };
2 时间复杂度为 $O(nlogn)$ 的排序 这一类排序是排序中最为重要的算法，因为他们普适性好，效率高，许多编程语言内置的排序函数的实现就综合了这里面的各类算法。
2.1 希尔排序 希尔排序本质上是对插入排序的一种优化，虽然现在几乎不被使用，但作为第一批将时间复杂度降到 $O(n^2)$ 以下的排序算法，还是有必要了解一下。
2.1.1 算法思想 希尔排序的基本思想是：
将待排序数组按照一定的间隔分为多个子数组，每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组，而是每跳跃一定间隔取一个值组成一组
逐渐缩小间隔进行下一轮排序
最后一轮时，取间隔为 1，也就相当于直接使用插入排序。但这时经过前面的宏观调控，数组已经基本有序了，所以此时的插入排序只需进行少量交换便可完成
其中，每一遍排序的间隔在希尔排序中被称之为增量，所有的增量组成的序列称之为增量序列，增量依次递减，最后一个增量必须为 1，所以希尔排序又被称为「缩小增量排序」。
增量序列的选择会极大地影响希尔排序的效率。本例中，我们采用的增量序列为 $D_m = N/2$，$D_k = D_{k+1} / 2$ 。这个序列正是当年希尔发表此算法的论文时选用的序列，所以也被称之为希尔增量序列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 void shellSort (vector<int > arr) for (int gap = arr.size () / 2 ; gap > 0 ; gap /= 2 ) { for (int groupStartIndex = 0 ; groupStartIndex < gap; groupStartIndex++) { for (int currentIndex = groupStartIndex + gap; currentIndex < arr.size (); currentIndex += gap) { int currentNumber = arr[currentIndex]; int preIndex = currentIndex - gap; while (preIndex >= groupStartIndex && currentNumber < arr[preIndex]) { arr[preIndex + gap] = arr[preIndex]; preIndex -= gap; } arr[preIndex + gap] = currentNumber; } } } }
2.1.2 算法优化 实际上，这段代码可以优化一下。我们现在的处理方式是：处理完一组间隔序列后，再回来处理下一组间隔序列，这非常符合人类思维。但对于计算机来说，它更喜欢从第 gap 个元素开始，按照顺序将每个元素依次向前插入自己所在的组这种方式。虽然这个过程看起来是在不同的间隔序列中不断跳跃，但站在计算机的角度，它是在访问一段连续数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void shellSort (vector<int > arr) for (int gap = arr.size () / 2 ; gap > 0 ; gap /= 2 ) { for (int i = gap; i < arr.size (); i++) { int currentNumber = arr[i]; int preIndex = i - gap; while (preIndex >= 0 && currentNumber < arr[preIndex]) { arr[preIndex + gap] = arr[preIndex]; preIndex -= gap; } arr[preIndex + gap] = currentNumber; } } }
这与插入排序非常相似，但多了一层外层的间隔序列循环。
2.1.3 算法性能 之前说过，增量序列的选择将直接影响希尔排序的性能，因此它也是希尔排序的核心优化点，学界有不少的大牛做过这方面的研究。比较著名的有 Hibbard 增量序列、Knuth 增量序列、Sedgewick 增量序列。由于希尔排序已经逐渐不被使用，因此这部分内容也不是我们学习的重点。
事实上，希尔排序时间复杂度非常难以分析，它的平均复杂度界于 $O(n)$ 到 $O(n^2)$ 之间，普遍认为它最好的时间复杂度为 $O(n^{1.3})$。希尔排序的空间复杂度为 $O(1)$，只需要常数级的临时变量。
我们现在学习希尔排序的意义在于，要理解希尔排序为什么能打破排序算法 $O(n^2)$ 的壁障，理解了这一点就明白了为什么希尔排序能承上启下，引发出之后一系列 $O(n^2)$ 以下的排序算法。
这可以通过逆序对来理解，所谓逆序对是指：当我们从小到大排序时，在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。排序算法本质上就是一个消除逆序对的过程。对于随机数组，逆序对的数量是 $O(n^2)$ 级的，如果采用交换相邻元素的办法来消除逆序对，每次最多只能消除一组逆序对，因此必须执行 $O(n^2)$ 级的交换次数，这就是为什么冒泡、插入、选择算法只能到 $O(n^2)$ 级的原因。反过来说，基于交换元素的排序算法要想突破 $O(n^2)$ 级，必须通过一些比较，交换间隔比较远的元素，使得一次交换能消除一个以上的逆序对。
希尔排序算法就是通过这种方式，打破了在空间复杂度为 $O(1)$ 的情况下，时间复杂度为 $O(n^2)$ 的魔咒，此后的快排、堆排等等算法也都是基于这样的思路实现的。
2.2 堆排序 2.2.1 算法思想 我们之前已经学习过优先队列和堆，并且自己动手实现了一个堆，因此堆排序的思想现在并不难理解。我们将该数组初始构建为一个大顶堆，然后每次将堆顶元素交换到数组末尾，剩下的元素调整形成新的大顶堆，重复以上过程即可。我们之前自己动手实现堆的时候已经知道了如何调整数组元素，现在只需要了解如何通过给定数组高效的构建一个大顶堆。
我们可以把给定数组直接视作一个大顶堆，而不要再开辟额外空间，直接在该数组上调整元素使其成为大顶堆就行了。 对于一个长度为 n 的数组形成的堆，它的最后一个非叶子节点的编号为 n / 2 - 1，我们从最后一个非叶子节点开始向前遍历，每个节点和它的孩子节点比较，并作相应的交换，所以叶子节点不需要调整，直接从最后一个非叶子节点开始即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution {public : void BuildHeap (vector<int >& nums) { for (int i = nums.size () / 2 - 1 ; i >= 0 ; --i) { AdjustHeap (nums, i, nums.size ()); } } void AdjustHeap (vector<int >& nums, int root, int heapsize) { int leftchild = 2 * root + 1 ; int rightchild = leftchild + 1 ; int maxindex = root; if (leftchild < heapsize && nums[leftchild] > nums[maxindex]) { maxindex = leftchild; } if (rightchild < heapsize && nums[rightchild] > nums[maxindex]) { maxindex = rightchild; } if (maxindex == root) return ; swap (nums[root], nums[maxindex]); AdjustHeap (nums, maxindex, heapsize); } vector<int > HeapSort (vector<int >& nums) { BuildHeap (nums); for (int heapsize = nums.size () - 1 ; heapsize > 0 ; --heapsize) { swap (nums[0 ], nums[heapsize]); AdjustHeap (nums, 0 , heapsize); } return nums; } };
2.2.2 算法性能 根据数学运算可以推导出初始化建堆的时间复杂度为 $O(n)$，重建堆的时间复杂度为 $O(n\log n)$，所以堆排序总的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(1)$。堆排序是一个优秀的排序算法，但是在实际应用中，快速排序的性能一般会优于堆排序。
2.2.3 相关练习
给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都互不相同 。
运动员将根据得分决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：
名次第 1 的运动员获金牌 “Gold Medal” 。
名次第 2 的运动员获银牌 “Silver Medal” 。
名次第 3 的运动员获铜牌 “Bronze Medal” 。
从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 “x”）。
使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况.
比较简单，堆排序记录下标即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution {public : struct cmp { bool operator () (pair<int , int >& x, pair<int , int >& y) { return x.first < y.first; } }; vector<string> findRelativeRanks (vector<int >& score) { int n = score.size (); priority_queue<pair<int , int >, vector<pair<int , int >>, cmp> q; for (int i = 0 ; i < n; ++i) { q.push (pair (score[i], i)); } vector<string> ans (n) ; for (int i = 1 ; i <= n; ++i) { pair<int ,int > maxscore = q.top (); q.pop (); if (i == 1 ) ans[maxscore.second] = "Gold Medal" ; else if (i == 2 ) ans[maxscore.second] = "Silver Medal" ; else if (i == 3 ) ans[maxscore.second] = "Bronze Medal" ; else ans[maxscore.second] = to_string (i); } return ans; } };
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
这是一道很简单的题目，排序后数组的中位数一定是多数元素，因此只需要对数组排序即可，自己手写堆排序可以不使用额外空间。
对于上述结论的证明以及这道题更好的解法——摩尔投票法，参考官方题解方法五 。
2.3 快速排序 2.3.1 算法思想 快速排序在时间复杂度为 $O(nlogn)$ 级的几种排序算法中，大多数情况下效率更高，所以快速排序的应用非常广泛。再加上快速排序所采用的分治思想非常实用，使得快速排序深受面试官的青睐，所以掌握快速排序的思想尤为重要。
快速排序算法的基本思想是：
从数组中取出一个数，称之为基数（pivot）
遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域
将左右两个区域视为两个数组，重复前两个步骤，直到排序完成
依据上面的思路，我们可以先写出快速排序的框架：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void SortArray (vector<int >& arr) quickSort (arr, 0 , arr.size () - 1 ); } void quickSort (vector<int >& arr, int start, int end) int middle = partition (arr, start, end); quickSort (arr, start, middle - 1 ); quickSort (arr, middle + 1 , end); } int partition (vector<int >& arr, int start, int end) }
这个框架存在一个严重的问题，就是没有退出递归的边界条件，显然当某个分区内只有一个数字或者没有数字的时候就不需要继续排序了，分区内只有一个数字即 start == end，分区内没有数字即 start > end，因此退出递归的条件是 start >= end。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void SortArray (vector<int >& arr) quickSort (arr, 0 , arr.size () - 1 ); } void quickSort (vector<int >& arr, int start, int end) if (start >= end) return ; int middle = partition (arr, start, end); quickSort (arr, start, middle - 1 ); quickSort (arr, middle + 1 , end); } int partition (vector<int >& arr, int start, int end) }
接下来实现最关键的分区函数，分区函数的目的是选择一个基数，然后将所有小于基数的数都放到基数左边，将所有大于基数的数都放到基数右边，最后返回基数所在的下标。
因此如何选择基数就成为了一个问题，一般来说有三种选择方案：
选择第一个数作为基数
选择最后一个数作为基数
随机选择一个数作为基数
这里我们以第一种基数选择方法为例来实现快速排序，但实际上随机选择一个数作为基数的快速排序平均时间复杂度最优，我们将在后面讨论。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 void SortArray (vector<int >& arr) quickSort (arr, 0 , arr.size () - 1 ); } void quickSort (vector<int >& arr, int start, int end) if (start >= end) return ; int middle = partition (arr, start, end); quickSort (arr, start, middle - 1 ); quickSort (arr, middle + 1 , end); } int partition (vector<int >& arr, int start, int end) int pivot = start; int left = start + 1 , right = end; while (left < right) { while (left < right && arr[left] < arr[pivot]) ++left; while (right > left && arr[right] >= arr[pivot]) --right; if (left < right) { swap (arr[left], arr[right]); ++left; --right; } } if (left == right && arr[right] >= arr[pivot]) --right; if (right != pivot) swap (arr[pivot], arr[right]); return right; }
上面的分区函数使用了双指针的方法，这也是容易想到的比较好的实现方法。上面的代码中有一个细节，在while循环结束后，还加了一个额外的判断：
1 if (left == right && arr[right] >= arr[pivot]) --right;
这是因为在上面的 while 退出的时候，left 和 right 同时指向的数还没有和基数做判断，所以需要额外做一次判断；同时这行代码还解决了 [start, end] 区间内只有两个数字的情况，这种情况下第一个数字做为基数，那么 [left, right] 区间内就只有一个数字，因此不会进入 while 循环，所以需要判断一次。
另外要注意的是，这里不能用 left 指针来判断，因为 left 指针递加有可能超出数组范围，而 right 指针递减至少也是和 pivot 相等，即指向区间内第一个元素，所以不会出现问题，最后交换和返回也都是用 right 指针更为安全。
双指针实现比较简单直观，但是要写的代码比较多，也要考虑比较多的特殊情况，更为简单的分区函数实现一般是：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int Partition (vector<int >& arr, int start, int end) int piovt = start; int ret = start; for (int right = start + 1 ; right <= end; ++right) { if (arr[right] < arr[piovt]) { ++ret; swap (arr[ret], arr[right]); } } swap (arr[start], arr[ret]); return ret; }
这样无需更多的特殊判断，是一种更高效的写法。
2.3.2 算法分析 快排的平均时间复杂度为 $O(nlogn)$，最坏情况下的时间复杂度为 $O(n^2)$；空间复杂度与递归的层数有关，最好情况下空间复杂度为 $O(logn)$，最坏情况下为 $O(n^2)$，平均空间复杂度为 $O(logn)$。
现在我们来分析以下为什么随机选择基数的平均复杂度更低，首先我们要搞清楚上面说的最坏情况是什么情况。理想中的快速排序在第 k 轮遍历中，可以排好 $2^{k-1}$ 个基数，假设我们用刚才实现的方法，即选择数组第一个数作为基数，考虑下面两种情况：
数组为正序，比如 nums = [1, 2, 3, 4, 5, 6]，这时第一次分区将原数组分为了 [0, 0] 和 [1, 5] 两个区间，而 0 是这一轮循环确定的基数的位置，所以相当于有一个区间是空的，下一次分区也是同样，因此每次分区都有一个区间是空的，相当于每一轮遍历都只能确定 1 个基数的位置，所以总的比较次数为 $(n-1) + (n-2) + …+1 = n(n-1)/2$ 次，此时快排的时间复杂度就达到了 $O(n^2)$。
数组为逆序，比如 nums = [6, 5, 4, 3, 2, 1]，这时第一次分区将原数组分为了 [0, 4] 和 [5, 5] 两个区间，而 5 是这一轮循环确定的基数的位置，所以相当于有一个区间是空的，下一轮分区时数组变为了 nums = [1, 5, 4, 3, 2, 6] ，我们要在 [0, 4] 区间上继续分区，经过这一轮，将区间 [0, 4] 分为了 [0, 0] 和 [1, 4] 两个区间，而 0 是这一轮循环确定的基数的位置，所以相当于有一个区间是空的，以此类推，每次分区都有一个区间是空的，相当于每一轮遍历都只能确定 1 个基数的位置，因此这种情况下快排的时间复杂度也是 $O(n^2)$。
所以为了避免这种情况，我们在数组中随机选择一个数作为基数，这样选到数组中最大值或者最小值的概率就很低，自然可以避免最坏情况的发生。
2.3.3 算法优化 根据上面的分析，一般来说快速排序前可以对原数组进行“洗牌”，以防止原数组有序的情况，洗牌算法的思想非常简单，从后向前遍历数组，然后随机选择一个数组中的数字与当前元素交换，最终所有元素都被交换一次，就打乱了原数组的顺序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 int RandIntRange (int low, int high) int len = high - low + 1 ; return low + (rand () % len); } void shuffle (vector<int >& nums) for (int i = nums.size () - 1 ; i >= 0 ; --i) { int p = RandIntRange (0 , i); if (p != i) swap (nums[p], nums[i]); } }
当然也可以在排序前对原数组进行一个判断，如果已经有序则直接返回，如果是逆序则直接倒序即可。显然洗牌算法的时间复杂度为 $O(n)$。实际实现快速排序的时候我们不需要把数组完整洗牌，每次选择基数的时候随机选择一个基数即可。
2.3.4 快速选择 基于快速排序的选择算法是面试中的高频考题，我们可以再次回顾一下 TopK 问题。
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
之前我们是用堆排序解决的，堆排序的方法时间复杂度为 $O(nlogn)$，空间复杂度为 $O(logn)$。使用基于快速排序的选择算法可以将平均时间复杂度降低至 $O(n)$。
快速选择的思想非常简单，在快速排序中，每一轮都可以确定区间内一个基数的最终位置，partition 函数会返回这个位置，因此我们从小到大进行快速排序，当确定的基数的位置为 nums.size() - k 时，就得到了第 K 个最大的元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution {public : int select_piovt (vector<int >& nums, int low, int high) { int len = high - low + 1 ; int t = low + (rand () % len); swap (nums[t], nums[low]); return nums[low]; } int partition (vector<int >& nums, int low, int high) { int piovt = select_piovt (nums, low, high); int ret = low; for (int right = low + 1 ; right <= high; ++right) { if (nums[right] < piovt) { swap (nums[++ret], nums[right]); } } swap (nums[ret], nums[low]); return ret; } int findKthLargest (vector<int >& nums, int k) int low = 0 , high = nums.size () - 1 , target = high - k + 1 ; while (1 ) { int index = partition (nums, low, high); if (index == target) break ; else if (index < target) low = index + 1 ; else high = index - 1 ; } return nums[target]; } };
2.4 归并排序 2.4.1 算法思想 归并排序也是一种性能很优秀的排序算法，并且由于它是稳定的排序算法，因此也被广泛应用。归并排序的基本思想是对原数组不停的二分，直到每个区间都只有 1 个数字，这时这个区间可以视为一个有序区间，然后再不停的合并两个有序区间即可。
合并两个有序数组是我们做过的一道题，一般来说可以开辟一个长度为两个区间之和的数组，然后双指针遍历两个数组即可。由此我们可以写出归并排序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 vector<int > sortArray (vector<int >& nums) { if (nums.size () < 2 ) return nums; vector<int > temp (nums.size()) ; MergeSort (nums, 0 , nums.size () - 1 , temp); return nums; } void MergeSort (vector<int >& nums, int start, int end, vector<int >& temp) if (start == end) return ; int mid = start + (end - start) / 2 ; MergeSort (nums, start, mid, temp); MergeSort (nums, mid + 1 , end, temp); merge (nums, start, end, temp); } void merge (vector<int >& nums, int start, int end, vector<int >& temp) int mid = start + (end - start) / 2 ; int index1 = start; int start2 = mid + 1 , index2 = start2; while (index1 <= mid && index2 <= end) { if (nums[index1] <= nums[index2]) { temp[index1 + index2 - start2] = nums[index1]; ++index1; } else { temp[index1 + index2 - start2] = nums[index2]; ++index2; } } while (index1 <= mid) { temp[index1 + index2 - start2] = nums[index1]; ++index1; } while (index2 <= end) { temp[index1 + index2 - start2] = nums[index2]; ++index2; } for (int i = start; i <= end; ++i) { nums[i] = temp[i]; } }
2.4.2 算法分析 归并排序的复杂度比较容易分析，拆分数组的过程中，会将数组拆分 $logn$ 次，每层执行的比较次数都约等于 $n$ 次，所以时间复杂度是 $O(nlogn)$。空间复杂度是 $O(n)$，主要占用空间的就是我们在排序前创建的长度为 n 的 temp 数组。
我们在合并数组的时候的判断条件是：
1 if (nums[index1] <= nums[index2])
这保证了归并排序是稳定的。如果没有等号则归并排序不再稳定。
2.4.3 相关练习
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
因为 A 数组末尾提供了足够的空间，我们使用双指针逆序从两个数组末尾取出数字，把最大的放到A的末尾。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : void merge (vector<int >& A, int m, vector<int >& B, int n) int pa = m - 1 , pb = n - 1 ; while (pa >= 0 && pb >= 0 ) { if (A[pa] >= B[pb]) { A[pa + pb + 1 ] = A[pa]; --pa; } else { A[pa + pb + 1 ] = B[pb]; --pb; } } while (pb >= 0 ) { A[pa + pb + 1 ] = B[pb]; --pb; } } };
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
使用暴力法很简单但时间复杂度太高，这道题非常考验对归并排序的理解。
关键在于归并排序中合并有序数组的时候，如果左边数组中当前指针指向的数字 nums[left] 比右边数组中当前指针指向的数字 nums[right] 小，那么就把 nums[left] 加入答案，同时判断右边数组中有多少数字比 nums[left] 小，这就是 nums[left] 对整个数组逆序对数量的贡献，因为右边数组中比 nums[left] 小的数原本排在了 nums[left] 的右边，就构成了一个逆序对。而右边数组中比 nums[left] 小的数字数量刚好就是右边数组的当前指针 right 相对于右边数组起始位置 mid + 1 的偏移，因为在右边数组当前指针之前的数字都已经加入到了结果中，一定比 nums[left] 小。
按照上面的思路，我们只需要在归并排序中加一个统计逆序对数量的变量即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 class Solution {public : int cnt = 0 ; void MergeSort (vector<int >& nums, int start, int end, vector<int >& temp) { if (start == end) return ; int mid = start + (end - start) / 2 ; MergeSort (nums, start, mid, temp); MergeSort (nums, mid + 1 , end, temp); merge (nums, start, end, temp); } void merge (vector<int >& nums, int start, int end, vector<int >& temp) { int mid = start + (end - start) / 2 ; int index1 = start; int start2 = mid + 1 , index2 = start2; while (index1 <= mid && index2 <= end) { if (nums[index1] <= nums[index2]) { temp[index1 + index2 - start2] = nums[index1]; ++index1; cnt += index2 - start2; } else { temp[index1 + index2 - start2] = nums[index2]; ++index2; } } while (index1 <= mid) { temp[index1 + index2 - start2] = nums[index1]; ++index1; cnt += index2 - start2; } while (index2 <= end) { temp[index1 + index2 - start2] = nums[index2]; ++index2; } for (int i = start; i <= end; ++i) { nums[i] = temp[i]; } } int reversePairs (vector<int >& nums) if (nums.size () < 2 ) return 0 ; vector<int > temp (nums.size()) ; MergeSort (nums, 0 , nums.size () - 1 , temp); return cnt; } };
3 时间复杂度为 $O(n)$ 的排序 这一类排序算法平均时间复杂度最优，但一般只适用于特定场景，在特定问题下的排序效率将高于其他算法。
3.1 计数排序 3.1.1 算法思想 计数排序的思想很简单，假设一个数组只包含 0 ~ 9 范围内的数字，那我们可以建立一个长度为 10 的数组，统计原数组中 0 ~ 9 各出现了几次，统计完成后再按顺序把数字填到数组中即可，整个过程如下图：
但这样排序并不是真正的计数排序，因为我们这样做相当于只是把和原数组中数字相同的值放回了原数组中，而这些值已经不是原来的数字了，这在实际工程中如果待排序的对象有其他属性的话，这样做就会丢掉其他属性，于是我们可以建立一个哈希表，去存储每个数字对应的原来的数字（对象），最后再按顺序放回去即可。
真正的计数排序使用的方法更为巧妙，统计完计数数组后，遍历原数组，对原数组的每一个元素可以根据计数数组的结果得到它排序后应该在的位置，他应该在的位置就是起始位置加上所有比它小的数字之和，因此直接把该数字放到对应的位置上即可。同时为了处理更一般的情况，而不是只有 0 ~ 9，要先统计计数范围，计数范围就是数组中的最小值到最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 void countingSort (vector<int >& arr) int n = arr.size (); if (n < 2 ) return ; int max = arr[0 ], min = arr[0 ]; for (int i = 1 ; i < n; ++i) { if (arr[i] > max) max = arr[i]; else if (arr[i] < min) min = arr[i]; } int range = max - min + 1 ; vector<int > counting (range) ; for (int & element : arr) { ++counting[element - min]; } int preCounts = 0 ; for (int i = 0 ; i < range; i++) { preCounts += counting[i]; counting[i] = preCounts - counting[i]; } vector<int > result (n) ; for (int element : arr) { result[counting[element - min]] = element; ++counting[element - min]; } for (int i = 0 ; i < n; i++) { arr[i] = result[i]; } }
上面的代码很好理解，计数排序还有另一种写法，即在统计对应元素所在位置的时候，不统计该元素在结果中起始位置的下标，而是统计最后一个位置的下标，然后遍历原数组的时候从后向前遍历，这样的写法可以避免记录 preCounts，效率更高，一般也常使用这种写法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 void countingSort (vector<int >& arr) int n = arr.size (); if (n < 2 ) return ; int max = arr[0 ], min = arr[0 ]; for (int i = 1 ; i < n; ++i) { if (arr[i] > max) max = arr[i]; else if (arr[i] < min) min = arr[i]; } int range = max - min + 1 ; vector<int > counting (range) ; for (int & element : arr) { ++counting[element - min]; } counting[0 ] -= 1 ; for (int i = 1 ; i < range; ++i) { counting[i] += counting[i-1 ]; } vector<int > result (n) ; for (int i = n - 1 ; i >= 0 ; --i) { result[counting[arr[i] - min]] = arr[i]; counting[arr[i] - min]--; } for (int i = 0 ; i < n; i++) { arr[i] = result[i]; } }
实际上在遍历原数组放到结果数组中相应位置的时候，不逆序遍历也可以得到正确的结果，但只有逆序遍历才能保证计数排序的稳定性。
3.1.2 算法分析 从计数排序的实现代码中可以看到，每次遍历都是进行 n 次或者 k 次，所以计数排序的时间复杂度为 $O(n + k)$，k 表示数据的范围大小。用到的空间主要是长度为 k 的计数数组和长度为 n 的结果数组，所以空间复杂度也是 $O(n + k)$。
需要注意的是，一般我们分析时间复杂度和空间复杂度时，常数项都是忽略不计的。但计数排序的常数项可能非常大，以至于我们无法忽略。并且由此我们可以发现计数排序的一个致命的缺点，如果对下面的数组使用计数排序：
1 vector<int > arr = {1 , INT_MAX};
我们将会创建一个从 1 到 INT_MAX 的计数数组，C++ 中 int 占 4 字节，一个长度为 $2^{31}$ 的数组要占用 8G 的空间。所以计数排序只适用于数据范围不大的场景，如果需要排序的数字中存在一位小数，可以将所有数字乘以 10，再去计算最终的下标位置。
接下来我们考虑为什么计数排序可以突破 $O(nlogn)$ 的时间复杂度。因为计数排序不是基于比较的排序算法 。
根据决策树理论可以推导出所有基于比较的排序算法最坏情况下都要做 $O(nlogn)$ 次比较 ，因此所有基于比较的排序算法无论怎么优化都不可能突破 $O(nlogn)$ 的下界，而基数排序不是基于比较的算法，是利用数字本身的属性进行排序，整个算法中没有出现任何一次比较。
3.1.3 相关练习
给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
我们可以按照计数排序的思想，统计每个数字出现的次数，然后根据 arr2 计算每个数字应该在结果中对应的左右一个下标位置，这样就可以把在 arr2 中出现过的数字排好，剩下没有出现过的放到数组末尾，然后再利用其他排序微调。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 class Solution {public : vector<int > relativeSortArray (vector<int >& arr1, vector<int >& arr2) { int n = arr1.size (), m = arr2.size (); unordered_map<int , int > map; for (int i = 0 ; i < m; ++i) { map[arr2[i]] = i; } int min = *min_element (arr1.begin (), arr1.end ()); int max = *max_element (arr1.begin (), arr1.end ()); int range = max - min + 1 ; vector<int > countings (range) ; for (int & e : arr1) { ++countings[e - min]; } vector<int > presum (m+1 ,0 ) ; for (int i = 1 ; i <= m; ++i) { presum[i] = presum[i-1 ] + countings[arr2[i-1 ] - min]; } int offset = 0 ; for (int i = 0 ; i < range; ++i) { if (map.find (i + min) != map.end ()) { int t = map[i + min]; countings[i] = countings[i] + presum[t] - 1 ; } else { int temp = countings[i]; countings[i] = countings[i] + presum[m] + offset - 1 ; offset += temp; } } vector<int > res (n) ; for (int i = n - 1 ; i >= 0 ; --i) { res[countings[arr1[i] - min]] = arr1[i]; countings[arr1[i] - min]--; } sort (res.begin () + presum[m], res.end ()); return res; } };
当然这样做显然使问题变得更复杂了，上面用到了哈希表、前缀和等复杂的技巧，对于这道简单题来说是完全没有必要的，我们只要用伪计数排序的思想，统计数字出现的次数，然后按照 arr2 提供的顺序找到计数数组中该数字出现的次数，放到结果数组中即可，之后再遍历一次计数数组把出现次数不为 0 的数按顺序放到结果末尾即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution {public : vector<int > relativeSortArray (vector<int >& arr1, vector<int >& arr2) { int min = *min_element (arr1.begin (), arr1.end ()); int max = *max_element (arr1.begin (), arr1.end ()); int range = max - min + 1 ; vector<int > countings (range) ; for (int & e : arr1) { ++countings[e - min]; } int index = 0 ; for (int & e : arr2) { while (countings[e - min]) { arr1[index] = e; ++index; --countings[e - min]; } } for (int i = 0 ; i < range; ++i) { while (countings[i]) { arr1[index] = i + min; ++index; --countings[i]; } } return arr1; } };
3.2 基数排序 3.2.1 算法思想 基数排序是通过对比数字的关键字进行排序的，关键字就称为基数，比如我们对 999, 997, 866, 666 这四个数字进行基数排序，过程如下：
先看第一位基数：6 比 8 小，8 比 9 小，所以 666 是最小的数字，866 是第二小的数字，暂时无法确定两个以 9 开头的数字的大小关系
再比较 9 开头的两个数字，看他们第二位基数：9 和 9 相等，暂时无法确定他们的大小关系
再比较 99 开头的两个数字，看他们的第三位基数：7 比 9 小，所以 997 小于 999
这就是基数排序的思路，上面的过程我们是从数字的最高位开始比较的，这样的基数排序叫做「最高位优先法」，简称 MSD (Most significant digital)，与之对应的还有「最低位优先法」，简称 LSD (Least significant digital)。思路是从最低位开始，依次对基数进行排序。使用 LSD 必须保证对基数进行排序的过程是稳定的。
一般来说 LSD 比 MSD 更常用。以上述排序过程为例，因为使用的是 MSD，所以在第二步比较两个以 9 开头的数字时，其他基数开头的数字不得不放到一边。体现在计算机中，这里会产生很多临时变量。但在采用 LSD 进行基数排序时，每一轮遍历都可以将所有数字一视同仁，统一处理。所以 LSD 的基数排序更符合计算机的操作习惯。
基数排序可以分为以下三个步骤：
找出数组中最大的数字的位数 maxDigitLength
获取数组中每个数字的基数
遍历 maxDigitLength 轮数组，每轮按照基数对其进行排序
对基数进行排序最好的办法就是使用计数排序，因为基数只可能在 0 ~ 9 之间，使用计数排序效率会很高，并且还能保证稳定。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 void radixSort (vector<int >& arr) if (arr.size () < 2 ) return ; int max = 0 ; for (int & value : arr) { if (value > max) { max = value; } } int maxDigitLength = 0 ; while (max != 0 ) { maxDigitLength++; max /= 10 ; } vector<int > counting (10 ) ; vector<int > result (arr.size()) ; int dev = 1 ; for (int i = 0 ; i < maxDigitLength; i++) { for (int value : arr) { int radix = value / dev % 10 ; counting[radix]++; } for (int j = 1 ; j < counting.size (); j++) { counting[j] += counting[j - 1 ]; } for (int j = arr.size () - 1 ; j >= 0 ; j--) { int radix = arr[j] / dev % 10 ; result[--counting[radix]] = arr[j]; } arr.assign (result.begin (), result.end ()); counting.assign (10 ,0 ); dev *= 10 ; } }
当数组中存在负数时，我们可以把计数排序的统计数组改为长度为19，用来统计 -9 ~ 9 出现的次数，但是要注意计算出的基数要加 9，以从 [-9, 9] 映射到计数数组下标 [0, 18]，完整的基数排序算法如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 void radixSort (vector<int >& arr) if (arr.size () < 2 ) return ; int max = 0 ; for (int & value : arr) { if (abs (value) > max) { max = abs (value); } } int maxDigitLength = 0 ; while (max != 0 ) { maxDigitLength++; max /= 10 ; } vector<int > counting (19 ) ; vector<int > result (arr.size()) ; int dev = 1 ; for (int i = 0 ; i < maxDigitLength; i++) { for (int value : arr) { int radix = value / dev % 10 ; counting[radix + 9 ]++; } for (int j = 1 ; j < counting.size (); j++) { counting[j] += counting[j - 1 ]; } for (int j = arr.size () - 1 ; j >= 0 ; j--) { int radix = arr[j] / dev % 10 ; result[--counting[radix + 9 ]] = arr[j]; } arr.assign (result.begin (), result.end ()); counting.assign (19 ,0 ); dev *= 10 ; } }
3.2.2 算法分析 基数排序需要经历 maxDigitLength 轮遍历，每轮遍历的时间复杂度为 $O(n + k)$，其中 k 表示每个基数可能的取值范围大小。如果是对非负整数排序，则 k = 10，如果是对包含负数的数组排序，则 k = 19。所以基数排序的时间复杂度为 $O(d(n + k))$，其中 d 表示最长数字的位数，k 表示每个基数可能的取值范围大小。
基数排序使用的空间和计数排序是一样的，空间复杂度为 $O(n + k)$，其中 k 表示每个基数可能的取值范围大小。
3.2.3 相关练习
给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。
您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。非商业转载请注明出处。
因为要保证线性时间和空间复杂度，因此使用基数排序符合要求，排序后再遍历找到最大差值即可。
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该最大总和 。
排序后拆分即可。使用基数排序会使时间复杂度更低。
3.3 桶排序 3.3.1 算法思想 桶排序的思想是：
将区间划分为 n 个相同大小的子区间，每个子区间称为一个桶
遍历数组，将每个数字装入桶中
对每个桶内的数字单独排序，这里需要采用其他排序算法，如插入、归并、快排等
最后按照顺序将所有桶内的数字合并起来
桶排序一般只能在特定情况下使用，因为桶排序算法基于一个假设：所有输入数据都服从均匀分布，也就是说输入数据应该尽可能地均匀分布在每个桶中。只有这个假设成立时，桶排序运行效率才比较高。在最差的情况下，所有数据都会被装入同一个桶中，此时桶排序算法只会徒增一轮遍历。
影响桶排序的效率的因素主要有两个：
一个是桶的数量，桶的数量过少，会导致单个桶内的数字过多，桶排序的时间复杂度就会在很大程度上受桶内排序算法的影响。桶的数量过多，占用的内存就会较大，并且会出现较多的空桶，影响遍历桶的效率。一般来说设置桶的数量要根据数组的数据量和数组内的最大值和最小值确定，一般用如下公式确定可以保证每个桶内的数字尽量均匀：
1 2 3 4 5 6 gap = (maxnum - minnum) / n + 1 ; bucketnum = (maxnum - minnum) / gap + 1 ; index = (nums[i] - min) / gap;
桶内排序算法，桶内排序算法可以使用插入排序、快速排序等，可以根据实际需要选择。
基于插入排序的桶排序的代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 void BucketSort (vector<int >& arr) int n = arr.size (); if (n < 2 ) return ; int maxnum = *max_element (arr.begin (), arr.end ()); int minnum = *min_element (arr.begin (), arr.end ()); int gap = (maxnum - minnum) / n + 1 ; int bucketnum = (maxnum - minnum) / gap + 1 ; vector<vector<int >> buckets (bucketnum); for (int & x : arr) { int index = (x - minnum) / gap; buckets[index].push_back (x); } arr.clear (); for (int i = 0 ; i < bucketnum; ++i) { insertsort (buckets[i]); arr.insert (arr.end (), buckets[i].begin (), buckets[i].end ()); } } void insertsort (vector<int >& nums) for (int i = 1 ; i < nums.size (); ++i) { int cur = nums[i]; int j = i - 1 ; while (j >= 0 && nums[j] > cur) { swap (nums[j], nums[j + 1 ]); --j; } nums[j+1 ] = cur; } }
3.3.2 算法分析 我们逐步分析桶排序的时间复杂度和空间复杂度。
第一步：找到最大值和最小值的过程需要一轮遍历，时间复杂度 $O(n)$，空间复杂度 $O(1)$。
第二步：装桶的过程需要遍历一轮数组，时间复杂度 $O(n)$，空间复杂度与$O(n)$。
第三步：桶内排序的过程与具体的排序算法有关，由于桶排序假设数据服从均匀分布，所以每个桶内的数字数量为 $n/k$,
如果采用 $O(n^2)$ 级排序算法，则每个桶内排序的时间复杂度为 $O((n/k)^2)$，所有桶完成排序的时间复杂度为 $O(k(n/k)^2)$，即 $O(n^2 / k)$。
如果采用 $O(n\log n)$ 级排序算法，每个桶内排序的时间复杂度 $O((n/k) \log (n/k))$，所有桶完成排序的时间复杂度为 $O(k(n/k) \log (n/k))$，即 $O(n \log (n/k))$。
在桶的数量合适的情况下，时间复杂度 $O(n^2 / k)$ 和 $O(n \log (n/k))$ 都约等于 $O(n)$。桶内排序的空间复杂度也和具体的排序算法有关，$O(1)$ 或者 $O(n)$。
第四步：桶内排序完成后，需要将所有桶的排序结果收集起来，虽然这一轮是遍历 k 个桶，但把所有桶的结果收集起来的总计算次数是 n。时间复杂度 $O(n)$，空间复杂度 $O(1)$。
综上，桶排序的时间复杂度为 $O(n)$，需要注意的是，这里 n 的常数项是比较大的，意味着桶排序不一定比 $O(n \log n)$ 级的排序算法快。空间复杂度为 $O(n)$。
3.3.3 相关练习
给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。
您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。非商业转载请注明出处。
使用桶排序解决这个问题更加巧妙。甚至不需要真正进行排序，只要把所有数字放到对应的桶里，然后记录每个桶的最大值和最小值，最后从左到右遍历桶，用后一个桶的最小值减去前一个桶的最大值，所有这些差值中最大的就是题目所要求的最大间距。具体证明参考官方题解方法二 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution {public : int maximumGap (vector<int >& nums) int n = nums.size (); if (n < 2 ) return 0 ; int minVal = *min_element (nums.begin (), nums.end ()); int maxVal = *max_element (nums.begin (), nums.end ()); int gap = (maxVal - minVal) / n + 1 ; int bucketnum = (maxVal - minVal) / gap + 1 ; vector<pair<int , int >> bucket (bucketnum, {-1 , -1 }); for (int i = 0 ; i < n; ++i) { int idx = (nums[i] - minVal) / gap; if (bucket[idx].first == -1 ) { bucket[idx].first = bucket[idx].second = nums[i]; } else { bucket[idx].first = min (bucket[idx].first, nums[i]); bucket[idx].second = max (bucket[idx].second, nums[i]); } } int ans = 0 ; int prev = -1 ; for (int i = 0 ; i < bucketnum; i++) { if (bucket[i].first == -1 ) continue ; if (prev != -1 ) { ans = max (ans, bucket[i].first - bucket[prev].second); } prev = i; } return ans; } };
4 C++ STL 中的 sort() 函数 STL 中的排序算法是所有算法中最庞大和复杂的一个，结合了上面多种排序算法，利用他们的特点，最大化排序效率。
4.1 插入排序 首先是插入排序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 template <class _RandomAccessIter >void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__first == __last) return ; for (_RandomAccessIter __i = __first + 1 ; __i != __last; ++__i) __linear_insert(__first, __i, __VALUE_TYPE(__first)); } template <class _RandomAccessIter , class _Compare >void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { if (__first == __last) return ; for (_RandomAccessIter __i = __first + 1 ; __i != __last; ++__i) __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp); } template <class _RandomAccessIter , class _Tp >inline void __linear_insert(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*) { _Tp __val = *__last; if (__val < *__first) { copy_backward (__first, __last, __last + 1 ); *__first = __val; } else __unguarded_linear_insert(__last, __val); } template <class _RandomAccessIter , class _Tp , class _Compare >inline void __linear_insert(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Compare __comp) { _Tp __val = *__last; if (__comp(__val, *__first)) { copy_backward (__first, __last, __last + 1 ); *__first = __val; } else __unguarded_linear_insert(__last, __val, __comp); } template <class _RandomAccessIter , class _Tp >void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) { _RandomAccessIter __next = __last; --__next; while (__val < *__next) { *__last = *__next; __last = __next; --__next; } *__last = __val; } template <class _RandomAccessIter , class _Tp , class _Compare >void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp) { _RandomAccessIter __next = __last; --__next; while (__comp(__val, *__next)) { *__last = *__next; __last = __next; --__next; } *__last = __val; }
4.2 快速排序 接下来是快速排序，STL 采用三点中值作为快排的 pivot：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 template <class _Tp >inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { __STL_REQUIRES(_Tp, _LessThanComparable); if (__a < __b) if (__b < __c) return __b; else if (__a < __c) return __c; else return __a; else if (__a < __c) return __a; else if (__b < __c) return __c; else return __b; } template <class _Tp , class _Compare >inline const _Tp&__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { __STL_BINARY_FUNCTION_CHECK(_Compare, bool , _Tp, _Tp); if (__comp(__a, __b)) if (__comp(__b, __c)) return __b; else if (__comp(__a, __c)) return __c; else return __a; else if (__comp(__a, __c)) return __a; else if (__comp(__b, __c)) return __c; else return __b; }
分区函数：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 template <class _RandomAccessIter , class _Tp >_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, _Tp __pivot) { while (true ) { while (*__first < __pivot) ++__first; --__last; while (__pivot < *__last) --__last; if (!(__first < __last)) return __first; iter_swap (__first, __last); ++__first; } } template <class _RandomAccessIter , class _Tp , class _Compare >_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, _Tp __pivot, _Compare __comp) { while (true ) { while (__comp(*__first, __pivot)) ++__first; --__last; while (__comp(__pivot, *__last)) --__last; if (!(__first < __last)) return __first; iter_swap (__first, __last); ++__first; } }
4.3 堆排序 STL 的排序算法还用到了堆排序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 template <class _RandomAccessIter , class _Tp >void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Tp*) { make_heap (__first, __middle); for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (*__i < *__first) __pop_heap(__first, __middle, __i, _Tp(*__i), __DISTANCE_TYPE(__first)); sort_heap (__first, __middle); } template <class _RandomAccessIter >inline void partial_sort (_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last) __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first)); } template <class _RandomAccessIter , class _Tp , class _Compare >void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Tp*, _Compare __comp) { make_heap (__first, __middle, __comp); for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (__comp(*__i, *__first)) __pop_heap(__first, __middle, __i, _Tp(*__i), __comp, __DISTANCE_TYPE(__first)); sort_heap (__first, __middle, __comp); } template <class _RandomAccessIter , class _Compare >inline void partial_sort (_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Compare __comp) __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool , typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp); }
4.4 IntroSort 通过之前的学习我们知道，快速排序时，不当的 pivot 选择，会导致不当的分割，最使得快速排序恶化为 $O(n^2)$。David R. Musser 于 1996 年提出一种混合式排序算法——Introspective Sorting（内省排序）。其行为在大部分情况下几乎与使用中值作为 pivot 的快排完全相同。但是当分割行为有恶化为二次行为倾向时，能自我侦测，转而改用堆排序，使效率维持在 $O(nlogn)$，又比一开始就使用堆排序来得好。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 const int __stl_threshold = 16 ;template <class _Size >inline _Size __lg(_Size __n) { _Size __k; for (__k = 0 ; __n != 1 ; __n >>= 1 ) ++__k; return __k; } template <class _RandomAccessIter , class _Tp , class _Size >void __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Size __depth_limit) { while (__last - __first > __stl_threshold) { if (__depth_limit == 0 ) { partial_sort (__first, __last, __last); return ; } --__depth_limit; _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2 ), *(__last - 1 )))); __introsort_loop(__cut, __last, (_Tp*) 0 , __depth_limit); __last = __cut; } } template <class _RandomAccessIter , class _Tp , class _Size , class _Compare >void __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Size __depth_limit, _Compare __comp) { while (__last - __first > __stl_threshold) { if (__depth_limit == 0 ) { partial_sort (__first, __last, __last, __comp); return ; } --__depth_limit; _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, *(__first + (__last - __first)/2 ), *(__last - 1 ), __comp)), __comp); __introsort_loop(__cut, __last, (_Tp*) 0 , __depth_limit, __comp); __last = __cut; } }
4.5 sort() 终于到了 sort 函数的实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 template <class _RandomAccessIter >inline void sort (_RandomAccessIter __first, _RandomAccessIter __last) __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, _LessThanComparable); if (__first != __last) { __introsort_loop(__first, __last, __VALUE_TYPE(__first), __lg(__last - __first) * 2 ); __final_insertion_sort(__first, __last); } } template <class _RandomAccessIter , class _Compare >inline void sort (_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); __STL_BINARY_FUNCTION_CHECK(_Compare, bool , typename iterator_traits<_RandomAccessIter>::value_type, typename iterator_traits<_RandomAccessIter>::value_type); if (__first != __last) { __introsort_loop(__first, __last, __VALUE_TYPE(__first), __lg(__last - __first) * 2 , __comp); __final_insertion_sort(__first, __last, __comp); } }
__final_insertion_sort 函数如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 template <class _RandomAccessIter >void __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { if (__last - __first > __stl_threshold) { __insertion_sort(__first, __first + __stl_threshold); __unguarded_insertion_sort(__first + __stl_threshold, __last); } else __insertion_sort(__first, __last); } template <class _RandomAccessIter , class _Compare >void __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { if (__last - __first > __stl_threshold) { __insertion_sort(__first, __first + __stl_threshold, __comp); __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp); } else __insertion_sort(__first, __last, __comp); }
其中 __unguarded_insertion_sort 只是调用了上面插入排序中的辅助函数二 __unguarded_linear_insert。
4.6 总结 通过以上的 STL 源码，可以看出 STL 的 sort 函数首先对整个序列使用 IntroSort 进行排序，如果序列长度不足 16，直接退出 IntroSort，因为对于短序列，快速排序效率可能不如插入排序，所以直接进行插入排序。IntroSort 内部会首先根据序列长度计算快速排序的最大递归层数，当快排递归到最大层数后改用堆排序，经过 IntroSort 后的序列被分为多个长度小于等于 16 的子序列，这些子序列之间有序，子序列内部基本有序，因此整个序列处于基本有序状态。最后调用插入排序对整个序列排序，插入排序在序列基本有序的情况下效率很高。
