Java 中的排序算法详解

一、冒泡排序（Bubble Sort）

原理

二、选择排序（Selection Sort）

原理

三、插入排序（Insertion Sort）

原理

四、快速排序（Quick Sort）

原理

五、归并排序（Merge Sort）

原理

六、希尔排序（Shell Sort）

原理

七、总结

作为一名 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 + " ");}}
}