快速回忆十大排序
Java 中 Arrays.sort()
通过查看 Arrays.sort() 的源码， 可以发现 Arrays.sort() 并不是简单的使用快排，而是根据要排序的长度选择不同的排序。 简单总结：
| 区间长度 | 所使用的排序算法 |
|---|---|
| 小于 47 | 插入排序 |
| 大于 47 小于 286 | 快排排序 |
| 大于 286，数据基本有序 | 归并排序 |
| 大于 286，数据基本无序 | 快速排序 |
进行快排时会计算 5 个元素如果有相同元素就进行传统快速排序 ，如果没有相同的就进行双轴快速排序。
插入排序、归并排序、快速排序连源码都在用可见其重要性。
经典十大排序
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(n log n) | O(n log2 n) | O(n log2 n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n2) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
| 桶数排序 | O(n+k) | O(n2) | O(n) | O(n+k) | 稳定 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
不稳定是指排序过程中会把原本有序区间破化成无序的
排序测试力扣题目
力扣 912.排序数组，地址： https://leetcode.cn/problems/sort-an-array/ 除了冒泡、插入会超时以外，其他排序方式都可以通过。
1. 冒泡排序
这应该是大家接触最早的排序。数就像水里的泡泡一样，泡泡从大到小一个个冒出来。 数组形式： [无序区间] [有序区间] ，在无序区间一直比较并交换把最大的冒到有序区间前。 两层 for 循环，一层循环将一个最大的数放到最后。 动图演示： 
Java 代码
for(int i = 0; i < nums.length; i++) {
for(int j = 0; j < nums.length - 1 - i; j++) {
if(nums[j] > nums[j + 1]) {
//交换
int tem = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tem;
}
}
}2. 选择排序
插入排序总结一句话就是挑最小的放前面，比较的次数多但是交换的次数少 数组形式： [有序区间] [无序区间] ，在无序区间挑一个最小的数跟在有序区间后面。 两层 for 循环，一层循环用来找到最小的数。 动图演示： 
Java 代码：
int minIndex = 0;
for(int i = 0; i < nums.length - 1; i++) {
minIndex = i;
for(int j = i + 1; j < nums.length; j++) {
if(nums[j] < nums[minIndex]) {
minIndex = j;
}
}
//找到最小数的索引，交换
int tem = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = tem;
}3. 插入排序
插入排序总结：拿到一个元素就去找他该在的位置插入进去 数组形式： [有序区间] [无序区间] ，在无序区间拿第一个元素插入到有序区其应该在的位置 从右往左，放第一个比他小的后面，且从右往左遍历过程中把数组右移。
动图演示： 
Java 代码：
for(int i = 1; i < nums.length; i++) {
int index = i - 1;
int tem = nums[i];
while(index >= 0 && nums[index] > tem) {
nums[index + 1] = nums[index]; //右移
index--;
}
nums[index + 1] = tem; //把无序部分第一个数插入到有序部分的这里
}4. 希尔排序
希尔排序是当时最早突破 O(n2)的排序，是插入排序的改进版本。 插入排序主要在于右移是 O(n) 希尔排序的思想是引入一个增量，先两两插入排序，再四四插入排序，最终整体插入排序，这样前面处理完，后面插入移动次数会变少。 每一轮按照事先决定的间隔进行插入排序，间隔依次缩小最后为 1。 动图演示： 
如果看不懂这个动图，可以先看看这个教程，再回头看这个动图。https://www.runoob.com/data-structures/shell-sort.htmlJava 代码：
for(int gap = nums.length / 2; gap > 0; gap /= 2) {
//对每组进行插入排序。 这里和动图不太一样，并不是一组一组进行的，而是各组交叉进行的
for(int i = gap; i < nums.length; i++) {
int tem = nums[i];
int index = i;
while(index >= gap && nums[index - gap] > tem) {
//按分组的位置右移
nums[index] = nums[index - gap];
index -= gap;
}
nums[index] = tem;
}
}
return nums;5. 归并排序
希尔排序是分治法的一个典型应用，将已有序的子序列合并，得到完全有序的序列；
动图演示： 
更直观的图片演示： 
Java 代码：
int[] tem;
public int[] sortArray(int[] nums) {
tem = new int[nums.length];
mergeSort(nums, 0, nums.length - 1);
return nums;
}
void mergeSort(int[] nums, int l, int r) {
if(l >= r) return;
int mid = (l + r) / 2;
//分
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
//治(归并)
int i = l, j = mid + 1;
int index = 0;
while(i <= mid && j <= r) {
if(nums[i] <= nums[j]) {
tem[index++] = nums[i++];
}else {
tem[index++] = nums[j++];
}
}
while(i <= mid) tem[index++] = nums[i++];
while(j <= r) tem[index++] = nums[j++];
//把归并完成的这部分赋值回给原始数组
for(int k = 0; k < r - l + 1; k++) {
nums[k + l] = tem[k];
}
}6. 快速排序
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小， 然后再分别对这两部分记录继续进行排序，以达到整个序列有序。 数组形式： [小数] [基准元素] [大数]，在区间中随机挑选一个元素作为基准，小于基准元素的放基准之前，大于基准的放基准之后。 然后再对小数和大数区间做快排
整个流程就是找到基准点应该放置的位置。
动图演示： 
Java 代码：
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int[] nums, int left, int right) {
//顺序选取基准值
if(left >= right) return;
int first = left, key = nums[first], end = right;
while (first < end) {
//先看右边的， 比基准大就不管
while (first < end && nums[end] >= key) {
end--;
}
//右边end指向的这个值小于分界值， 交换.
nums[first] = nums[end];
//然后走左边
while (first < end && nums[first] <= key) {
++first;
}
//如果first指针指向的值大于分界值key, 交换
nums[end] = nums[first];
}
// 左右指针相同， 基准值该在这个位置，使得基准值左右两边是比他小和比他大的数
nums[first] = key;
//递归， 对左右两边再进行上面操作
quickSort(nums, left, first - 1);
quickSort(nums,first + 1, right);
}如果遇到数组是 9 8 7 6 5 4 3 2 1， 再从左往右顺序选取基准值的话，每次都得移动 n 个， 算法时间复杂度退回到 O(n2)。 所以最好是随机选取基准，或者提前打乱数组，数组越乱，快排越快 随机选取基准值，快排代码：
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int[] nums, int left, int right) {
if(left >= right) return;
//随机选取基准值
int index = left + (int)(Math.random() * (right - left + 1));
int key = nums[index];
int first = left, end = right;
nums[index] = nums[first];
nums[first] = key;
while (first < end) {
//先看右边的， 比基准大就不管
while (first < end && nums[end] >= key) {
end--;
}
//右边end指向的这个值小于分界值， 交换.
nums[first] = nums[end];
//然后走左边
while (first < end && nums[first] <= key) {
++first;
}
//如果first指针指向的值大于分界值key, 交换
nums[end] = nums[first];
}
// 左右指针相同， 基准值该在这个位置，使得基准值左右两边是比他小和比他大的数
nums[first] = key;
//递归， 对左右两边再进行上面操作
quickSort(nums, left, first - 1);
quickSort(nums,first + 1, right);
}7. 堆排序
利用小顶堆。
待补充
8. 计数排序
记录索引位置数的个数，利用索引本身就有序进行排序。 有一个缺点就是得事先知道数据得范围，范围多大就得开多大数组。 动图演示： 
Java 代码：
public int[] sortArray(int[] nums) {
int[] dic = new int[100001];
for(int i = 0; i < nums.length; i++) {
dic[nums[i] + 50000]++;
}
int index = 0;
for(int i = 0; i < dic.length; i++) {
for(int j = 0; j < dic[i]; j++) {
nums[index++] = i - 50000;
}
}
return nums;
}9. 桶排序
桶排序是计数排序的升级版， 计数排序是一对一的映射，而桶排序是一对多的映射，把数据分到不同的桶里的元素用其他排序方式排序。 动图演示：
Java 代码：
public int[] sortArray(int[] nums) {
int n = nums.length;
int max = nums[0], min = nums[0];
for(int i = 0; i < n; i++) {
if(nums[i] > max) max = nums[i];
if(nums[i] < min) min = nums[i];
}
int diff = max - min;
//设n个桶
List<Integer>[] buket = new List[n];
for(int i = 0; i < n; i++) {
buket[i] = new ArrayList<>();
}
//每个桶的范围，防止为0
int section = diff / n + 1;
for(int i = 0; i < n; i++) {
int id = (nums[i] - min) / section - 1; // -1防止等于 n
if(id < 0) id = 0;
buket[id].add(nums[i]);
}
//桶内排序
for(int i = 0; i < n; i++) {
Collections.sort(buket[i]);
}
//返回排序数组
int index = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < buket[i].size(); j++) {
nums[index++] = buket[i].get(j);
}
}
return nums;
}10. 基数排序
基数排序是桶排序的扩展， 思想是把整数按每位不同放入不同的桶里，按每位进行比较。 比如 32，34，16， 5 排序， 先按个位数排序 32，34，5，16， 再按十位排序 5，16，32，34 就完事了 【因为之前按个位排序时把 32 放在了 34 前面，所以再进行十位排序时，按顺序来 32 自然在 34 前面】 动图演示： 
Java 代码：
public int[] sortArray(int[] nums) {
List<Integer>[] buket = new List[10];
for(int i = 0; i < 10; i++) buket[i] = new ArrayList<>();
// 把负数全部转化成正数处理
int max = nums[0] + 50000;
//得到最大的数
for(int t : nums) if(t + 50000 > max) max = t + 50000;
//从个位到最高位
int len = String.valueOf(max).length(); //最高位位数
for(int i = 0; i < len; i++) {
//入桶
for(int t : nums) {
buket[((t + 50000) / (int)Math.pow(10, i)) % 10].add(t + 50000);
}
//出桶
int index = 0;
for(int j = 0; j < 10; j++) {
for(int k = 0; k < buket[j].size(); k++) {
nums[index++] = buket[j].get(k) - 50000;
}
buket[j].clear(); //清空桶
}
}
return nums;
}对链表进行排序
如果你掌握了 插入排序、快速排序、归并排序的精髓，那么试试这三种方法对链表进行排序吧 狂刷三道力扣中等题： 力扣 147. 对链表进行插入排序力扣 148. 排序链表力扣 剑指 Offer II 077. 链表排序
1. 插入排序 O(n2)
插入排序： 【有序】【无序】 无序部分找最小值放有序后头
直接上 Java 代码：
public ListNode insertionSortList(ListNode head) {
//由于链表只能从前往后遍历，所以只能从前往后遍历找插入位置
//没有元素或者只有一个元素直接返回
if(head == null || head.next == null) return head;
ListNode dump = new ListNode();
dump.next = head;
ListNode lastNode = head;//有序节点的最后一个节点
ListNode cur = head.next;
while(cur != null) {
if(cur.val >= lastNode.val) {
//直接往后走
lastNode = lastNode.next;
}else {
ListNode pre = dump;
while(pre.next.val < cur.val) {
pre = pre.next;
}
//lastNode 不变，但是lastNode下一个数被插入前面了，
lastNode.next = cur.next;
cur.next = pre.next;
pre.next = cur;
}
cur = lastNode.next;
}
lastNode.next = null;
return dump.next;
}2.快速排序 O(n log n)
快速排序： 【小数】【基准元素】【大数】，所有小数移动到基准元素左边，大数移动到基准元素右边
直接上 Java 代码： 对于力扣 148. 排序链表，快排超时了。
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode dump = new ListNode();
dump.next = head;
return quickSort(dump, null);
}
ListNode quickSort(ListNode headPre, ListNode end) {
if(headPre == end || headPre.next == end || headPre.next.next == end) return headPre;
//将小于基准值的节点存在这个临时链表中
ListNode temDump = new ListNode();
ListNode tp = temDump;
//key 为基准节点，基准节点左边是比他小的，右边是比他大的
ListNode key = headPre.next, lp = headPre;
while(lp.next != end) {
if(lp.next.val < key.val) {
//节点值小于基准节点，就把这个节点放到左边
tp.next = lp.next;
tp = tp.next;
lp.next = lp.next.next;
}else {
lp = lp.next;
}
}
//合并大小两个链表
tp.next = key;
//整个链表用headPre连回来
headPre.next = temDump.next; // 链表插回原链表（如果不做这一步，处理右半部分的时候就断了）
quickSort(headPre, key);
quickSort(key, end);
return headPre.next;
}2.归并排序 O(n log n)
链表排序最好就是用归并排序， 链表的归并排序不需要额外空间 归并，分治
归并排序需要不断的把链表分为两段，分为两段的方法可以用快慢指针，快指针溢出走两步，慢指针一次走一步，快指针走到头慢指针指向中间节点。
直接上 Java 代码：
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
return mergeSort(head);
}
ListNode mergeSort(ListNode head) {
if(head.next == null) return head;
// 分
//找中间节点
ListNode fast = head, slow = head, pre = null;//pre 是slow节点的前一个节点
while(fast != null && fast.next != null) {
fast = fast.next.next;
pre = slow;
slow = slow.next;
}
pre.next = null; //断链， 现在head只有一半链表, slow 是另一半链表
ListNode left = mergeSort(head); // 继续把head这一半进行分半
ListNode right = mergeSort(slow); //继续把slow这一半进行分半
//治
//left、 right都是从最小（一个节点）回溯到最长（一半）
//合并left、right
ListNode dump = new ListNode();
ListNode cur = dump;
while(left != null && right != null) {
if(left.val <= right.val) {
cur.next = left;
left = left.next;
cur = cur.next;
}else {
cur.next = right;
right = right.next;
cur = cur.next;
}
}
if(left != null) cur.next = left;
if(right != null) cur.next = right;
return dump.next;
}
}