Java实现数组排序

介绍

排序是程序设计中常用的算法之一。在现实生活中，很多问题都需要对数据进行排序，比如搜索引擎对搜索结果按相关性排序、股票交易中根据股票价格排序等。在 Java 中，对数组进行排序也是常见的操作，通常使用 Arrays 类中的 sort() 方法实现。本文将从多个方面介绍 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 - 1 - i; j++) {
            // 如果前一个元素比后一个元素大，则交换两个元素的位置
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

选择排序

选择排序的工作原理是搜索数组中最小值（或最大值），并将其放置在第一个位置；接着，在剩余的数组中搜索第二小值（或第二大值），并将其放置在第二个位置；以此类推，直到整个数组排序完成。选择排序的实现也很简单，可以使用双重循环进行：

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            // 找到最小元素的下标
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // 将最小元素与第 i 个元素交换位置
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}

插入排序

插入排序的工作原理是将未排序的元素插入到已排序好的子序列中，初始状态下已排序的子序列只包含第一个元素。在遍历数组过程中，将当前元素与已排序的子序列中的元素比较，找到该元素对应的位置并插入。插入排序同样可以使用双重循环进行：

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;
        // 将比 key 大的元素向右移动一位，空出 key 的位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 将 key 插入到正确的位置
        arr[j + 1] = key;
    }
}

快速排序

快速排序是一种比较高效的排序算法，其基本思路是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字值均比另一部分记录的关键字值小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。在实现快速排序时，通常使用递归方式进行：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivotIdx = partition(arr, left, right);
        quickSort(arr, left, pivotIdx - 1);
        quickSort(arr, pivotIdx + 1, right);
    }
}
private static int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i++;
        }
    }
    int temp = arr[right];
    arr[right] = arr[i];
    arr[i] = temp;
    return i;
}

Arrays.sort() 方法

Java 提供了 Arrays 类，该类提供了许多操作数组的方法。其中的 sort() 方法可以对数组进行排序，sort() 方法使用快速排序算法实现。该方法的基本使用方式如下：

int[] arr = {4, 2, 9, 7};
Arrays.sort(arr);

如果要对数组按从大到小排序，可以使用 sort() 方法的重载版本，并传入自定义的 Comparator 对象：

int[] arr = {4, 2, 9, 7};
Arrays.sort(arr, (a, b) -> b - a);

总结

本文介绍了 Java 中常见的数组排序算法，包括冒泡排序、选择排序、插入排序和快速排序，并提供了每个算法的实现代码。此外，也介绍了使用 Arrays 类的 sort() 方法对数组进行排序的方式。掌握了这些知识，读者可以在实际项目中根据不同情况选择合适的排序算法。