快速排序算法详解：从基本思想到代码实现

快速排序算法详解：从基本思想到代码实现

引用

CSDN

1.

https://blog.csdn.net/qq_39181839/article/details/109478094

快速排序是一种非常高效的排序算法，采用分治策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。本文将通过图文结合的方式，详细解释快速排序的原理和实现过程。

基本思想

快速排序的核心思想是选择一个基准元素（base），通过一趟排序将待排序的数据分割成两部分，其中一部分的所有数据都比另一部分的所有数据小，然后再对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

图文详解

以数组 [3,4,6,1,2,4,7] 为例，选择第一个元素 3 作为基准元素（base）。定义两个指针（小熊 l 和小熊 r），分别从两端开始扫描。从右向左找比 base 小的数，替换 l 所在位置的元素；再从左往右找比 base 大的数，替换 r 所在位置的元素。重复此过程直至两个指针重合，此时 base 替换此元素，第一轮结束。再递归排序 base 左右两部分的元素。

初始状态

让小熊 l 指向序列的最左边，指向数字 3。让小熊 r 指向序列的最右边，指向数字 7。

第一轮扫描

小熊 r 向左移动，直到找到比 base（3）小的数（2），替换此时小熊 l 所在位置的元素。

替换后的序列为 [2,4,6,1,2,4,7]。

小熊 l 向右移动，直到找到比 base 大的数（4），替换此时小熊 r 所在位置的元素。

替换后的序列为 [2,1,6,1,4,4,7]，小熊 r 再次向左移动。

小熊 l 向右移动，直到找到比 base 大的数（6），替换此时小熊 r 所在位置的元素。

此时小熊 l 和小熊 r 指向同一元素。

base（3）替换此元素。

第一轮扫描完成，序列为 [2,1,3,6,4,4,7]。此时 base 左边的元素都比它小，右边的元素都比它大，再对这两部分进行上述操作。

代码实现

以下是两种不同风格的快速排序代码实现：

实现一

public static void quickSort(int nums[], int start, int end) {
    // 数组有多个元素进行排序
    if (start < end) {
        int base = nums[start]; // 以要进行排序数组第0个元素为base
        int left = start; // 左指针
        int right = end; // 右指针
        while (left < right) {
            // 从右向左找，比base大，right--
            while (left < right && nums[right] >= base) {
                right--;
            }
            // 比base小，替换left所在位置的数字
            nums[left] = nums[right];
            // 从左向右找，比base小，left++
            while (left < right && nums[left] <= base) {
                left++;
            }
            // 比base大，替换right所在位置的数字
            nums[right] = nums[left];
        }
        nums[left] = base; // 此时left=right，用base替换这个位置的数字
        // 排列比base小的数字的数组
        quickSort(nums, start, left - 1);
        // 排列比base大的数字的数组
        quickSort(nums, left + 1, end);
    }
}

实现二

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

public int partition(int[] arr, int left, int right) {
    int base = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= base) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= base) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = base;
    return left;
}

采用分治的思想，先找到每次分割的点 pos，再排序。通过递归的方式，不断将数组分为更小的部分，直到每个部分都排序完成。