/**
-
常见排序算法汇总
*/
public class SortAlgorithms {/**
- 冒泡排序（Bubble Sort）
- 思想：相邻元素两两比较，大的往后沉。
- 时间复杂度：O(n^2)
- 稳定性：稳定
*/
public static void bubbleSort(int[] arr) {
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(arr, j, j + 1);
}
}
}
}
/**
- 选择排序（Selection Sort）
- 思想：每轮选择最小（或最大）的元素放到前面。
- 时间复杂度：O(n^2)
- 稳定性：不稳定
*/
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
// 找到未排序部分的最小值
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 将最小值放到当前轮的开头
swap(arr, i, minIndex);
}
}
/**
- 插入排序（Insertion Sort）
- 思想：将元素插入到前面已排序部分的正确位置。
- 时间复杂度：O(n^2)
- 稳定性：稳定
*/
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i]; // 当前要插入的元素
int j = i - 1;
// 从后往前比较，找到插入位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 向后移动
j--;
}
arr[j + 1] = key; // 插入
}
}
/**
- 希尔排序（Shell Sort）
- 思想：将序列分为若干子序列进行插入排序，逐步减小间隔。
- 时间复杂度：O(n log n)
- 稳定性：不稳定
*/
public static void shellSort(int[] arr) {
// gap为步长，每轮缩小一半
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
int temp = arr[i];
int j = i;
// 按gap间隔进行插入排序
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
/**
- 归并排序（Merge Sort）
- 思想：分治法，将数组分为两半，分别排序后再合并。
- 时间复杂度：O(n log n)
- 稳定性：稳定
*/
public static void mergeSort(int[] arr) {
mergeSortHelper(arr, 0, arr.length - 1);
}
private static void mergeSortHelper(int[] arr, int left, int right) {
if (left >= right) return; // 递归终止条件
int mid = (left + right) / 2;
mergeSortHelper(arr, left, mid); // 排序左半部分
mergeSortHelper(arr, mid + 1, right); // 排序右半部分
merge(arr, left, mid, right); // 合并
}// 合并两个有序子数组
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;// 合并过程：按顺序比较左右两边元素while (i <= mid && j <= right) {temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];}// 将剩余元素依次拷贝while (i <= mid) temp[k++] = arr[i++];while (j <= right) temp[k++] = arr[j++];// 拷贝回原数组for (int t = 0; t < temp.length; t++) {arr[left + t] = temp[t];}}
/**
- 快速排序（Quick Sort）
- 思想：分治法，选取一个“基准”，小的放左边，大的放右边。
- 时间复杂度：平均O(n log n)，最坏O(n^2)
- 稳定性：不稳定
*/
public static void quickSort(int[] arr) {
quickSortHelper(arr, 0, arr.length - 1);
}
private static void quickSortHelper(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = arr[left]; // 选取第一个元素为基准
int i = left, j = right;// 分区过程while (i < j) {while (i < j && arr[j] >= pivot) j--; // 从右往左找小于pivot的数while (i < j && arr[i] <= pivot) i++; // 从左往右找大于pivot的数if (i < j) swap(arr, i, j);}// 将基准放到正确位置swap(arr, left, i);// 递归左右子序列quickSortHelper(arr, left, i - 1);quickSortHelper(arr, i + 1, right);}
/**
-
堆排序（Heap Sort）
-
思想：利用堆结构（最大堆）来排序。
-
时间复杂度：O(n log n)
-
稳定性：不稳定
*/
public static void heapSort(int[] arr) {
int n = arr.length;// 1. 构建最大堆（从最后一个非叶子节点开始）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}// 2. 取出堆顶元素放到数组末尾
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // 交换堆顶与末尾元素
heapify(arr, i, 0); // 重新调整堆
}
}
// 调整堆，使其满足最大堆性质
private static void heapify(int[] arr, int n, int i) {
int largest = i; // 假设当前节点最大
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点// 找出最大值的节点if (left < n && arr[left] > arr[largest]) largest = left;if (right < n && arr[right] > arr[largest]) largest = right;// 如果最大值不是当前节点，则交换并递归调整if (largest != i) {swap(arr, i, largest);heapify(arr, n, largest);}}
/**
- 工具函数：交换数组中的两个元素
*/
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
-
🧪 测试主函数
*/
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2, 7, 1, 6};System.out.println("原始数组：");
printArray(arr);// 测试不同排序算法
quickSort(arr); // 可替换为 bubbleSort(arr)、mergeSort(arr) 等System.out.println("排序后：");
printArray(arr);
}
/**
- 辅助打印函数
*/
public static void printArray(int[] arr) {
for (int n : arr) {
System.out.print(n + " ");
}
System.out.println();
}
}