Java排序算法详解
在Java编程中，排序算法是数据处理和算法设计中的基础且重要的部分。它们广泛应用于各种场景，如数据库管理、数据分析、图形界面排序等。掌握几种常见的排序算法对于提升程序效率和优化性能至关重要。本文将详细解析几种经典的Java排序算法，包括冒泡排序、选择排序、插入排序、快速排序和归并排序，并探讨它们的原理、实现方式及适用场景。
冒泡排序（Bubble Sort）
冒泡排序是最简单的排序算法之一，通过重复遍历待排序的数列，比较每对相邻元素的值，若发现顺序错误则交换它们的位置。这个过程就像水中的气泡一样逐渐“浮”到数列的顶端（即排序的末端），因此得名冒泡排序。冒泡排序实现简单，但效率较低，特别是对于大数据集来说，其时间复杂度为O(n^2)，其中n是数列的长度。
public void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换arr[j]和arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}
选择排序（Selection Sort）
选择排序算法的基本思想是：在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的时间复杂度同样是O(n^2)，但在某些情况下（如数据交换次数较少时）可能比冒泡排序更优。
public 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;}}// 交换arr[i]和arr[minIndex]int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}
}
插入排序（Insertion Sort）
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在小数据集上表现优异，时间复杂度最好情况下为O(n)，平均和最坏情况下为O(n^2)。
public void insertionSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int key = arr[i];int j = i - 1;/* 将arr[i]插入到arr[0...i-1]中已排序的序列中 */while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}
}
快速排序（Quick Sort）
快速排序是一种分治策略的排序算法，它通过选择一个“基准”元素，将待排序的数组分割成两个子数组，一个包含所有小于基准值的元素，另一个包含所有大于基准值的元素，然后递归地对这两个子数组进行快速排序。快速排序的平均时间复杂度为O(n log n)，但在最坏情况下（如输入数组已经有序）会退化到O(n^2)。
public void quickSort(int[] arr, int low, int high) {if (low < high) {// pi是partition的位置，arr[pi]现在位于正确的位置int pi = partition(arr, low, high);// 分别对pi左右两边的子数组进行递归排序quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}// 分区操作，返回pivot元素的