【leetcode】手撕排序算法，力扣912题的7大排序算法代码归总（纯代码）
前言
🌟🌟本期讲解关于力扣的几篇题解的详细介绍~~~
🌈感兴趣的小伙伴看一看小编主页：GGBondlctrl-ZEEKLOG博客
🔥 你的点赞就是小编不断更新的最大动力
🎆那么废话不多说直接开整吧~~
目录
——前言：本期小编主要是代码的展示，对于每个算法在之前就已经讲解过，那么那就展示吧~~
——分治归并算法讲解：【leetcode】拆解与整合：分治并归的算法逻辑-ZEEKLOG博客
——基础排序算法讲解：【数据结构】关于冒泡排序，选择排序，插入排序，希尔排序，堆排序你到底了解多少？？？（超详解）_堆排序、希尔排序、冒泡排序、选择排序-ZEEKLOG博客
📚️1.超时排序
这里的超时就是针对于912题进行的测试~~~
🚀1.1冒泡排序
直接上代码：
class Solution { public int[] sortArray(int[] nums) { //冒泡排序 for(int i = 0; i < nums.length; i++){ for(int j = 0 ; j < nums.length - 1 - i; j ++){ if(nums[j + 1] < nums[j]){ swap(nums,j+1,j); } } } return nums; } public void swap(int[] nums,int i,int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }大体思路：就是不断遍历我们的数组，然后将最大的值确认到我们的数组最后方，总共要循环数组长度大小次数；
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
运行结果：
🚀1.2插入排序
代码如下：
class Solution { public int[] sortArray(int[] nums) { //插入排序 for(int j = 1; j < nums.length; j++){ int temp = nums[j]; for(int i = j - 1; i >= 0 ; i--){ if(nums[i] > temp){ nums[i + 1] = nums[i]; }else{ break; } nums[i] = temp; } } return nums; } }大体思路：就是在遍历的时候，将遍历区间内的最小数移动到数组最左端；就像是从左向右理扑克牌一样
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：
最坏情况：O(N^2) （5 4 3 2 1）完全逆序
最好情况：O(N) （1 2 3 4 5）完全顺序
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
运行结果：
🚀1.3选择排序
代码如下：
class Solution { public int[] sortArray(int[] nums) { //选择排序 for(int i = 0;i < nums.length; i++){ int midIndex = i; for(int j = i + 1; j < nums.length;j ++){ if(nums[midIndex] > nums[j]){ midIndex = j; } } //与我们的第一个数值进行交换操作 int temp = nums[midIndex]; nums[midIndex] = nums[i]; nums[i] = temp; } return nums; } }大体思路：即遍历完数组确定最小元素下标，与第一个数组第一个值进行交换；
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)（不管排序情况咋样）
3. 空间复杂度：O(1)
4. 稳定性：不稳定
运行结果：
📚️2.通过排序
🚀2.1希尔排序
代码如下所示：
class Solution { public int[] sortArray(int[] nums) { int gap = nums.length; while(gap >= 1){ gap /= 2; shell(nums,gap); } return nums; } //希尔排序，优化插入排序 public void shell(int[] nums,int gap){ for(int j = gap ; j < nums.length; j++){ int temp = nums[j]; for(int i = j - gap ; i >= 0 ; i-=gap){ if(nums[i] > temp){ nums[i + gap] = nums[i]; }else{ break; } nums[i] = temp; } } } }大体思路：其实具体的实现方式主要是对于插入排序的优化，在进行最后的插入操作中，让整个数组的值趋于有序的状态；
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
4.希尔排序是不稳定的排序
运行结果：
🚀2.2堆排序
代码如下：
小根堆
class Solution { public int[] sortArray(int[] nums) { //堆排序 PriorityQueue<Integer> queue = new PriorityQueue<>(); for(int i = 0; i < nums.length;i ++){ queue.offer(nums[i]); } for(int i = 0;i < nums.length; i++){ nums[i] = queue.poll(); } return nums; } }大根堆
class Solution { public int[] sortArray(int[] nums) { //堆排序 PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1); for(int i = 0; i < nums.length;i ++){ queue.offer(nums[i]); } for(int i = nums.length-1;i >= 0; i--){ nums[i] = queue.poll(); } return nums; } }大体思路：就是利用优先级队列的特性；
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
运行结果：
🚀2.3分治排序
代码如下：
class Solution { public int[] sortArray(int[] nums) { //分治 sort(nums,0,nums.length-1); return nums; } //分治操作 public void sort(int[] nums,int l,int r){ //边界判断 if(l >= r){ return; } //找到我们对应的mid; int mid = nums[new Random().nextInt(r - l + 1) + l]; //进行核心分治 int left = l - 1; int right = r + 1; int i = l; while(i < right){ if(nums[i] < mid){ left ++; swap(nums,left,i); i++; }else if(nums[i] == mid){ i++; }else{ right --; swap(nums,right,i); } } //[l left][left + 1 right - 1][right r] sort(nums,l,left); sort(nums,right,r); } public void swap(int[] nums,int left,int right){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } }大体思路：其实就是分为三块，然后对于左右两块进行递归分治操作
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
运行结果：
🚀 2.4归并排序
代码如下：
class Solution { public int[] sortArray(int[] nums) { //归并排序 sort(nums, 0, nums.length - 1); return nums; } public void sort(int[] nums, int left, int right) { //边界判断 if (left >= right) { return; } //获取中间值 int mid = (left + right) / 2; //分治 sort(nums, left, mid); sort(nums, mid + 1, right); //合并 int[] temp = new int[right - left + 1]; int cur1 = left; int cur2 = mid + 1; int i = 0; while (cur1 <= mid && cur2 <= right) { if (nums[cur1] <= nums[cur2]) { temp[i] = nums[cur1]; i++; cur1++; } else { temp[i] = nums[cur2]; i++; cur2++; } } while (cur1 <= mid) { temp[i] = nums[cur1]; i++; cur1++; } while (cur2 <= right) { temp[i] = nums[cur2]; cur2++; i++; } //放到我们的nums数组中 for (int j = left; j <= right; j++) { nums[j] = temp[j - left]; } } }大体思路：就是不断分为一个一个元素，然后再两两合并即可~~
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
运行结果：
📚️3.总结
小小透露一下，某阿里**的笔试题中考到过算法的稳定性哦：
冒泡：稳定 插入：稳定 归并：稳定
选择：不稳定 希尔：不稳定 堆排：不稳定 分治：不稳定
本期主要讲解了关于排序算法的7种解题方式，涉及冒泡，选择，插入，希尔，堆排，分治，并归排序~~~
🌅🌅🌅~~~~最后希望与诸君共勉，共同进步！！！
💪💪💪以上就是本期内容了， 感兴趣的话，就关注小编吧。
😊😊 期待你的关注~~~
