在Java编程中，排序算法是数据处理非常重要的一部分。快速排序、归并排序和计数排序是几种经典的排序算法，各有其独特的特性和适用场景。以下是这三种排序算法的详细解析及其代码示例。
1. 快速排序（Quick Sort）
快速排序是一种分治法策略的排序算法。它通过一个基准元素将数据分为左边比基准小、右边比基准大的两个部分，然后对这两个部分分别进行快速排序。
算法步骤： 1. 从数组中选择一个基准元素。 2. 将数组划分为两个子数组：一边是小于基准元素的，另一边是大于基准元素的。 3. 递归地排序两个子数组。
代码示例：
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 static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组：" + Arrays.toString(arr));
}
}
2. 归并排序（Merge Sort）
归并排序也是一种分治法的排序算法。它将数组分为两半，分别排序后再合并结果。归并排序在稳定性和效率上表现优秀，适合处理大规模数据。
算法步骤： 1. 将数组分为两部分。 2. 递归地对每个部分进行归并排序。 3. 合并两个已排序的部分。
代码示例：
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 n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
System.arraycopy(arr, left, leftArr, 0, n1);
System.arraycopy(arr, mid + 1, rightArr, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < n1) {
arr[k++] = leftArr[i++];
}
while (j < n2) {
arr[k++] = rightArr[j++];
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组：" + Arrays.toString(arr));
}
}
3. 计数排序（Counting Sort）
计数排序是一种非比较型排序算法。它的基本思想是统计数组中每个元素出现的次数，然后根据这些计数值来确定每个元素在结果数组中的位置。计数排序适用于范围有限且不涉及负数的整数排序。
算法步骤： 1. 找到数组中的最大值和最小值。 2. 创建一个计数数组来统计元素的出现次数。 3. 根据计数数组生成排序后的结果数组。
代码示例：
public class CountingSort {
public static void countingSort(int[] arr) {
int maxVal = Arrays.stream(arr).max().getAsInt();
int[] count = new int[maxVal + 1];
for (int num : arr) {
count[num]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i]-- > 0) {
arr[index++] = i;
}
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 2, 8, 3, 3, 1};
countingSort(arr);
System.out.println("排序后的数组：" + Arrays.toString(arr));
}
}
总结
在Java中，快速排序、归并排序和计数排序分别在时间复杂度、空间复杂度和稳定性等方面各有优势。快速排序一般情况下效率较高，但在最坏情况下时间复杂度为O(n^2)；归并排序在大多数情况下性能稳定，为O(n log n)，但需要额外的空间；计数排序对范围有限的数值数组非常高效，时间复杂度为O(n+k)，但只能处理非负整数。根据具体问题的要求选择合适的排序算法，可以让我们的程序更加高效。
