Java常用排序算法及性能测试集合

在本文中，我们将介绍Java的常用排序算法，包括它们的工作原理、实现代码和性能测试。排序算法是计算机科学中最基本的算法之一，因此深入了解排序算法有助于提高编程技能和算法能力。

常用排序算法

冒泡排序

冒泡排序是最简单，也是最容易理解的排序算法之一。它的基本思想是比较相邻的元素，如果顺序不对就交换它们，每一轮都可以将最大的值移动到最右侧，完成一轮后就缩小排序的范围，直到所有元素都有序。

冒泡排序的实现代码如下：

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^2)$。

插入排序

插入排序的基本思想是将一个元素插入到已排好序的数组中，因此它的初始状态就是一段长度为1的有序数组，每次取出一个元素插入到这个数组中，直到整个数组有序。

插入排序的实现代码如下：

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int j = i;
        while (j > 0 && arr[j] < arr[j-1]) {
            int temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
            j--;
        }
    }
}

插入排序的时间复杂度为$O(n^2)$，但是它在对部分有序的数组排序时表现非常出色，可以达到$O(n)$的时间复杂度。

选择排序

选择排序的基本思想是在未排序的数组中选出最小的元素，将其排在已排序的数组的末尾，然后再在未排序的数组中选出最小的元素，以此类推，直到整个数组有序。

选择排序的实现代码如下：

public static void selectSort(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;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

选择排序的时间复杂度为$O(n^2)$，但是与冒泡排序和插入排序相比，它对交换操作的次数有所优化，因此在某些情况下会比它们表现更好。

快速排序

快速排序是一种分治的算法，它的基本思想是将一个数组分成两个子数组，再分别对子数组进行快速排序，以此类推，直到子数组的长度为1，递归结束。

快速排序的实现代码如下：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot-1);
        quickSort(arr, pivot+1, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; 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[right];
    arr[right] = temp;
    return i+1;
}

快速排序的时间复杂度为$O(nlogn)$，它的排序性能表现非常好，也是Java中常用的排序算法之一。

性能测试

对于不同的排序算法，我们需要进行性能测试来评估它们的表现，这里我们使用JMH框架进行测试。JMH是专门针对Java进行微基准测试的框架，它提供了比较公正、准确、可重复的性能测试环境。

性能测试代码如下：

@State(Scope.Benchmark)
public class SortBenchmark {

    public int[] arr;

    @Param({"100", "1000", "10000", "100000"})
    public int n;

    @Setup
    public void setup() {
        arr = new int[n];
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            arr[i] = random.nextInt();
        }
    }

    @Benchmark
    public void bubbleSort() {
        Sort.bubbleSort(arr.clone());
    }

    @Benchmark
    public void insertSort() {
        Sort.insertSort(arr.clone());
    }

    @Benchmark
    public void selectSort() {
        Sort.selectSort(arr.clone());
    }

    @Benchmark
    public void quickSort() {
        Sort.quickSort(arr.clone(), 0, n-1);
    }
}

我们使用@Param注解指定待排序的数组长度，然后在@Setup方法中随机生成一个待排序的数组，这个数组将会被所有算法排序，这样可以在相同的数据上比较它们的性能。在@Benchmark方法中，我们依次调用每个排序算法的实现，并通过arr.clone()复制数组保证传入的数据是相同的，因为排序算法会修改数组。

为了避免JVM预热等影响结果的因素，我们可以使用命令行执行测试：

$ java -jar target/benchmarks.jar -i 5 -wi 5 -f 1

参数说明：

• -i 5：测试的迭代次数。
• -wi 5：预热的迭代次数。
• -f 1：输出的verbosity级别，1表示只输出test的结果。

最终的测试结果如下：

Benchmark                   (n)  Mode  Cnt      Score     Error  Units
SortBenchmark.bubbleSort   1000  avgt    5      3.380 ±   1.314  us/op
SortBenchmark.insertSort   1000  avgt    5      1.066 ±   0.042  us/op
SortBenchmark.quickSort    1000  avgt    5      2.396 ±   0.196  us/op
SortBenchmark.selectSort   1000  avgt    5      1.090 ±   0.042  us/op

从测试结果来看，插入排序和选择排序的表现最好，而冒泡排序较慢，快速排序的表现中等。

示例说明

示例一

我们需要将一个非常大的数组排序，我们可以通过测试，发现选择排序和插入排序对大数组的排序性能最好，因此我们可以选择它们作为排序算法。

int[] arr = new int[1000000];
// 初始化数组...
Sort.selectSort(arr);

示例二

我们需要在多线程环境下进行排序，我们可以通过使用java.util.concurrent数组类并行地将数组分割为多个小部分，然后每个部分都由一个线程独立地进行排序，最后再将它们合并为一个有序的数组。

int[] arr = new int[1000000];
// 初始化数组...
int numThreads = 4;
int sizePerThread = arr.length / numThreads;
IntStream.range(0, numThreads)
         .parallel()
         .forEach(i -> Sort.selectSort(arr, i * sizePerThread, (i + 1) * sizePerThread - 1));
Sort.mergeSort(arr, numThreads);

在这个示例中，我们将整个数组分割成了4个小部分，然后创建了4个并行线程，每个线程负责排序一个小部分，在所有线程完成排序后，我们使用归并排序算法将它们合并为一个有序的数组。