CountingSort* ## 适用场景 1.

DigitLetterGroup* 对字母数字进行排序，小写字母放左边，数字放中间，大写字母放右边 */.

InsertSort 插入排序 ## 算法思路 1.

InsertSortWithSentinel 使用了哨兵模式的插入排序 在数组头部插入一个空元素，然后将每次比较的元素放到 arr[0] 中。以此省略掉 for 循环中的一次比较 */.

LetterGroup* ## 题目 对字母进行分组 例如存在 "D a F B c A z" 字符串，需要将小写字母都放在大写字母前面，小写字母/大写字母内部的顺序无所谓 ## 思路 和快排的 partition 函数类似，都是逐个判断数组中的元素，然后进行原地交换 从两头对数组中的字符进行判断，如果它所处的位置不对，则和对面进行位置交换 ## 桶排序思路 分成大写和小写字母两个桶，然后分别将元素放入到桶中，最后在按序输出两个桶 这里省略了桶内排序的步骤，所以时间复杂度是 O(n) 这个思路申请了额外的空间，空间复杂度是 O(n), 没有上面的思路好。 ## 复杂度分析 charGroup 从两头对整个数组进行了一次遍历，所以时间复杂度是 O(n) 没有以 n 为单位申请新空间，空间复杂度是 O(1) */.

QuickSort 快速排序* ## 思路 它的思路是，给定一个数组 arr - partition 函数找到支撑点 pivot 的索引 p，保证 p 左边的数字都 < pivot，右边的数字都 >= pivot - 在 partition 函数中巧妙地实现了原地排序，没有申请新的数组空间 - 然后再用分治的思想，分别将 p 左右两边的数组再进行排序 快排和归并排序的过程正好是相反的， - 归并排序是自底向上，先将长度为1的数组进行排序，再逐级往上 - 快排是自顶向下，先将数组分成两份，保证 all of left < pivot < all of right, 再对左右两个数组进行排序 ## 时间复杂度 大部分情况下，时间复杂度都是 O(n*logn), 最坏情况下时间复杂度是 O(n^2) ### 最坏情况 例如 1, 3, 5, 6, 8 这个有序数组，每次分区只得到一个数组, 左边是 n-1, 右边是 0 T(1) = C T(n) = T(n-1) + n = T(n-2) + n - 1 + n ...

RadixSort* 基数排序 ## 问题 对手机号进行排序 ## 思路 从右边起，对每一位数字进行计数排序 ## 分析 因为计数排序是稳定性排序，我们可以这样操作，如果计数排序是不稳定排序，就不能工作了。 ## 复杂度分析 手机号一共有11位，每次计数排序的时间复杂度是 O(n), 得到整体时间复杂度是 O(11 * n) **/.

TopK* ## 题目 O(n) 时间复杂度内求数组的第 k 大元素 ## 思路介绍 这个题目也使用了分治的思想 利用快排的 partition 函数，获取最后一个数在数组中的大小索引 p(注意 p 是从0开始的)，并按大小左右分组 如果 p+1 > k, 则说明第 k 个数在左边, 在 start:p-1 中继续寻找 如果 p+1 < k, 则说明第 k 个数在右边，在 p+1:end 中继续寻找 如果 p+1 == k, 则是找到了目标 ## 时间复杂度分析 T(1) = C topKC 函数每次只查一边，另外一边不查，所以是 or T(n) = T(sub_ln) or T(sub_rn) 假设 p 每次正好在中间点上，这样遍历完之后，查找的次数是 n + n/2 + n/4 + n/8 + ..