首页　>　文章列表　>　实现和改进Java中的快速排序算法

实现和改进Java中的快速排序算法

快速排序优化算法实现
170 2024-02-18

Java快速排序算法实现及优化

快速排序是一种经典的排序算法，在实际应用中具有广泛的应用。本文将介绍Java中快速排序算法的实现，并通过优化提升算法的效率。

快速排序算法原理
快速排序采用了分治的思想，其基本思想是通过一个"基准"将待排序的序列分成两部分，其中一部分小于基准，另一部分大于基准，然后对两部分分别递归地进行快速排序，最终使得整个序列有序。

具体实现过程如下：

选择一个基准元素，通常选择序列的第一个元素。
设置两个指针low和high，分别指向序列的头部和尾部。
从high开始，向前搜索找到一个比基准小的元素，并将其移动到low的位置；然后从low开始，向后搜索找到一个比基准大的元素，并将其移动到high的位置。
重复上述过程，直到low和high相遇。
将基准元素放入相遇的位置，此时基准元素左边的元素都小于它，右边的元素都大于它。
对基准元素左右两部分分别递归调用快速排序。

Java实现快速排序算法
下面是Java中实现快速排序算法的示例代码：

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high); // 基准元素的位置
            quickSort(arr, low, pivot - 1); // 对基准元素左边的子序列进行快速排序
            quickSort(arr, pivot + 1, high); // 对基准元素右边的子序列进行快速排序
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low]; // 选择第一个元素作为基准元素
        while (low < high) {
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high]; // 将比基准小的元素移到低端

            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low]; // 将比基准大的元素移到高端
        }
        arr[low] = pivot; // 基准元素放入相遇的位置
        return low; // 返回基准元素的位置
    }

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

以上是快速排序算法的基本实现，可以通过main方法测试排序结果。