排序算法
冒泡排序
算法介绍
冒泡排序（Bubble Sort），它重复地遍历要排序的列表，比较相邻的元素并根据需要交换它们的位置。这个过程会将每次遍历中最大（或最小）的未排序元素“冒泡”到列表的末尾。遍历列表的工作重复进行直到没有需要交换的元素为止，这意味着列表已经排序完成。
算法逻辑
- 从数组的第一个元素开始，依次比较相邻的两个元素。
- 如果前一个元素大于后一个元素，则交换它们的位置（升序排序时）。
- 每次遍历会将当前未排序部分中最大的元素“冒泡”到正确的位置（即末尾）。
- 重复上述过程，直到整个数组有序。
文字示例（升序）
原始数组：[5, 3, 8, 4, 2]
- 第一轮遍历：
- 比较 5 和 3 → 交换 → [3, 5, 8, 4, 2]
- 比较 5 和 8 → 不交换
- 比较 8 和 4 → 交换 → [3, 5, 4, 8, 2]
- 比较 8 和 2 → 交换 → [3, 5, 4, 2, 8]（最大值已到位）
- 第二轮遍历（忽略最后一位8）：
- 比较 3 和 5 → 不交换
- 比较 5 和 4 → 交换 → [3, 4, 5, 2, 8]
- 比较 5 和 2 → 交换 → [3, 4, 2, 5, 8]（次大值到位）
- 继续进行下去，直到全部有序。
代码示例
import java.util.Scanner;
public class BubbleSortDemo {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入数组长度：");
int arrLength = scanner.nextInt();
int[] arr = new int[arrLength];
for(int i = 0; i < arrLength; i++) {
int temp = i + 1;
System.out.println("请输入第" + temp + "个元素值：");
arr[i] = scanner.nextInt();
}
bubbleSort(arr);
System.out.println("排序后的数组为：");
for (int i = 0; i < arrLength; i++) {
System.out.print(arr[i] + " ");
}
}
public static void bubbleSort(int[] arr) {
boolean swap;
for (int i = 0; i < arr.length - 1; i++) {
swap = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swap = true;
}
}
if(!swap) {
break;
}
}
}
}选择排序
插入排序
快速排序
算法介绍
快速排序（Quick Sort）是一种基于分治策略的高效排序算法。它的核心思想是：通过一趟排序将待排序列分割成独立的两部分，其中一部分的所有元素均比基准值小，另一部分均比基准值大，然后递归地对这两部分继续进行排序，最终使整个序列有序。快速排序的平均时间复杂度为 O(n log n)，在大多数情况下表现优异。
算法逻辑
从数组中选取一个基准元素（通常选择最后一个元素）。
重新排列数组，使得所有小于基准的元素位于基准左侧，所有大于基准的元素位于基准右侧（分区操作）。此时基准元素处于其最终正确位置。
递归地对基准左侧和右侧的子数组重复上述步骤，直到子数组的长度为 0 或 1（自然有序）。
文字示例（升序）
原始数组：[8, 4, 7, 2, 5, 1, 3, 6]
选择最后一个元素 6 作为基准。
第一次分区：
初始化 i = -1（指向小于基准区域的最后一个位置）。
依次遍历 j = 0 到 j = 6：
j=0，8 > 6，不交换。
j=1，4 ≤ 6，i 变为 0，交换 arr[0] 和 arr[1] → [4, 8, 7, 2, 5, 1, 3, 6]。
j=2，7 > 6，不交换。
j=3，2 ≤ 6，i 变为 1，交换 arr[1] 和 arr[3] → [4, 2, 7, 8, 5, 1, 3, 6]。
j=4，5 ≤ 6，i 变为 2，交换 arr[2] 和 arr[4] → [4, 2, 5, 8, 7, 1, 3, 6]。
j=5，1 ≤ 6，i 变为 3，交换 arr[3] 和 arr[5] → [4, 2, 5, 1, 7, 8, 3, 6]。
j=6，3 ≤ 6，i 变为 4，交换 arr[4] 和 arr[6] → [4, 2, 5, 1, 3, 8, 7, 6]。
最后将基准 6 与 arr[i+1]（即 arr[5]）交换 → [4, 2, 5, 1, 3, 6, 7, 8]。
此时基准 6 已归位，索引为 5，左子数组为 [4, 2, 5, 1, 3]（均小于 6），右子数组为 [7, 8]（均大于 6）。
处理左子数组 [4, 2, 5, 1, 3]（基准为最后一个元素 3）：
初始化 i = -1，遍历 j = 0 到 j = 3：
j=0，4 > 3，不交换。
j=1，2 ≤ 3，i 变为 0，交换 arr[0] 和 arr[1] → [2, 4, 5, 1, 3]。
j=2，5 > 3，不交换。
j=3，1 ≤ 3，i 变为 1，交换 arr[1] 和 arr[3] → [2, 1, 5, 4, 3]。
将基准 3 与 arr[i+1]（arr[2]）交换 → [2, 1, 3, 4, 5]。
基准 3 归位，索引 2，左子数组 [2, 1]，右子数组 [4, 5]。
处理左子数组 [2, 1]（基准为最后一个元素 1）：
初始化 i = -1，遍历 j = 0：
- j=0，2 > 1，不交换。
将基准 1 与 arr[i+1]（arr[0]）交换 → [1, 2]。
基准 1 归位，索引 0，左子数组为空，右子数组 [2]（自然有序）。
处理右子数组 [4, 5]（基准为最后一个元素 5）：
初始化 i = -1，遍历 j = 0：
- j=0，4 ≤ 5，i 变为 0，交换 arr[0] 与自身（不变）→ [4, 5]。
将基准 5 与 arr[i+1]（arr[1]）交换，数组仍为 [4, 5]。
基准 5 归位，索引 1，左子数组 [4]，右子数组为空。
处理右子数组 [7, 8]（基准为最后一个元素 8）：
初始化 i = -1，遍历 j = 0：
- j=0，7 ≤ 8，i 变为 0，交换 arr[0] 与自身（不变）→ [7, 8]。
将基准 8 与 arr[i+1]（arr[1]）交换，数组仍为 [7, 8]。
基准 8 归位，索引 1，左子数组 [7]，右子数组为空。
最终合并结果：所有子数组已有序，组合得到完整有序数组 [1, 2, 3, 4, 5, 6, 7, 8]。
代码示例
/**
* 快速排序
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后：" + java.util.Arrays.toString(arr));
}
/**
* 交换索引下标为 i 和 索引下标为 j 的数组的值
* @param array 数组值
* @param i 索引 i
* @param j 索引 j
*/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* 分区
* @param array 数组
* @param low 开始索引下标
* @param high 结束索引下标
* @return 基准索引下标
*/
public static int partition(int[] array, int low, int high) {
// 选择最后一个元素作为基准
int pivot = array[high];
// i 指向小于基准的区域的最后一个位置，初始为 low - 1
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
swap(array, ++i, j);
}
}
swap(array, ++i, high);
// 返回基准的最终索引
return i;
}
// 快速排序入口
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int pivotIndex = partition(array, low, high);
quickSort(array, low, pivotIndex - 1);
quickSort(array, pivotIndex + 1, high);
}
}
}