以下是Java中几种常见排序算法的实现，包括冒泡排序、选择排序、插入排序、快速排序和归并排序。
各排序算法特点说明：
冒泡排序：
- 原理：重复比较相邻元素，将大的元素逐步"冒泡"到数组末尾
- 特点：稳定排序，适合小规模数据，可优化（加入交换标记提前退出）
- 空间复杂度：O(1)（原地排序）
选择排序：
- 原理：每次从剩余元素中找到最小元素，放到已排序区间末尾
- 特点：不稳定（可能改变相等元素的相对顺序），交换次数少
- 空间复杂度：O(1)（原地排序）
插入排序：
- 原理：将元素逐个插入到前面已排序的区间中合适的位置
- 特点：稳定排序，对近乎有序的数据效率很高（接近O(n)）
- 空间复杂度：O(1)（原地排序）
快速排序：
- 原理：通过分区操作将数组分为两部分，递归排序子数组
- 特点：实际应用中最快的排序算法之一，不稳定，最坏情况性能差
- 空间复杂度：O(log n)（递归栈空间）
归并排序：
- 原理：将数组分成两半分别排序，再合并两个有序子数组
- 特点：稳定排序，性能稳定（始终O(n log n)），需要额外空间
- 空间复杂度：O(n)（需要临时数组）
import java.util.Arrays;
public class SortingAlgorithms {
// 1. 冒泡排序（稳定，O(n²)）
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 外层循环控制需要进行多少轮比较
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
// 内层循环每轮将最大元素"冒泡"到末尾
for (int j = 0; j < n - 1 - i; 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;
}
}
// 2. 选择排序（不稳定，O(n²)）
public static void selectionSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 外层循环控制未排序区间的起点
for (int i = 0; i < n - 1; i++) {
// 找到未排序区间中最小元素的索引
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 将最小元素与未排序区间的第一个元素交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
// 3. 插入排序（稳定，O(n²)，适合近乎有序的数据）
public static void insertionSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 从第二个元素开始，将其插入到前面的有序区间
for (int i = 1; i < n; i++) {
int key = arr[i]; // 当前要插入的元素
int j = i - 1;
// 移动有序区间中大于key的元素
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// 将key插入到正确位置
arr[j + 1] = key;
}
}
// 4. 快速排序（不稳定，平均O(n log n)，最坏O(n²)）
public static void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int left, int right) {
if (left < right) {
// 分区操作，返回基准元素的正确位置
int pivotIndex = partition(arr, left, right);
// 递归排序基准元素左右两侧的子数组
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right]; // 以最右侧元素作为基准
int i = left - 1; // i指向小于基准的元素的最后位置
// 遍历数组，将小于基准的元素放到左侧
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
// 交换元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准元素放到正确位置
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
return i + 1; // 返回基准元素的索引
}
// 5. 归并排序（稳定，O(n log n)，需要额外空间）
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
}
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = left + (right - left) / 2; // 避免溢出
// 递归排序左右两半
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
// 合并两个有序子数组
merge(arr, left, mid, right, temp);
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 左子数组的起始索引
int j = mid + 1; // 右子数组的起始索引
int k = left; // 临时数组的起始索引
// 合并两个子数组到临时数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 复制左子数组剩余元素
while (i <= mid) {
temp[k++] = arr[i++];
}
// 复制右子数组剩余元素
while (j <= right) {
temp[k++] = arr[j++];
}
// 将临时数组中的元素复制回原数组
for (k = left; k <= right; k++) {
arr[k] = temp[k];
}
}
// 测试
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
int[] copy;
copy = Arrays.copyOf(arr, arr.length);
bubbleSort(copy);
System.out.println("冒泡排序: " + Arrays.toString(copy));
copy = Arrays.copyOf(arr, arr.length);
selectionSort(copy);
System.out.println("选择排序: " + Arrays.toString(copy));
copy = Arrays.copyOf(arr, arr.length);
insertionSort(copy);
System.out.println("插入排序: " + Arrays.toString(copy));
copy = Arrays.copyOf(arr, arr.length);
quickSort(copy);
System.out.println("快速排序: " + Arrays.toString(copy));
copy = Arrays.copyOf(arr, arr.length);
mergeSort(copy);
System.out.println("归并排序: " + Arrays.toString(copy));
}
}