【leetcode】手撕排序算法，力扣912题的7大排序算法代码归总（纯代码）
【leetcode】手撕排序算法，力扣912题的7大排序算法代码归总（纯代码）
——前言：本期小编主要是代码的展示，对于每个算法在之前就已经讲解过，那么那就展示吧~~ ——分治归并算法讲解：【leetcode】拆解与整合：分治并归的算法逻辑-CSDN博客 ——基础排序算法讲解：【数据结构】关于冒泡排序，选择排序，插入排序，希尔排序，堆排序你到底了解多少？？？（超详解）_堆排序、希尔排序、冒泡排序、选择排序-CSDN博客
📚️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.总结
小小透露一下，某阿里**的笔试题中考到过算法的稳定性哦：
冒泡：稳定 插入：稳定 归并：稳定
选择：不稳定 希尔：不稳定 堆排：不稳定 分治：不稳定
腾讯云开发者
