Java中的快速排序（QuickSort）、归并排序（Merge Sort）和堆排序（Heap Sort）是三种常用的排序算法，它们各有优缺点。以下是这些排序算法的简单介绍以及在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;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
归并排序
归并排序也是一种分治算法，它将数组分成两个相等（或几乎相等）的部分，分别对每个部分进行排序，然后合并已排序的两个部分。
public class MergeSort {
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[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
System.arraycopy(temp, 0, arr, left, temp.length);
}
}
堆排序
堆排序是一种通过构建大顶堆或小顶堆来实现的排序算法。它首先构造一个大顶堆（或小顶堆），然后不断交换堆顶元素与最后一个元素，并重新调整堆结构，直到整个数组有序。
public class HeapSort {
public 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) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
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--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
每种排序算法都有其独特的应用场景和性能特点。快速排序通常具有良好的平均性能，但最坏情况下会退化为O(n²)；归并排序始终具有稳定的O(n log n)时间复杂度，但需要额外的空间；堆排序的时间复杂度也是O(n log n)，并且原地排序不需要额外空间，但它不是稳定的排序算法。
