介绍交换排序中的冒泡排序与快速排序，以及归并排序。详细讲解快速排序的三种分区方法（Hoare、挖坑法、前后指针法）、优化策略（三数取中、小区间插入排序）及非递归实现。对比多种排序算法的时间复杂度、空间复杂度及稳定性，帮助理解不同场景下的排序选择。
基本思想：将待排序的元素看做是'气泡'，比较相邻两个元素进行交换，每次遍历都会将当前最大（最小）的元素像'气泡'一样，浮到一端。
实现过程：
代码：
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
boolean flg = false;
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
flg = true;
}
}
if (!flg) {
break;
}
}
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
基本思想
基本思想：任取待排序元素序列中的某元素作为基准值，通过一趟排序将待排序集合分割成两个子序列，左子序列中的所有元素均小于基准值，右子序列中的所有元素均大于基准值，然后对左右子序列重复该过程，直到所有元素在相应的位置上。
public static void quickSort(int[] array) {
// 快速排序入口
quick(array, 0, array.length - 1);
}
public static void quick(int[] array, int start, int end) {
// 递归结束条件
if (start >= end) {
return;
}
// 划分区间
int pivot = partition(array, start, end);
quick(array, start, pivot - 1);
quick(array, pivot + 1, end);
}
实现过程：
思路：将最左边的数作为基准数；通过双指针从两端向中间移动，通过内层循环，直到 right 寻找比 tmp 小的元素，left 寻找比 right 小的元素，将两下标元素进行交换，直到两指针相遇；将基准数与两指针相遇的位置进行交换，划分左右区间；
// Hoare 版分割
public static int partitionHoare(int[] array, int left, int right) {
int tmp = array[left];
int tmpleft = left;
// 直到两指针相遇结束循环
while (left < right) {
// right 寻找比 tmp 小的元素
// 所以只要大于等于 tmp，那么 right 向左移动
while (left < right && array[right] >= tmp) {
right--;
}
// left 寻找比 tmp 大的元素
// 所以只要小于等于 tmp，那么 left 向右移动
while (left < right && array[left] <= tmp) {
left++;
}
// 将左右指针的元素进行交换
swap(array, left, right);
}
// 将基准数与指针相遇的地方交换，划分左右区间
swap(array, left, tmpleft);
return left;
}
可能有的疑惑：
可不可以后面往前面向后面找，为什么是从后面开始往前面找？
答案是不可以的。
如上图所示，从前往后找可能会使 left 比 right 更先找到比基准值大的值，然后将他们进行交换，导致左边区间可能出现比基准值大的元素。
如果要排序的数组是 [6,1,4,2],left 下标只要没有比 tmp 下标的元素来的大，那么就要一直向右移动，甚至移到 right 的右边。right 也同理。
如果数组中有相同的元素，而内层循环条件是 array[left]<tmp，array[right]>tmp，那么将会造成死循环。
实现过程：
思路：
最左边的树作为基准数；通过双指针从两端向中间移动，通过内层循环，直到 right 寻找比 tmp 大的元素，将 right 的元素给 left，left 寻找比 right 小的元素，将 left 的元素给 right，直到两指针相遇；将基准数给两指针相遇的位置，划分左右区间；
代码：
public static int partition(int[] array, int left, int right) {
int tmp = array[left];
while (left < right) {
// 右指针寻找比 tmp 小的值给左指针
while (left < right && array[right] >= tmp) {
right--;
}
// 将 right 下标元素给 left 下标元素
array[left] = array[right];
// 左指针寻找比 tmp 大的值给右指针
while (left < right && array[left] <= tmp) {
left++;
}
// 将 left 下标元素给 right 下标元素
array[right] = array[left];
}
// 将基准数给 left 或者 right 下标
array[left] = tmp;
return left;
}
实现过程：
思路：
初始化 prev 指向首位置，cur 指向 prev 的下一个位置；如果 cur 的元素小于基准值，并且 prev 向后移动一位与 cur 不等，那么将 cur 与 prev 中的元素进行交换；cur 遍历完后，交换基准值与 left 的元素，划分区间。
public static int partition2(int[] array, int left, int right) {
int prev = left;
int cur = left + 1;
while (cur <= right) {
if (array[cur] < array[left] && array[++prev] != array[cur]) {
swap(array, cur, prev);
}
cur++;
}
swap(array, prev, left);
return prev;
}
public static void quick(int[] array, int start, int end) {
// 递归结束条件
if (start >= end) {
return;
}
// 找到中间元素下标
int midIndex = getMid(array, start, end);
// 将中间元素与首元素进行比较
swap(array, midIndex, start);
// 划分区间
int pivot = partition2(array, start, end);
quick(array, start, pivot - 1);
quick(array, pivot + 1, end);
}
private static int getMid(int[] array, int left, int right) {
int mid = (left + right) / 2;
// 如果 left 下标小于 right 下标元素
if (array[left] < array[right]) {
// 比较 left 与 mid
if (array[left] > array[mid]) {
return left;
} else if (array[right] < array[mid]) {
// 比较 right 与 mid
return right;
} else {
return mid;
}
// 如果 left 下标大于 right 下标元素
} else {
// 比较 left 与 mid
if (array[left] < array[mid]) {
return left;
} else if (array[right] > array[mid]) {
// 比较 right 与 mid
return right;
} else {
return mid;
}
}
}
public static void quick(int[] array, int start, int end) {
// 递归结束条件
if (start >= end) {
return;
}
if (end - start + 1 <= 7) {
insertSortRange(array, start, end);
}
int midIndex = getMid(array, start, end);
swap(array, midIndex, start);
// 划分区间
int pivot = partition2(array, start, end);
quick(array, start, pivot - 1);
quick(array, pivot + 1, end);
}
private static void insertSortRange(int[] array, int start, int end) {
// 这里 end 取闭区间
for (int i = start + 1; i <= end; i++) {
// 将下标 i 中的元素给 tmp；
int tmp = array[i];
int j = i - 1;
for (; j >= start; j--) {
// 将 j 中的元素与 tmp 中的元素进行比较
// 如果 j 中的元素大于 tmp 中的元素，那么将 j 中的元素放到 j+1 的元素中
if (tmp < array[j]) {
array[j + 1] = array[j];
} else {
// 否则说明 j+1 是适合 tmp 元素的位置，将其插入
array[j + 1] = tmp;
break;
}
}
array[j + 1] = tmp;
}
}
实现过程：
思路：
先对整体数组做一次划分；将基准元素两边的左右边界进行入栈；先弹出右边界，再弹出左边界，在左右边界区间中再进行划分，循环此操作直到栈为空为止。
代码：
public static void quickSort(int[] array) {
// 快速排序入口
quickNor(array, 0, array.length - 1);
// quick(array,0,array.length-1);
}
public static void quickNor(int[] array, int left, int right) {
Deque<Integer> stack = new ArrayDeque<>();
// 划分区域
int pivot = partition(array, left, right);
// 将两边的左右区间放入栈中
if (pivot - 1 > left) {
stack.push(left);
stack.push(pivot - 1);
}
if (pivot + 1 < right) {
stack.push(pivot + 1);
stack.push(right);
}
// 只要栈不为空，就代表还不是整体有序
while (!stack.isEmpty()) {
// 弹出右边界，再弹出左边界
right = stack.pop();
left = stack.pop();
// 将左右边界区间在进行分割
pivot = partition(array, left, right);
// 如果满足条件，在进行入栈
if (pivot - 1 > left) {
stack.push(left);
stack.push(pivot - 1);
}
if (pivot + 1 < right) {
stack.push(pivot + 1);
stack.push(right);
}
}
}
// 挖坑法
public static int partition(int[] array, int left, int right) {
int tmp = array[left];
while (left < right) {
// 右指针寻找比 tmp 小的值给左指针
while (left < right && array[right] >= tmp) {
right--;
}
// 将 right 下标元素给 left 下标元素
array[left] = array[right];
// 左指针寻找比 tmp 大的值给右指针
while (left < right && array[left] <= tmp) {
left++;
}
// 将 left 下标元素给 right 下标元素
array[right] = array[left];
}
// 将基准数给 left 或者 right 下标
array[left] = tmp;
return left;
}
快速排序总结
基本思想：
归并排序是一种高效的基于分治策略的排序算法。
分治策略：将一个数组分成两个子数组，然后递归的对这两个子数组进行排序，最后将排好序的子树组合并成一个完整的排序数组。
实现过程：
思路：
分解：如果子数组只有一个元素返回，也就是当 left>=right 的时候，停止分解；否则对数组进行左右递归分解；
合并：创建临时数组 tmp；用两个指针来比较两个元素大小，将小的放入 tmp；将剩余的元素放入 tmp 中；将数组放入原数组对应的位置。
代码：
public static void mergeSort(int[] array) {
mergeSortTmp(array, 0, array.length - 1);
}
// 分解
public static void mergeSortTmp(int[] array, int left, int right) {
if (left >= right) {
return;
}
// 分解：
int mid = (left + right) / 2;
mergeSortTmp(array, left, mid);
mergeSortTmp(array, mid + 1, right);
// 合并
merge(array, left, mid, right);
}
// 合并
public static void merge(int[] array, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int k = 0;
int s1 = left;
int s2 = mid + 1;
while (s1 <= mid && s2 <= right) {
if (array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
} else {
tmp[k++] = array[s2++];
}
}
// 放入剩余的元素
while (s1 <= mid) {
tmp[k++] = array[s1++];
}
while (s2 <= right) {
tmp[k++] = array[s2++];
}
// 保证数组有序
for (int i = 0; i < k; i++) {
array[i + left] = tmp[i];
}
}
| 排序 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(1) | 不稳定 |
| 快速排序 | O(n*log(n)) | O(n*log(n)) | O(n^2) | O(log(n))~O(n) | 不稳定 |
| 归并排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(n) | 稳定 |
