快速排序（重点）

本是古典何须时尚 2024-03-03 06:54 1阅读 0赞

## 前言 ##

快排是一种比较重要的排序算法，他的思想有时候会作用到个别算法提上，公司招聘的笔试上有时候也有他的过程推导题，所以搞懂快排势在必行！！！

## 快速排序 ##

**基本思想：** 根据基准，将数据分成两个部分，一部分小于基准，另一部分大于基准，然后在通过分治是思想，将每个部分在进行上述操作，最终合并结果  
**时间复杂度：** 最好情况O(nlogn)，最坏情况O(n^2)；  
**排序稳定性：** 不稳定；

现在主流上，快排有两种实现方式，一种是单边循环，一种是双边循环，我个人认为双边循环比较容易理解记忆，而且效率更高一点，所以我还是推荐学习后者即可。

## 详细介绍（双边） ##

1.  选择最左元素作为基准点元素
2.  j指针负责从右向左找比基准点小的元素，i指针负责从左向右找比基准点大的元素 ()，一旦找到二者交换，直至i，j相交
3.  最后基准点与i(此时i与i相等)交换，i即为分区位置

图示：  
![在这里插入图片描述][5773888b99944840a6ac71736323caac.png_pic_center]  
**准备工作：** i、j指针分别执行数组首尾，而我们的基准pv选择首  
**i的任务：** 从左往右找比基准大的值  
**j的任务：** 从右往左找比基准小的值  
**交换：** 当 i 和 j 的任务都完成后，就将二者的值进行swap，  
**停止：** 当左右指针相遇的时候，停止并且，pv指针的值和i指针进行交换  
**结果：** 这个时候就做到了以基准为分界线，左右两边被分成了两个部分的目的，记录pv当前所在位置

> 因为上面只是一轮的比较，为了完全排序，我们还需要对两个部分的数据进行递归

快速排序代码实现：

public class QuickSort {
        
    
        public static void main(String[] args) {
        
            int[] arr = new int[]{
        5, 8, 6, 1, 12, 13, 14};
            quickSort(arr, 0, arr.length - 1);
        }
    
        private static void quickSort(int[] arr, int l, int r) {
        
            // 大于：说明后面两个部分都已经排好了
            // 等于：同一个数之间没有排序意义
            if (l >= r) {
        
                return;
            }
            int pv = partition(arr, l, r);
            quickSort(arr, l, pv - 1);
            quickSort(arr, pv + 1, r);
        }
    
        // 对于将头设置为pv的情况，我们必须先找右再找左，否则会出现错误
        // 举个例子（反例）：
        // pv指向头的情况下，我们先往左寻找，那么i和j相遇的地点一定是在j的位置上（i<j，i就会比j多走一步），
        // 在j的位置的值是比pv的值大的，当将 i 和 pv 进行交换的时候，就会将大的值置换到基准的左边从而导致排序出现问题
        //
        // 那么反过来，我们先找的j，由于i<j，那么j就会多走一步，在i的位置上相遇，而i位置上的值又是比pv小的，
        // 所以二者交换pv两边符合一小一大的排序规则。
        //
        // 如果说，你实在是要先走左边，那么你的基准指针pv应该自信数组末尾！！！
        private static int partition(int[] arr, int l, int r) {
        
            int pv = arr[l];
            int i = l;
            int j = r;
            // 当l == r就会退出
            while (i < j) {
        
                // 从右往左找大
                while (i < j && arr[j] > pv) {
        
                    j--;
                }
                // 从左往右找小
                // 遇到相等就继续往右走
                while (i < j && arr[i] <= pv) {
        
                    i++;
                }
                // 当i和j都在一个位置的时候没有交换的意义
                if(i != j){
        
                    swap(arr, i, j);
                }
            }
            // 循环出来后交换i和pv的值
            swap(arr, l, j);
            return i;
        }
    
        private static void swap(int[] arr, int i, int j) {
        
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }

排序结果：

[1, 5, 6, 8, 12]

> 部分细节说明，已经写在代码中，请详细阅读

以上是本文全部内容，感谢阅读

[5773888b99944840a6ac71736323caac.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/9486c9ff98434ee7a9756a16c9ef203f.png