快速排序原理及代码实现

ゝ一纸荒年。 2023-09-27 12:49 116阅读 0赞

快速排序是对 **冒泡排序** 的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

**快速排序和归并排序的区别：**

快速排序是另外一种分治的排序算法，**平均时间复杂度为** **O(nlogn)**，它将一个数组分成两个子数组，将两部分独立的排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序，而快速排序的方式则是当两个数组都有序时，整个数组自然就有序了。在归并排序中，一个数组被等分为两半，归并调用发生在处理整个数组之前，在快速排序中，切分数组的位置取决于数组的内容，递归调用发生在处理整个数组之后。

快速排序需要一个基准值，在基准值的右侧找一个比基准值小的元素，在基准值的左侧找一个比基准值大的元素，然后交换这两个元素，此时会破坏稳定性，所以快速排序是一种**不稳定的算法**。

**排序原理：**

1.首先设定一个 分界值 ，该值可为第一个元素，通过该分界值将数组分成左右两部分；

2.将**大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边**。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；

![bdddba9205fe4d9d8fce67782b82169d.png][]

3.然后，**左边和右边的数据可以独立排序**。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理；

![6f2dca02fa5e466a8396cda914ee87c9.png][]

4.**重复上述过程**，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

**代码实现：**

import java.util.Arrays;
    
    /**
     * 快速排序
     * 切分原理：
     * 把一个数组切分成两个子数组的基本思想：
     * 1.找一个基准值，用两个指针分别指向数组的头部和尾部；
     * 2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
     * 3.再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
     * 4.交换当前左边指针位置和右边指针位置的元素；
     * 5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。
     */
    public class Quick {
        public static void main(String[] args) {
            int arr[] = {2,3,45,2,4,6,2};
            quickSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }
    
        /**
         * 入口函数（递归方法），算法的调用从这里开始。
         */
        public static void quickSort(int[] arr, int startIndex, int endIndex) {
            if (startIndex >= endIndex) {
                return;
            }
    
            // 核心算法部分：双边指针（交换法），找出分界值索引
            int pivotIndex = doublePointerSwap(arr, startIndex, endIndex);
    
            // 用分界值下标区分出左右区间，进行递归调用
            quickSort(arr, startIndex, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, endIndex);
        }
    
        /**
         * 双边指针（交换法）
         * 思路：
         * 记录分界值 pivot，创建左右指针（记录下标）。
         * （分界值选择方式有：首元素，随机选取，三数取中法）
         *
         * 首先从右向左找出比 pivot 小的数据，
         * 然后从左向右找出比 pivot 大的数据，
         * 左右指针数据交换，进入下次循环。
         *
         * 结束循环后将当前指针数据与分界值互换，
         * 返回当前指针下标（即分界值下标）
         */
        private static int doublePointerSwap(int[] arr, int startIndex, int endIndex) {
            int pivot = arr[startIndex];//规定分解值为第一个元素
            int leftPoint = startIndex;//左指针指向开始索引
            int rightPoint = endIndex;//右指针指向结束索引
    
            while (leftPoint < rightPoint) {
                // 从右向左找出比pivot小的数据
                while (leftPoint < rightPoint && arr[rightPoint] > pivot) {
                    rightPoint--;
                }
                // 从左向右找出比pivot大的数据
                while (leftPoint < rightPoint && arr[leftPoint] <= pivot) {
                    leftPoint++;
                }
                // 没有过界则交换
                if (leftPoint < rightPoint) {
                    int temp = arr[leftPoint];
                    arr[leftPoint] = arr[rightPoint];
                    arr[rightPoint] = temp;
                }
            }
            // 最终将分界值与当前指针数据交换
            arr[startIndex] = arr[rightPoint];
            arr[rightPoint] = pivot;
            // 返回分界值所在下标
            return rightPoint;
        }
    }

[bdddba9205fe4d9d8fce67782b82169d.png]: https://img-blog.csdnimg.cn/bdddba9205fe4d9d8fce67782b82169d.png
[6f2dca02fa5e466a8396cda914ee87c9.png]: https://img-blog.csdnimg.cn/6f2dca02fa5e466a8396cda914ee87c9.png