Java 中十大经典排序算法全面总结与优化
·
Java 中十大经典排序算法全面总结与优化
在 Java 编程的世界里，排序算法是数据处理中不可或缺的工具。掌握常见的排序算法，能让开发者更高效地处理各种数据场景。本文将深入总结 Java 中的十大经典排序算法，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序，并探讨它们的优化策略。
一、冒泡排序（Bubble Sort）
原理
比较相邻元素，若顺序不对则交换，每一轮将最大（或最小）元素 “浮” 到数组末尾。
代码实现
public class BubbleSort {
public static void main(String[] args) {
int[] array = {
64,
34,
25,
12,
22,
11,
90
};
bubbleSort(array);
for (int num: array) {
System.out.print(num + " ");
}
}
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
性能分析
- 时间复杂度：最好情况 O (n)，最坏和平均情况 O (n²)。
- 空间复杂度：O(1)。
优化策略
设置标志位，若某一轮没有交换，说明数组已有序，提前结束排序。
二、选择排序（Selection Sort）
原理
将数组分为已排序和未排序部分，每一轮从未排序部分选最小（或最大）元素，与未排序部分第一个元素交换。
代码实现
public class SelectionSort {
public static void main(String[] args) {
int[] array = {
64,
34,
25,
12,
22,
11,
90
};
selectionSort(array);
for (int num: array) {
System.out.print(num + " ");
}
}
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
}
性能分析
- 时间复杂度：始终为 O (n²)。
- 空间复杂度：O(1)。
优化策略
减少不必要交换，当找到的最小元素就是当前元素时，不进行交换。
三、插入排序（Insertion Sort）
原理
将数组分为已排序和未排序部分，从第二个元素起，将未排序元素插入已排序部分的合适位置。
代码实现
public class InsertionSort {
public static void main(String[] args) {
int[] array = {
64,
34,
25,
12,
22,
11,
90
};
insertionSort(array);
for (int num: array) {
System.out.print(num + " ");
}
}
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
}
性能分析
- 时间复杂度：最好情况 O (n)，最坏和平均情况 O (n²)。
- 空间复杂度：O(1)。
优化策略
使用二分查找在已排序部分查找插入位置，减少比较次数。
四、希尔排序（Shell Sort）
原理
将原始数据分成多个子序列，对每个子序列进行插入排序，随着排序进行，步长逐渐减小，最终进行一次普通插入排序。
代码实现
public class ShellSort {
public static void main(String[] args) {
int[] array = {
64,
34,
25,
12,
22,
11,
90
};
shellSort(array);
for (int num: array) {
System.out.print(num + " ");
}
}
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
}
性能分析
- 时间复杂度：依赖步长序列，常见为 O (n log² n) 到 O (n²)。
- 空间复杂度：O(1)。
优化策略
选择更优步长序列，如 Hibbard 序列，可使时间复杂度接近 O (n log n)。
五、归并排序（Merge Sort）
原理
基于分治思想，将数组不断分成两个子数组，对每个子数组排序后再合并。
代码实现
public class MergeSort {
public static void main(String[] args) {
int[] array = {
64,
34,
25,
12,
22,
11,
90
};
mergeSort(array);
for (int num: array) {
System.out.print(num + " ");
}
}
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int[] temp = new int[arr.length];
mergeSortHelper(arr, temp, 0, arr.length - 1);
}
private static void mergeSortHelper(int[] arr, int[] temp, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSortHelper(arr, temp, left, mid);
mergeSortHelper(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
}
private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k] = arr[i];
i++;
} else {
temp[k] = arr[j];
j++;
}
k++;
}
while (i <= mid) {
temp[k] = arr[i];
i++;
k++;
}
while (j <= right) {
temp[k] = arr[j];
j++;
k++;
}
for (i = left; i <= right; i++) {
arr[i] = temp[i];
}
}
}
性能分析
- 时间复杂度：始终为 O (n log n)。
- 空间复杂度：O(n)。
优化策略
减少临时数组创建次数，在最外层创建一次并传递给递归函数；对小规模数组使用插入排序。
六、快速排序（Quick Sort）
原理
选择基准元素，将数组分为两部分，使左边元素小于等于基准，右边元素大于等于基准，递归对两部分排序。
代码实现
public class QuickSort {
public static void main(String[] args) {
int[] array = {
64,
34,
25,
12,
22,
11,
90
};
quickSort(array, 0, array.length - 1);
for (int num: array) {
System.out.print(num + " ");
}
}
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;
}
}
性能分析
- 时间复杂度：平均 O (n log n)，最坏 O (n²)。
- 空间复杂度：平均 O (log n)，最坏 O (n)。
优化策略
随机选择基准元素；三数取中选择基准元素；对小规模数组使用插入排序。
七、堆排序（Heap Sort）
原理
利用堆（最大堆或最小堆）的数据结构，先构建堆，然后将堆顶元素与堆末尾元素交换，再调整堆。
代码实现
public class HeapSort {
public static void main(String[] args) {
int[] array = {
64,
34,
25,
12,
22,
11,
90
};
heapSort(array);
for (int num: array) {
System.out.print(num + " ");
}
}
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, i, 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);
}
}
}
性能分析
- 时间复杂度：构建堆 O (n)，排序 O (n log n)，总体 O (n log n)。
- 空间复杂度：O(1)。
优化策略
减少比较次数，预先计算好比较范围，减少越界检查；使用索引堆，减少对象交换开销。
八、计数排序（Counting Sort）
原理
统计每个元素在数组中出现的次数，根据统计信息重建有序数组。
代码实现
public class CountingSort {
public static void main(String[] args) {
int[] array = {
64,
34,
25,
12,
22,
11,
90
};
int[] sortedArray = countingSort(array);
for (int num: sortedArray) {
System.out.print(num + " ");
}
}
public static int[] countingSort(int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
int min = arr[0];
int max = arr[0];
for (int num: arr) {
if (num < min) {
min = num;
}
if (num > max) {
max = num;
}
}
int[] countArray = new int[max - min + 1];
for (int num: arr) {
countArray[num - min]++;
}
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
int[] sortedArray = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
sortedArray[countArray[arr[i] - min] - 1] = arr[i];
countArray[arr[i] - min]--;
}
return sortedArray;
}
}
性能分析
- 时间复杂度：O (n + k)，n 为数组长度，k 为数据范围。
- 空间复杂度：O(n + k)。
优化策略
减少计数数组空间，根据数据范围调整计数数组；处理负数，通过偏移量将负数转换为非负数。
九、桶排序（Bucket Sort）
原理
将数据分到有限数量的桶中，对每个桶内数据排序，再按顺序合并桶中数据。
代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class BucketSort {
public static void main(String[] args) {
double[] array = {
0.897,
0.565,
0.656,
0.1234,
0.665,
0.3434
};
double[] sortedArray = bucketSort(array);
for (double num: sortedArray) {
System.out.print(num + " ");
}
}
public static double[] bucketSort(double[] arr) {
int n = arr.length;
List < List < Double >> buckets = new ArrayList < > (n);
for (int i = 0; i < n; i++) {
buckets.add(new ArrayList < > ());
}
for (double num: arr) {
int bucketIndex = (int)(num * n);
buckets.get(bucketIndex).add(num);
}
for (List < Double > bucket: buckets) {
Collections.sort(bucket);
}
int index = 0;
for (List < Double > bucket: buckets) {
for (double num: bucket) {
arr[index++] = num;
}
}
return arr;
}
}
性能分析
- 时间复杂度：理想 O (n)，最坏 O (n²)。
- 空间复杂度：O (n + k)，k 为每个桶内最大数据量。
优化策略
动态调整桶的数量；选择合适的桶内排序算法；减少数据分配时的计算量。
十、基数排序（Radix Sort）
原理
按数据的每一位数字进行排序，从最低位到最高位依次处理。
代码实现
性能分析
- 时间复杂度：假设数据的最大位数为 d ，数组长度为 n，基数为 r（对于十进制 r = 10），则每一轮的时间复杂度为 O (n + r)，总共需要 d 轮，所以基数排序的时间复杂度为 O (d * (n + r))。当 d 和 r 相对 n 较小时，基数排序接近线性时间复杂度。
- 空间复杂度：在每一轮排序中，需要额外的空间来存储计数数组和输出数组，计数数组大小为 r，输出数组大小为 n，所以空间复杂度为 O (n + r)。
优化策略
- 减少不必要的计算：在确定最大数和计算每一位数字时，可以采用更高效的算法。比如确定最大数时，利用分治法，将数组分成多个子数组，分别计算子数组的最大数，最后合并得到整个数组的最大数，以此减少比较次数。
- 并行处理：针对大规模数据，可利用多线程或并行计算加速基数排序。每一轮的分配和收集操作能够并行开展，从而提高排序效率。但在实现并行处理时，必须考虑线程安全和数据同步等问题。
- 自适应基数选择：依据数据的特点，动态调整基数的大小。若数据集中在较小的范围内，可选择较小的基数，减少桶的数量和计算量；要是数据范围较大，则可适当增大基数，提升排序效率。
综合对比与总结
这十大经典排序算法各有优劣 ，在实际应用中，需要根据数据规模、数据分布、数据类型以及稳定性要求等因素来选择合适的排序算法。
- 小规模数据：插入排序、冒泡排序和选择排序简单直观，对于小规模数据可以使用。其中插入排序在部分有序的数据上表现较好；冒泡排序代码简单，但效率相对较低；选择排序的比较次数固定，不受数据初始状态影响。
- 大规模数据：
-
- 基于比较的排序：快速排序、归并排序和堆排序的平均时间复杂度为 O (n log n) ，适用于大规模数据排序。快速排序平均性能最优，但最坏情况下性能较差；归并排序性能稳定，且是稳定排序算法；堆排序是原地排序，空间复杂度低。
-
- 非比较排序：计数排序、桶排序和基数排序适用于特定的数据类型和分布。计数排序适用于数据范围较小的整数排序；桶排序假设数据服从均匀分布，对浮点数等数据有较好的效果；基数排序适用于整数类型，且数据位数相对固定或者数据范围不是特别大的情况。
深入理解这些排序算法的原理、性能以及优化策略，能够帮助开发者在 Java 编程中更高效地处理各种排序任务，提升程序的整体性能。
public class RadixSort {
public static void main(String[] args) {
int[] array = {
170,
45,
75,
90,
802,
24,
2,
66
};
radixSort(array);
for (int num: array) {
System.out.print(num + " ");
}
}
public static void radixSort(int[] arr) {
int max = getMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
private static int getMax(int[] arr) {
int max = arr[0];
for (
int num: arr) {
if (num > max) {
max = num;
}
}
return max;
}
private static void countingSort(int[] arr, int exp) {
int[] output = new int[arr.length];
int[] count = new int[10];
for (int num: arr) {
int digit = (num / exp) % 10;
count[digit]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
int digit = (num / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
for (int i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
}
}
更多推荐
24
0- 0
已为社区贡献1条内容
所有评论(0)