# Sort 排序

## Sort 排序

### Selection Sort

找右侧最小的加入数组

### Insertion Sort

辅助数组， 一个一个加入，每次加入的时候都找到自己合适的位置插入。 这对于几乎有序的数组和小数组非常好用。

### Quick Sort 快速排序

快排除了打乱之外，最适合手动操作的就是 2-way quick sort 和 3 - way quick sort

#### 2-way Quick Sort

相关题目： [LC215](https://zichao-yang.gitbook.io/leetcode-zichao/leetcode-p201-300/leetcode-215-kth-largest-element-in-an-array) Method 2 的 Quick Select

#### 3-way Quick Sort

相关题目： [LC075](https://zichao-yang.gitbook.io/leetcode-zichao/leetcode-p001-100/leetcode-075-sort-colors) 这是 3-way Quick Sort 的典型应用

## 线性时间复杂度的排序算法

常见的能达到线性时间复杂度的排序算法有基数排序 Radix Sort，计数 Counting Sort 排序和桶排序。

### Bucket Sort 桶排序

分析参见 347 [LC347](https://zichao-yang.gitbook.io/leetcode-zichao/leetcode-p301-400/leetcode-347-top-k-frequent-elements) [LC451](https://zichao-yang.gitbook.io/leetcode-zichao/leetcode-p401-800/leetcode-451-sort-charactersby-frequency) 164 <https://www.cxyxiaowu.com/587.html> 692

一个不典型的题目，041，为桶排序提供了一种可能。

### Radix Sort

### Sort 应用

179
