深入了解Java中常考的排序算法：从冒泡到快排的全景解析

在学习Java编程的过程中，排序算法常常是面试官关注的一个重要话题。无论是初学者还是有经验的程序员，对排序算法的理解都可以展示出你的逻辑思维能力和编程技巧。今天，我想跟大家深入探讨一些在Java中常考的排序算法。

排序算法的种类

在众多排序算法中，最常见的几种算法包括：

• 冒泡排序（Bubble Sort）
• 选择排序（Selection Sort）
• 插入排序（Insertion Sort）
• 快速排序（Quick Sort）
• 归并排序（Merge Sort）
• 堆排序（Heap Sort）

1. 冒泡排序（Bubble Sort）

冒泡排序是最简单的排序算法之一，它的基本思路是重复地走访待排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。这样，每次遍历后，最大的元素就会“冒泡”到数列的末端。

虽然冒泡排序简单易懂，但由于其时间复杂度达到O(n²)，在排序大数据量时效率较低，实际应用中比较少用。但在面试中，了解这个算法的原理和实现仍然是有帮助的。

2. 选择排序（Selection Sort）

选择排序的核心思想是在未排序的部分中选择最小元素，将其与未排序部分的第一个元素进行交换。这一过程不断重复，直到所有元素都有序。

与冒泡排序相比，选择排序的最坏情况时间复杂度虽然也是O(n²)，但它的数据交换次数较少，效率略优。要实现选择排序可以参考以下示例代码：

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; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }

3. 插入排序（Insertion Sort）

插入排序通过将每个元素插入到它前面已排好序的子序列中，实现最终的排序。这种算法的时间复杂度为O(n²)，但由于其简单易实现且在某些情况下表现良好（如数据基本有序时），在面试中依然会被提及。

这里也给出一个插入排序的简单实现：

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; } }

4. 快速排序（Quick Sort）

快速排序是一种分而治之的算法，通过一个基准值将列表分割成两个子数组，其中一个子数组的所有元素都小于基准值，另一个则都大于基准值。然后递归地对两个子数组进行快速排序。

快速排序的时间复杂度为O(n log n)，在处理大量数据时非常高效。它的性能主要取决于基准值的选择。下面是一个快速排序的实现：

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]; 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; }

5. 归并排序（Merge Sort）

归并排序同样采用分治法，通过递归将数组分成两半，并对每一半进行排序。在两个已排序的数组合并成一个新的已排序数组时，算法可确保效率和稳定性。

归并排序的时间复杂度为O(n log n)，适合于大数据排序。以下是归并排序的简单代码示例：

public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } } private 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, 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++; } }

6. 堆排序（Heap Sort）

堆排序是一种基于堆数据结构的排序算法。它的基本思想是将待排序的数组构造成一个大顶堆，然后将堆顶元素（最大值）与堆的最后一个元素交换，逐步缩小堆的范围。这种算法的时间复杂度也为O(n log n)。

public static void heapSort(int[] arr) { int n = arr.length; for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } for (int i = n - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, n, 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) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } }