十大排序算法分类

本篇分享十大排序算法中的需要进行交换操作的冒泡排序与快速排序 , 其余算法也有介绍噢（努力赶进度中，后续会添加上）

冒泡排序

冒泡排序是一种非常直观的排序算法，遍历数组，每次比较两个元素，如果后者比前者小则交换位置，重复的进行直至没有再需要交换，说明该数组排序完成。冒泡排序的名字由来是因为越小的元素会经过交换慢慢"浮"到数组的顶端。

算法步骤：

核心逻辑

外层循环控制轮数，共进行 n-1 轮遍历，n 为数组长度。
每轮内层循环比较相邻元素 arr[j] 和 arr[j+1]，若前者较大则交换。
每轮结束后，当前未排序部分的最大值会“冒泡”到正确位置（数组末尾）。

优化方法

提前终止：引入boolean变量，如果在某轮内循环未发生交换，说明数组有序，可直接结束排序
减少遍历范围：每轮外层循环后，数组末尾已有序，内层循环无需再比较已排序部分。

终止条件

外层循环完成n - 1次遍历，或boolean = false

动图演示：

性能分析：

时间复杂度：

最好情况：数组已经有序，此时只需要遍历一次，时间复杂度 O(n)
最坏情况：数组完全倒序，此时需要遍历n - 1次，每次遍历都需要进行n - i 次比较可能的交换（i为当前遍历次数），因此时间复杂度为O(n^2)
平均情况：时间复杂度为O(n^2)

空间复杂度：

仅需常数级额外空间因此空间复杂度为O(1)

稳定性：

稳定排序（相等元素不会交换位置）

代码实现（Java）：

/*** 冒泡排序算法实现（升序排序）* @param arr 待排序的整型数组*/
public void bubbleSort(int[] arr) {// 获取数组长度int n = arr.length;// 布尔变量用于    boolean swapped;// 外层循环：控制排序轮数（最多需要 n-1 轮）for (int i = 0; i < n - 1; i++) {// 每轮开始前初始化交换标志为 falseswapped = false;// 内层循环：比较相邻元素并交换// 每轮结束后，最大的元素会"冒泡"到数组末尾，所以比较范围逐渐缩小for (int j = 0; j < n - i - 1; j++) {// 如果前一个元素大于后一个元素（升序排序）if (arr[j] > arr[j + 1]) {// 交换相邻元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;// 标记发生了交换swapped = true;}}// 优化：如果本轮没有发生任何交换，说明数组已经有序，提前结束排序if (!swapped) {break;}}
}

快速排序（挖坑法）

快速排序核心就是选择一个基准值(就是一个作参照的数)，然后将数组分成左右两部分，左边是比基准值小的元素。右边是比基准值大的元素。然后递归地对左右两部分继续进行这个过程，最终整个数组有序

快速排序是通过一次分区就定位一个元素的最终位置，并递归处理两侧子数组

算法步骤：

核心逻辑

首先设定一个基准值（通常是第一个数字/最后一个数字），通过该基准值将数组分成左右两部分。

分区(partition)：将所有小于基准值的元素移到基准值左边，大于的移到右边

递归排序：对左右两个子数组递归进行上述过程

概括来说为挖坑填数 + 分治法

优化方法

采用三数取中法（取左、中、右三个位置的中间值作为基准值）
如果分区后子数组长度小于阈值（如 10）时，直接改用插入排序，减少了递归的开销

终止条件

当left >= right (起始索引大于等于结束索引，子数据长度 <= 1)，终止当前递归（说明该子数组已有序）
所有子数组均完成分区和排序时，整个数组即有序

动图演示：

（借用大佬的动图）

性能分析：

时间复杂度：

时间性能你取决于递归的深度
最好情况：二叉树几乎平衡时，也就是数组划分的比较均匀（基准值位于中间）。，递归次数最少，要log2N 次。递归过程中需要对i，j下标一起扫描数组，所以总体时间复杂度时O(N*log2N)
最坏情况：二叉树极度不平衡，整体时间复杂度达到 (N²)

空间复杂度：

空间性能取决于递归消耗的栈空间
最好情况：已经分析过，需要递归logzN次，空间复杂度为O（logzN）
最坏情况：已经分析过，需要递归N-1次，空间复杂度为O(N)

稳定性：

不稳定

代码实现（Java）：

public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int start, int end) {// 取大于号，防止 start > endif (start >= end) {return;}int pivot = pirtiton1(array, start, end);quick(array, start, pivot - 1);quick(array, pivot + 1, end);}// 挖坑法private static int pirtiton1(int[] array, int left, int right) {int tmp = array[left];while (left < right) {// 为什么判断条件加等号，// 用int[] arr = {5, 7, 3, 1, 4, 9, 6, 5}测试while (left < right && array[right] >= tmp) {right--;}array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}// 将找到的大于基准值的元素填入右边的"坑"array[right] = array[left];}// 将基准值放入最后的"坑"中（此时left == right）array[left] = tmp;return left;}