参考链接：
排序算法作为数据结构中重要的组成部分，必须要掌握。
1. 相关术语介绍
排序：将一序列对象根据某个关键字进行排序。
稳定排序：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
非稳定排序：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此需要把数据放在磁盘中，而排序需要通过磁盘和内存的数据传输才能进行；
时间复杂度：排序所耗费的时间；
空间复杂度：排序所耗费的内存；
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
2. 排序算法分类以及对应复杂度
2.1 排序算法分类
2.1.1 按照比较类排序、非比较类排序进行分类
-
比较类排序：
? ? ? ?常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置 。在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n2)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
? ? ? ?优势：适用于各种规模的数据，不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
-
非比较类排序
? ? ? ?计数排序、基数排序、桶排序则属于非比较排序 。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置 。
? ? ? ?非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置，所以对数据规模和数据分布有一定的要求。
2.1.2 按照内部排序、外部排序进行分类
其他分类待完善
2.2 不同排序算法的复杂度以及稳定性
图片名词解释：
-
n: 数据规模
-
k: “桶”的个数
-
In-place: 占用常数内存，不占用额外内存
-
Out-place: 占用额外内存
3. 冒泡排序/相邻比序法---交换排序
3.1 算法思想
? ? ? ?冒泡排序是一种简单的排序算法。它通过重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换的，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。即：从要排序序列的第一个元素开始，依次比较相邻元素的值，发现逆序则交换，将值较大的元素逐渐从前向后移动。
3.2 实现逻辑
主要通过两层循环实现
-
外层循环代表需要比较几轮/趟，即每次将最大的一个数放到最后所需要的次数， 即需要元素个数-1趟；
-
内层循环代表两两需要对比多少次，比如n个数据第1次两两比较需要n-1次，第2次两两比较需要n-2次，以此类推。
举例：
3.3 Java代码实现
?package sort;
??
?import java.util.Arrays;
??
?/**
? * @ClassName BubbleSort
? * @Description 冒泡排序
? * @Author Jiangnan Cui
? * @Date 2022/10/19 0:11
? * @Version 1.0
? */
?public class BubbleSort {
? ? public static void main(String[] args) {
? ? ? ? int[] arr = {3,9,-1,10,20};
? ? ? ? System.out.println("原始数组：");
? ? ? ? for (int i : arr) {
? ? ? ? ? ? System.out.print(i + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? int[] bubbleSortResult = bubbleSort(arr);
? ? ? ? System.out.println("排序后新数组为：");
? ? ? ? for (int i : bubbleSortResult) {
? ? ? ? ? ? System.out.print(i + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? ? ? int[] bubbleSortResult2 = bubbleSort2(arr);
? ? ? ? System.out.println("排序优化后新数组为：");
? ? ? ? for (int i : bubbleSortResult2) {
? ? ? ? ? ? System.out.print(i + " ");
? ? ? ? }
??
? ? }
??
? ? /**
? ? ? * @MethodName bubbleSort
? ? ? * @Description 冒泡排序
? ? ? * @param: arr
? ? ? * @return: int[]
? ? ? * @Author Jiangnan Cui
? ? ? * @Date 0:31 2022/10/19
? ? ? */
? ? public static int[] bubbleSort(int[] arr){
? ? ? ? // 数组中不包含或只包含1个元素时，直接返回
? ? ? ? if(arr.length == 0 || arr.length == 1){
? ? ? ? ? ? return arr;
? ? ? ? }
? ? ? ? // 数组中多于1个元素时进行冒泡排序
? ? ? ? // 外层循环控制循环趟数
? ? ? ? for (int i = 0; i < arr.length - 1; i++) {
? ? ? ? ? ? // 内层循环控制两两两比较次数
? ? ? ? ? ? for (int j = 0; j < arr.length - 1 - i; j++) {
? ? ? ? ? ? ? ? // 前一个元素大于后一个元素时，进行交换
? ? ? ? ? ? ? ? if (arr[j] > arr[j + 1]) {
? ? ? ? ? ? ? ? ? ? swap(j, j+1, arr);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return arr;
? ? }
??
? ? /**
? ? ? * @MethodName bubbleSort2
? ? ? * @Description 冒泡排序优化：如果某趟排序中，没有发生交换，则可结束排序
? ? ? * @param: arr
? ? ? * @return: int[]
? ? ? * @Author Jiangnan Cui
? ? ? * @Date 0:31 2022/10/19
? ? ? */
? ? public static int[] bubbleSort2(int[] arr){
? ? ? ? // 数组中不包含或只包含1个元素时，直接返回
? ? ? ? if(arr.length == 0 || arr.length == 1){
? ? ? ? ? ? return arr;
? ? ? ? }
? ? ? ? boolean flag = false;// 标志位，用来表示没有发生过交换
? ? ? ? // 数组中多于1个元素时进行冒泡排序
? ? ? ? // 外层循环控制循环趟数
? ? ? ? for (int i = 0; i < arr.length - 1; i++) {
? ? ? ? ? ? // 内层循环控制两两两比较次数
? ? ? ? ? ? for (int j = 0; j < arr.length - 1 - i; j++) {
? ? ? ? ? ? ? ? // 前一个元素大于后一个元素时，进行交换
? ? ? ? ? ? ? ? if (arr[j] > arr[j + 1]) {
? ? ? ? ? ? ? ? ? ? swap(j, j+1, arr);
? ? ? ? ? ? ? ? ? ? flag = true;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? // 某趟没有发生过交换，直接结束排序
? ? ? ? ? ? if(!flag){
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? } else{
? ? ? ? ? ? ? ? flag = false;// 发生过交换时，重置标志位，方便下次判断
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return arr;
? ? }
??
? ? /**
? ? ? * @MethodName swap
? ? ? * @Description 交换数组中的两个元素
? ? ? * @param: i
? ? ? * @param: j
? ? ? * @param: arr
? ? ? * @Author Jiangnan Cui
? ? ? * @Date 0:19 2022/10/19
? ? ? */
? ? private static void swap(int i, int j,int[] arr) {
? ? ? ? int temp = arr[i];
? ? ? ? arr[i] = arr[j];
? ? ? ? arr[j] = temp;
? ? }
?}
输出结果：
?原始数组： ?3 9 -1 10 20 ?排序后新数组为： ?-1 3 9 10 20 ?排序优化后新数组为： ?-1 3 9 10 20
3.4 复杂度分析
时间复杂度：总共执行次数n-1,n-2,......，2,1，等差数列求和为n*(n-1)/2，即最高次项为n^2，故时间复杂度为O(n^2）；
-
最佳情况：O(n)，即第1趟循环时发现已经排好序了
-
最差情况：O(n^2)，所有情况均执行。
-
平均情况：O(n^2)
空间复杂度：有限个变量占用空间i、j，故时间复杂度为O(1)；
稳定性分析：相同元素比较时不交换顺序，故稳定。
其他排序算法待完善