【唐叔学算法】第19天：交换排序-冒泡排序与快速排序的深度解析及Java实现

引言

排序算法是计算机科学中的基础问题，而交换排序作为其中一类经典的排序方法，因其简单直观的思想和易于实现的特点，在初学者中广受欢迎。交换排序的核心思想是通过不断交换相邻元素来达到排序的目的。本文将深入探讨两种典型的交换排序算法：冒泡排序和快速排序，分析它们的原理、实现细节、时间复杂度和空间复杂度，并通过Java代码进行具体实现。

冒泡排序：简单却经典的排序算法

算法原理

冒泡排序（Bubble Sort）是一种基础的交换排序算法，其核心思想是通过重复地遍历待排序的序列，依次比较相邻的两个元素，如果它们的顺序错误就交换它们的位置。这样，每一轮遍历都会将当前未排序部分的最大（或最小）元素“冒泡”到序列的末尾。

算法步骤

1. 从序列的起始位置开始，比较相邻的两个元素。
2. 如果前一个元素大于后一个元素，则交换它们的位置。
3. 对序列中的每一对相邻元素重复上述操作，直到序列末尾。
4. 重复以上步骤，直到没有需要交换的元素为止。

时间复杂度与空间复杂度

• 时间复杂度：
  • 最坏情况：O(n²)，当输入序列是逆序时，需要进行n(n-1)/2次比较和交换。
  • 最好情况：O(n)，当输入序列已经有序时，只需进行一次遍历即可。
  • 平均情况：O(n²)。
• 空间复杂度：O(1)，冒泡排序是原地排序算法，不需要额外的存储空间。

Java实现

public class BubbleSort {public static void bubbleSort(int[] arr) {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; // 如果没有交换，提前退出}}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);System.out.println("Sorted array: ");for (int i : arr) {System.out.print(i + " ");}}
}

快速排序：高效的分治排序算法

算法原理

快速排序（Quick Sort）是一种基于分治思想的交换排序算法。其核心思想是选择一个“基准元素”（pivot），将序列分为两部分：一部分比基准元素小，另一部分比基准元素大，然后递归地对这两部分进行排序。

算法步骤

1. 选择一个基准元素（通常选择第一个元素、最后一个元素或中间元素）。
2. 将序列分为两部分：小于基准元素的部分和大于基准元素的部分。
3. 对这两部分分别递归地进行快速排序。
4. 合并结果。

时间复杂度与空间复杂度

• 时间复杂度：
  • 最坏情况：O(n²)，当每次选择的基准元素都是序列的最大或最小值时，快速排序会退化为冒泡排序。
  • 最好情况：O(n log n)，当每次选择的基准元素都能将序列均匀地分为两部分时。
  • 平均情况：O(n log n)。
• 空间复杂度：O(log n)，快速排序的空间复杂度主要取决于递归调用的栈空间。

Java实现

public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high); // 获取基准元素的位置quickSort(arr, low, pivotIndex - 1); // 递归排序左子序列quickSort(arr, pivotIndex + 1, high); // 递归排序右子序列}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为基准int i = low - 1; // i指向小于基准的元素的位置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};quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: ");for (int i : arr) {System.out.print(i + " ");}}
}

对比与总结

冒泡排序 vs 快速排序

特性	冒泡排序	快速排序
时间复杂度	O(n²)	平均 O(n log n)，最坏 O(n²)
空间复杂度	O(1)	O(log n)
稳定性	稳定	不稳定
适用场景	小规模数据或基本有序数据	大规模数据或随机数据

选择与应用

• 冒泡排序：虽然时间复杂度较高，但实现简单，适合教学和小规模数据的排序。
• 快速排序：虽然实现稍复杂，但时间复杂度较低，适合处理大规模数据，是实际应用中最常用的排序算法之一。

通过本文的讲解和Java实现，希望读者能够深入理解冒泡排序和快速排序的原理和实现细节，并在实际编程中根据需求灵活选择合适的排序算法。