Java中的数组排序方式(快速排序、冒泡排序、选择排序)

下面是Java中的数组排序方式的完整攻略。

1. 快速排序

快速排序是常用的一种排序算法，其时间复杂度为O(nlogn)。其基本思想是选择一个基准数，将数组分成左右两部分，比基准数小的放在左边，比基准数大的放在右边，然后再对左右两部分分别递归地进行快速排序。

Java中快速排序的实现基于Arrays类的sort方法。下面是一个示例代码：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int partitionIndex = partition(arr, left, right); // 分割索引
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
}

public static int partition(int[] arr, int left, int right) {
    int pivot = left; // 设定基准值（pivot）
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

在以上示例代码中，quickSort方法递归调用了自身，算法的主要逻辑体现在partition方法中，该方法用于分割数组，找到基准数的正确位置，并将基准数与正确位置进行交换。swap方法用于交换数组中的两个元素。

下面是一个基于快速排序的示例代码：

public class QuickSortExample {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right); // 分割索引
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = left; // 设定基准值（pivot）
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

输出结果为：[1, 2, 3, 4, 5, 6, 7, 8]。

2. 冒泡排序

冒泡排序的基本思想是将相邻的两个元素进行比较，如果前者大于后者，则交换位置，直到序列中所有元素都满足顺序要求为止。时间复杂度为O(n^2)，因此在处理较长的序列时效率较低。

下面是一个示例代码：

public class BubbleSortExample {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    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]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

在以上示例代码中，bubbleSort方法中嵌套了两个循环，第一个循环控制比较的轮数，第二个循环控制每轮比较的次数。swap方法用于交换数组中的两个元素。

以上代码的输出结果为：[1, 2, 3, 4, 5, 6, 7, 8]。

3. 选择排序

选择排序的基本思想是每次找到最小的元素，并将其放在已排序的序列末尾。时间复杂度同样为O(n^2)。

下面是一个示例代码：

public class SelectSortExample {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void selectSort(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;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

在以上示例代码中，selectSort方法中嵌套了两个循环，第一个循环控制排序的轮数，第二个循环用于寻找最小元素的下标。swap方法用于交换数组中的两个元素。

以上代码的输出结果为：[1, 2, 3, 4, 5, 6, 7, 8]。