前言
排序种类繁多，大致可以分为两大类：
-
比较类排序：属于非线性时间排序，时间复杂度不能突破下界 (O(nlogn));
-
非比较类排序：能达到线性时间 (O(n))，不是通过比较来排序，有基数排序、计数排序、桶排序。
了解一个概念：排序的稳定性
稳定是指相同大小的元素多次排序能保证其先后顺序保持不变。假设有一些学生的信息，我们先根据他们的姓名进行排序，然后我们还想根据班级再进行排序，如果这时使用的时不稳定的排序算法，那么第一次的排序结果可能会被打乱，这样的场景需要使用稳定的算法。
堆排序、快速排序、希尔排序、选择排序是不稳定的排序算法，而冒泡排序、插入排序、归并排序、基数排序是稳定的排序算法。
1、冒泡排序
大多数人学编程接触的第一种排序，名称很形象。每次遍历排出一个最大的元素，将一个最大的气泡冒出水面。
- 时间复杂度：平均：(O(n^2))；最好：(O(n))；最坏：(O(n^2))
- 空间复杂度：(O(1))
public static void bubbleSort(int[] arr) {
/**
* 总共走len-1趟即可，每趟排出一个最大值放在最后
*/
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tp;
}
}
}
}
2、选择排序
最直观易理解的排序算法，每次排出一个最小的元素。也是最稳定的算法，时间复杂度稳定为O(n^2)。需要一个变量记录每次遍历最小元素的位置。
- 时间复杂度：(O(n^2))
- 空间复杂度：(O(1))
public static void selectSort(int[] arr){
int n = arr.length;
for (int i = 0; i < n; i++) {
int maxIdx = 0;
for(int j = 1; j < n - i; j++){
if(arr[maxIdx] < arr[j]){
maxIdx = j;
}
}
int tp = arr[maxIdx];
arr[maxIdx] = arr[n - 1 - i];
arr[n - 1 - i] = tp;
}
}
3、插入排序
一种直观的排序算法，从第二个元素开始，每次往前面遍历找到自己该在的位置。
- 时间复杂度：平均：(O(n^2))；最好：(O(n))；最坏：(O(n^2))
- 空间复杂度：(O(1))
public static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
for(int j = i; j > 0 && arr[j] < arr[j-1]; j--){
int tp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tp;
}
}
}
4、希尔排序
是第一个突破O(n^2)复杂度的算法，是插入排序改进版，又称缩小增量排序。选择一个增量g，每次将数据按g分隔分成g组，每次对组内进行插入排序。每组排完后，将g/2继续直到g=1。一般选择g=len/2，但这不是最优选择，还有很多增量选择方案。
- 时间复杂度：基于不同增量选择--O(n1.3~n2)
- 空间复杂度：O(1)
public static void shellSort(int[] arr){
for(int g = arr.length/2; g > 0; g /= 2){
for(int i = g; i < arr.length; i++){
for(int j = i; j - g >= 0 && arr[j] < arr[j - g]; j -= g){
int tp = arr[j];
arr[j] = arr[j-g];
arr[j-g] = tp;
}
}
}
}
5、快速排序
是冒泡排序的一种改进算法。
基本思想是：
- 在数据集之中，选择一个元素作为"基准"（pivot）。
- 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
- 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
经典的快排选择第一个数为基准。当排的是一个近乎有序的序列时，经典快排会退化为(O(n^2))，这时采用随机快速排序则比较恰当，随机快排是在排序的数中随机选择一个做基准。快排可以做到原地实现。
-
时间复杂度：平均（理想）：(O(nlogn))；最坏：(O(n^2));
每一层递归都需要比较n次，如果理想情况都是五五开，那么递归深度就是(logn)，如果最坏的情况递归深度就是n。
-
空间复杂度：每次快排需要一个额外的空间，因此空间复杂度=递归深度=(O(logn))或者(O(n)).
-
实现：
形象点叫-填坑法，这个实现是《算法》里提到的，我觉得最简洁。
public static void quick(int a[], int lo, int hi){ if( lo >= hi) return; int x = a[lo]; int i = lo, j = hi; while (i < j){ while (i < j && a[j] > x){ j--; } if(i < j){ a[i++] = a[j]; } while (i < j && a[i] < x){ i++; } if(i < j){ a[j--] = a[i]; } } a[i] = x; quick(a, lo, i-1); quick1(a, i+1, hi); } -
多路快排：
当序列中有大量重复元素时，原算法也会退化，这时需要双路快速排序，甚至是三路快排，三路快排在重复元素时表现出很好的性能，在普通的，非大量重复时，速度略慢于普通快排，不过在可接受范围，因此一般使用三路快排。
6、归并排序
归并的思想是先使每个子序列有序，再使得子序列合并后有序。与快排一样，都基于分治思想，不过快排在于分，而归并在于合。
是一个稳定的算法。一般归并的比较次数少于快排，而移动次数多于快排。(所以这是计算机中多用快排的原因，移动数据的代价更高)。对于本身具有一定有序性的序列，可以采用改进的归并，最好的情况能将复杂度降低至O(n).
归并还有一个用途：用于求逆序数。
- 时间复杂度：一直是(O(nlogn))
- 空间复杂度：(O(n))，需要一个一样大的辅助数组
《算法》上看到的写法，非常优雅：
static void sort(int[] arr, int lo, int hi, int[] temp){
if(lo >= hi) return;
int mid = lo + (hi - lo)/2;
// 小技巧，递归时将数组反过来复制，temp->arr，这样不用每次都将排好序的temp复制回arr
sort(temp, lo, mid, arr);
sort(temp, mid + 1, hi, arr);
merge(arr, lo, mid, hi, temp);
}
static void merge(int[] arr, int lo, int mid, int hi, int[] temp) {
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) temp[k] = arr[j++];
else if(j > hi) temp[k] = arr[i++];
else if(arr[i] > arr[j]) temp[k] = arr[j++];
else temp[k] = arr[i++];
}
}
7、堆排序
这里特指二叉堆，二叉堆是一种完全二叉树，并且所有结点的值大于(小于)等于子节点的值，分别称为大(小)顶堆。下面以大顶堆为例讲述。
首先我们要知道，完全二叉树和数组可以相互映射，通过下标可以找到节点的子节点，节点i的左子节点为：2i+1；右子节点为：2i+2。通常我们排序的是数组，就将其映射成完全二叉树来实现。
堆排序就是给定了一个无序的序列，先将其构造成一个大顶堆，然后将大顶堆的堆顶元素与最后一个元素交换，那么第一个数就排好了，然后逐个排序
-
建堆过程
常见的建堆有两种方法，一种是应用于堆元素已经确定了的，另外一种是针对元素动态增加的。
对于元素已经确定的我们通常做法是这样的：
a. 先找到这颗完全二叉树的最后一个非叶子节点的位置 k：(size/2 - 1);如上图就是 9/2-1=3.
b. 以这个节点作为根节点构造一个二叉堆，找出该节点和其子节点中最大的节点，并将堆顶交换为最大的那个节点。
c. 然后前移找前一个非叶子节点，也重复步骤b。直到整个树都被构造成二叉堆，堆就建好了。
public static void buildHeap(int[] arr){ for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, arr.length); } }关键是调整代码：
// 截取原来的二叉树，调整以 i 为根节点的堆 private static void adjustHeap(int[] arr, int i, int len){ int left = 2*i + 1, right = 2*i +2; int maxIndex = i; if(left<len && arr[left] > arr[maxIndex]){ maxIndex = left; } if(right<len && arr[right] > arr[maxIndex]){ maxIndex = right; } if(maxIndex != i){ swap(arr,maxIndex,i); adjustHeap(arr, maxIndex, len); } } -
排序
建好堆后，堆顶就是最大的元素，我们取堆顶元素，将其与堆末尾元素交换，然后我们将原本堆的末尾元素剔除，堆元素减一，此时由于交换使得堆需要再次调整。调整完后堆顶元素即为第二大元素，然后交换到第二末尾的位置，剔除，调整堆...直到堆的大小变为1，排序完成。
完整代码：
public static void heapsort(int[] arr) {
buildHeap(arr);
for (int i = arr.length - 1; i > 0; i--) {
swap(arr,0,i);
adjustHeap(arr, 0, i);
}
}
private static void buildHeap(int[] arr){
// len/2-1 是最后一个非叶子节点的下标
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
}
private static void adjustHeap(int[] arr, int i, int len){
int left = 2*i + 1, right = 2*i +2;
int maxIndex = i;
if(left<len && arr[left] > arr[maxIndex]){
maxIndex = left;
}
if(right<len && arr[right] > arr[maxIndex]){
maxIndex = right;
}
if(maxIndex != i){
swap(arr,maxIndex,i);
adjustHeap(arr, maxIndex, len);
}
}
private static void swap(int[] arr, int i, int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
-
堆排序时间复杂度稳定在O(nlogn)，看起来堆排序比快速排序还要好？
但实际上计算机中排序还是没有采用它，它的实际效率还是低于快速排序。因为排序的时间不仅要考虑实际cpu计算的时间，还要考虑数据读取的时间，计算机中采用的cache机制使得一次不能读取很多数据，数据一般是分段读入cache的，快排进行计算时使用的数据具有良好的局部性(这些数据一般挨得很近)，而堆排序由于经常同时操作树头和树尾的数据，这些数据通常隔得比较远，所以需要花很多时间在数据读取上，整体效率还下降了。
-
时间复杂度：(O(nlogn))
建堆的复杂度为(O(n)),排序时重建堆的复杂度为(O(nlogn)).
-
空间复杂度：(O(1))
8、计数排序
计数排序是非比较型排序，适用于具有确定范围的序列。计数排序新建了一个k=maxval-minval大小的数组用来统计各个数出现次数。是一个稳定的排序算法，当序列比较集中时，它优于所有的比较排序算法。但当(O(k)>O(n*logn))时，效率反而不如比较型算法。
- 时间复杂度：(O(n+k))
- 空间复杂度：(O(k))
public static void countSort(int[] arr) {
// 假设arr[i]都在0-99范围内
int[] space = new int[100];
for (int i = 0; i < arr.length; i++) {
space[arr[i]]++;
}
for (int i = 0, j = 0; i < space.length; i++) {
while (space[i]-- > 0){
arr[j++] = i;
}
}
}
9、桶排序
划分多个范围相同的区间，每个子区间自排序，最后合并。
桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素。而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。
一般的做法是，找到排序的序列所在区间，平均分成几个区域（即几个桶），然后根据映射关系将数逐一放入桶内，对每个入桶的数据在该桶内还要进行排序（可以自选排序算法），然后依次取出桶中数据得到有序数列。
当数据服从均匀分布时，该算法线性时间O(n)，如果数据很集中，当所有数据集中在同一个桶中时，桶排序就失去了意义。
桶排序的关键：
元素值域的划分，也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择，若规则设计的过于模糊、宽泛，则可能导致待排序集合中所有元素全部映射到一个桶上，则桶排序向比较性质排序算法演变。若映射规则设计的过于具体、严苛，则可能导致待排序集合中每一个元素值映射到一个桶上，则桶排序向计数排序方式演化。
-
时间复杂度：
对于待排序序列大小为 N，共分为 M 个桶，主要步骤有：
N 次循环，将每个元素装入对应的桶中
M 次循环，对每个桶中的数据进行排序（平均每个桶有 N/M 个元素）
假如桶内排序算法时间复杂度为(O(NlogN))，那么总复杂度为：
(O(N)+O(M*(N/M*log(N/M)))=O(N+N*log(N/M)))
当M=N时，复杂度则为O(N),完全退化为计数排序。
-
空间复杂度：(O(N+M))
public static void bucketSort(int[] arr) {
int max = Integer.MIN_VALUE,
min = Integer.MAX_VALUE;
for (int i : arr) {
max = Math.max(max,i);
min = Math.min(min,i);
}
int bucketNum = (max-min)/arr.length + 1;
List<List<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<>());
}
for (int i = 0; i < arr.length; i++) {
int index = (arr[i] - min) / arr.length;
bucketArr.get(index).add(arr[i]);
}
for (int i = 0; i < bucketArr.size(); i++) {
Collections.sort(bucketArr.get(i));
}
for (int i = 0, j = 0; i < bucketArr.size(); i++) {
for (int i1 = 0; i1 < bucketArr.get(i).size(); i1++) {
arr[j++] = bucketArr.get(i).get(i1);
}
}
}
10、基数排序
基数排序是逐位进行排序的算法。先按照低位先排序，排好后收集，再逐次升高位数进行排序，收集，直到最高位，收集后即为有序序列。相当于用十个桶进行排序，又称为桶子法。其排序效率取决于最大数的位数d，每位数字的分布范围k（0-9）,一般k=10。
- 时间复杂度：(O(d*(n+k)))
- 空间复杂度：取决于桶的数量 (O(k+n))
public static void baseSort(int[] arr) {
// 取得最大数的位数
int digits = 3;
List<List<Integer>> tong = new ArrayList<>(10);
for (int i = 0; i < 10; i++) {
tong.add(new ArrayList<>());
}
int mod = 10, dev = 1;
for (int i = 0; i < digits; i++, dev *= 10, mod *= 10) {
for (int j = 0; j < arr.length; j++) {
int index = (arr[j] % mod) / dev;
tong.get(index).add(arr[j]);
}
for (int j = 0, index = 0; j < tong.size(); j++) {
while (!tong.get(j).isEmpty()){
arr[index++] = tong.get(j).get(0);
tong.get(j).remove(0);
}
}
}
}
外部排序
前述排序都是指直接在内存中可以完成的，即内部排序。外部排序是指数据量很大，需要多次从磁盘读入的情况。
外部排序一般使用归并算法，为了提高效率，并且通常是多路归并。