目录
作为一名 Java 初学者，掌握排序算法是编程路上的重要一步。排序算法不仅能帮助我们更好地理解数据处理逻辑，还能在实际开发中解决各种问题。
一、冒泡排序（Bubble Sort）
泡排序是最基础的排序算法之一，它的核心思想是通过重复遍历要排序的数组，每次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。
原理
就像水中的气泡会逐渐上浮一样，越大的元素会经由交换慢慢 “浮” 到数组的末端。具体来说，每一轮遍历都会将当前未排序部分中最大的元素移动到正确的位置。
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// 每轮结束后，最大的元素已到位，下一轮可以少比较一次
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;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}排序后的数组：
11 12 22 25 34 64 90
优缺点：
- 优点：实现简单，易于理解，是入门排序算法的好选择。
- 缺点：效率较低，时间复杂度为 O (n²)，在处理大规模数据时性能不佳。
二、选择排序（Selection Sort）
选择排序的思路相对直观，它每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
原理
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
public class SelectionSort {
public static void selectionSort(int[] arr) {
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[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}排序后的数组：
11 12 22 25 64
优缺点：
- 优点：实现简单，相较于冒泡排序，交换次数更少。
- 缺点：时间复杂度仍为 O (n²)，不适合处理大量数据。
三、插入排序（Insertion Sort）
插入排序的工作方式类似于我们整理手中的扑克牌，它将数组分为已排序和未排序两部分，每次从为排序部分中取出一个元素，插入到已排序部分的正确位置。
原理
从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复上一步骤，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复以上步骤。
public class InsertionSort {
public static void insertionSort(int[] arr) {
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 = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
insertionSort(arr);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}排序后的数组：
5 6 11 12 13
优缺点：
- 优点：对于近乎有序的数组，插入排序的效率很高，时间复杂度可接近 O (n)；实现也较为简单。
- 缺点：在处理完全无序的大规模数据时，时间复杂度仍为 O (n²)。
四、快速排序（Quick Sort）
快速排序是一种高效的排序算法，它采用了分治法的思想，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
原理
选择一个元素作为 “基准”（pivot），通常选择数组的第一个元素、最后一个元素或中间元素。然后将所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准后面，这个过程称为分区（partition）操作。接着，对基准前后的两个子数组分别重复上述过程，直到子数组的长度为 1 或 0。
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 分区操作，得到基准元素的正确位置
int pi = partition(arr, low, high);
// 递归排序基准元素左边和右边的子数组
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
// 选择最右边的元素作为基准
int pivot = arr[high];
// i表示小于基准元素的区域的边界
int i = low - 1;
for (int j = low; j < high; 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[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}排序后的数组：
1 5 7 8 9 10
优缺点：
- 优点：平均时间复杂度为 O (n log n)，效率高，在实际应用中广泛使用。
- 缺点：在最坏情况下（如数组已经有序），时间复杂度会退化为 O (n²)；不稳定，可能会改变相等元素的相对顺序。
五、归并排序（Merge Sort）
归并排序同样基于分治法，它的核心是将两个或两个以上的有序表合并成一个新的有序表。
原理
将待排序数组不断二分，直到每个子数组只包含一个元素（此时子数组自然有序）。然后，将这些有序的子数组两两合并，每次合并都得到一个更大的有序数组，重复这个过程，直到最终得到一个完整的有序数组。
public class MergeSort {
// 合并两个有序子数组
public static void merge(int[] arr, int left, int mid, int right) {
// 计算两个子数组的长度
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
int[] L = new int[n1];
int[] R = new int[n2];
// 将数据复制到临时数组
for (int i = 0; i < n1; ++i) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[mid + 1 + j];
}
// 合并临时数组
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 归并排序主方法
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// 找到中间点
int mid = left + (right - left) / 2;
// 递归排序左右两部分
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并已排序的两部分
merge(arr, left, mid, right);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
int n = arr.length;
mergeSort(arr, 0, n - 1);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}排序后的数组：
5 6 7 11 12 13
优缺点
- 优点：时间复杂度稳定为 O (n log n)，不受输入数据的影响；是稳定的排序算法。
- 缺点：需要额外的存储空间，空间复杂度为 O (n)。
六、希尔排序（Shell Sort）
希尔排序是插入排序的一种改进版本，它通过将数组按照一定的间隔分组，对每组进行插入排序，然后逐渐缩小间隔，直到间隔为 1，此时进行最后一次插入排序，使数组完全有序。
原理
先确定一个增量序列，增量序列可以有多种选择，常见的有初始增量为数组长度的一半，之后每次减半，直到增量为 1。对于每个增量，将数组中所有距离为该增量的元素组成一个子数组，对每个子数组进行插入排序。随着增量逐渐减小，子数组的长度逐渐增大，当增量为 1 时，整个数组就是一个子数组，此时进行一次插入排序，数组就会变得有序。
public class ShellSort {
public static void shellSort(int[] arr) {
int n = arr.length;
// 初始增量为数组长度的一半，之后每次减半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个子数组进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
// 移动同组中比temp大的元素
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {12, 34, 54, 2, 3};
shellSort(arr);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}排序后的数组：
2 3 12 34 54
优缺点
- 优点：相较于插入排序，希尔排序在处理大规模数据时效率更高，平均时间复杂度优于 O (n²)，具体取决于增量序列的选择。
- 缺点：时间复杂度受增量序列影响较大，不同的增量序列可能会导致不同的性能；是不稳定的排序算法。
七、总结
以上六种排序算法各有特点，适用于不同的场景。
冒泡排序、选择排序和插入排序是基础的排序算法，实现简单但效率较低，适合处理小规模数据或作为学习排序算法的入门内容。
快速排序、归并排序和希尔排序是更高级的排序算法，它们在处理大规模数据时表现更出色。快速排序平均效率高，应用广泛；归并排序时间稳定且稳定，但需要额外空间；希尔排序是插入排序的改进，性能优于基础的插入排序。
同时，Java 类库中提供的 Arrays.sort () 方法内部采用了多种高效排序算法的组合，在大多数情况下能满足我们的需求，但了解各种排序算法的原理和实现，能帮助我们更好地理解和使用这些工具。