登神长阶
上古神器-常见排序算法
冒泡排序/快速排序/归并排序/非基于比较排序
💰一.前言
为保障知识获取的可读性，以及连贯性，再开始可以适当的重新温习前文内容 ：Java 【数据结构】常见排序算法实用详解（上） 插入排序/希尔排序/选择排序/堆排序【贤者的庇护】
在本篇内容我们将紧跟前篇内容，进一步学习冒泡排序，快速排序，归并排序以及非基于比较排序。
🪙二.冒泡排序
基本原理
冒泡排序是一种简单直观的排序算法，它重复地遍历要排序的列表，一次比较两个元素，并且如果它们的顺序错误就将它们交换位置。这个过程持续到列表没有任何再次交换的元素为止。
算法步骤
- 从列表的第一个元素开始，依次比较相邻的两个元素。
- 如果顺序不正确（例如，前面的元素大于后面的元素），则交换这两个元素。
- 继续对每一对相邻元素进行相同的操作，直到到达列表的末尾。
- 重复以上步骤，每次都从列表的开始处进行，直到没有任何元素需要交换。
时间复杂度
冒泡排序的时间复杂度为O(n^2)，其中n是列表的长度。这是因为在最坏情况下，需要进行n-1轮比较，每一轮最多进行n-1次交换。
冒泡排序是稳定的排序算法。在排序过程中，相同元素的相对位置不会发生变化，只有在相邻元素大小不同时才进行交换。
冒泡排序是一个简单但效率较低的排序算法，通常用于教学目的或者在数据集较小时。由于其时间复杂度较高，在大型数据集上性能不佳，不适合实际应用。然而，由于其实现简单，易于理解和实现，有时在一些特殊场景下可能会被采用。
源代码
/**
* 冒泡排序
* 时间复杂度：
* 不管数据 有序 还是无序 在不优化的情况下：O(N^2) 5 4 3 2 1
* 空间复杂度：O(1)
* 稳定性：稳定
* 目前学到现在为止：2个稳定排序 ，插入排序 冒泡排序
* @param arr
*/
public static void bubbleSort(int[] arr){
for (int i = 0; i arr[j+1]){
swap(arr,j,j+1);
flag=true;
}
}
//在优化了的情况下，当数据有序，1 2 3 4 5
//时间复杂度为：O(N)
if (flag==false){
break;
}
}
}
💴三.快速排序
基本原理
快速排序是一种基于分治思想的排序算法。它的基本思想是选择一个基准元素，然后将数组分割成两个子数组，一个子数组中的所有元素都比基准元素小，另一个子数组中的所有元素都比基准元素大。然后递归地对这两个子数组进行排序。
算法步骤
- 选择一个基准元素（通常是数组中的第一个元素）。
- 将数组分割成两个子数组，一个子数组中的元素都比基准元素小，另一个子数组中的元素都比基准元素大。
- 递归地对两个子数组进行排序。
- 将两个排序好的子数组合并起来。
时间复杂度
快速排序的平均时间复杂度为O(n log n)，其中n是数组的长度。最坏情况下的时间复杂度是O(n^2)，当数组已经有序或者基准元素选择不当时会发生。然而，由于快速排序通常表现良好，因此平均时间复杂度更具代表性。
稳定性
快速排序是不稳定的排序算法。在排序过程中，相同元素的相对位置可能会发生变化。
适用性
快速排序在大多数情况下表现良好，并且通常被认为是最快的排序算法之一（因此得名）。它特别适用于大型数据集的排序，因为其平均时间复杂度相对较低。然而，由于其不稳定性和最坏情况下的性能可能较差，有时可能不适用于特定情况，例如需要稳定排序的场景。
源代码
/**
* 快速排序
* 时间复杂度：O(N*logN)
* 空间复杂度：O(logN)
* 稳定性：不稳定
* @param array
*/
public static void quickSort(int arr[]){//保证接口的统一性
quick(arr,0,arr.length-1);
}
public static void quick(int[] arr,int start,int end){
if (start>=end){
return;
}
//寻找基准元素
int par=partition(arr,start,end);
quick(arr,start,par-1);
quick(arr,par+1,end);
}
在上述代码之中， int par=partition(arr,start,end);有多种方法，在这里我们展开说明三种：
1.挖坑法
/**
* 挖坑法
* @param arr
* @param left
* @param right
* @return
*/
public static int partitionDig(int[] arr,int left,int right){
int temp=arr[left];
while(left 
