#前言

在这么多的排序算法中，不考虑桶排序，只有堆排序、快速排序、归并排序的时间复杂度是O(nlogn)，今天就来讨论一下神奇的排序算法——快速排序

之所以说快排是个神奇的算法，不仅仅是因为其时间复杂度较低，其中包含的几个比较重要的思想非常值得我们学习一下

#关于快速排序

##基本思想

快速排序算法包含其中一个思想就是分治思想，这也是快排的时间复杂度能够保持在O(nlogn)的关键因素

• 每次从序列中选出一个基准值，其他数依次和基准值作比较，比基准值大的放在右边，比基准值小的放在左边，然后再对左边和右边的数分别选出一个基准值，进行同样的比较移动，重复步骤，直到最后变为单个元素，整个数组就成为了有序的序列

#算法实现

##单边扫描

• 随意抽取一个数作为基准值，同时设定一个标记 mark 代表左边序列最右侧的下标位置，当然初始为 0 ，接下来遍历数组，如果元素大于基准值，无操作，继续遍历，如果元素小于基准值，先将 mark 所在位置的元素和遍历到的元素交换位置，再把 mark + 1 ，mark 这个位置存储的是比基准值小的数据，当遍历结束后，将基准值与 mark 所在元素交换位置即可
• mark的作用就是，从左至右遍历数组时，将第一个小于基准值的数放在0的位置，将第二个小于基准值的数放在1的位置，以此类推...
• 代码：

public class QuickSort1 {
        public static void main(String[] args) {
            nt[] A = {3,2,1,5,4,7,6,6};
            sort(A);
            //partition(a,0,a.length-1);
            System.out.println("排序后的a:"+ Arrays.toString(A));
        }
        private static void sort(int[] arr){
            sort(arr,0,arr.length-1);
        }

        private static void sort(int[] arr,int startIndex,int endIndex){
            if(startIndex >= endIndex) return;
            int p = partition(arr,startIndex,endIndex);
            sort(arr,startIndex,p-1);
            sort(arr,p+1,endIndex);
        }

        private static int partition(int[] arr,int startIndex,int endIndex){
            int mark = 0;
            int pilot = arr[startIndex];
            for(int i=0;i<arr.length;i++){
                if(arr[i]>pilot){
                    continue;
                }
                if(arr[i]<=pilot){
                    int pre = arr[mark];
                    arr[mark] = arr[i];
                    arr[i]=pre;
                    mark++;
                }
            }
            int pre = arr[startIndex];
            arr[startIndex] = arr[mark-1];
            arr[mark-1] = pre;
            return mark-1;
        }
}

##双边扫描

• 随意抽取一个数作为基准值，然后从数组左右两边进行扫描，先从左往右找到一个大于基准值的元素，将下标指针记录下来，然后转到从右往左扫描，找到一个小于基准值的元素，交换这两个元素的位置，重复步骤，直到左右两个指针相遇，再将基准值与左侧最右边的元素交换
• 代码：

public class QuickSort2 {
        public static void main(String[] args) {
            int[] A = {5, 3, 6, 4, 1, 7, 9, 2, 8};
            sort(A);
            System.out.println("排序后的A:" + Arrays.toString(A));
        }

        private static void sort(int[] arr) {
            sort(arr, 0, arr.length - 1);
        }

        //用递归
        private static void sort(int[] arr, int startIndex, int endIndex) {
            //终止条件
            if (endIndex <= startIndex) {
                return;
            }
            int pivotIndex = partition(arr, startIndex, endIndex);
            sort(arr, startIndex, pivotIndex - 1);
            sort(arr, pivotIndex + 1, endIndex);
        }

        private static int partition(int[] arr, int startIndex, int endIndex) {
            int left = startIndex;
            int right = endIndex;
            int pivot = arr[startIndex];
            //这里采用直接覆盖的方式，这样可以省去每次申请的temp变量开销
            while (left < right) {
                while (left < right && arr[right] >= pivot) right--;  // ①
                arr[left] = arr[right];
                while (left < right && arr[left] <= pivot) left++;    // ②
                arr[right] = arr[left];
            }
            arr[left] = pivot;
            return left;
        }
}

#单边扫描与双边扫描基准值选取区别

对于单、双边扫描的算法实现是不同的，但是有个细节，那就是选取基准值pivot

##区别

• 其中单向扫描可以随机地选择pivot值，即可以选择待排序数组中的任意一个元素作为pivot，对结果是没有影响的
• 而双边扫描是不可以随意选取基准值的，一般情况下我们选择第一个或者最后一个元素，但是注意选取的元素位置应与最初扫描方向相反，即：
  • 当我们选择第一个元素作为pivot时，最初应该先右边向左扫描，也就是上述代码① 应该在代码② 之前
  • 反之，当我们选择最后一个元素作为pivot时，最初应该先右边向左扫描，也就是上述代码① 应该在代码② 之后

##为什么呢？

• 其实可以这么理解
• 当最后左右指针即将相遇时（左右指针挨边），此时，左指针指向所有小于基准值的最右边，右指针指向所有大于基准值的最左边
• 下一步就是指针相遇（指的是同一个位置），如果选择第一个作为pivot，按照上述规则，首轮需要右指针先从右往左扫描，有人会问：如果我偏不这么做，那么接下来将会发生什么？
• 如果我们让左指针先从左往右扫描，那么此时左指针往右移动一步与右指针重合，但是刚刚说过，此时右指针指向所有大于基准值的最左边
• 也就是此时重合的位置指向的元素大于基准值，如果此时交换，那么第一个元素就是一个大于基准值的元素
• 最终我们的排序结果中，第一个元素就是一个大于pivot的元素
• 然而，如果我们遵循上述规则，则不会发生这种情况

#快排衍生题

快排还有一些衍生题目，这里简单提一下

如何找出一个无序数组的中位数？

• 思路无非是找到排序之后位于中间的那个数（如果是偶数个，则需要找出中间的两个数）

• 暴力解

  • 可以先将数组排序为有序数组，再找出中位数

• 快排思路

  • 对数组进行partition，每次的 partition 返回一个位置，直到找到中间那个位置

找出一个无序数组中第 k 小的元素，即排序后的第 k-1 位置上的元素？

• 同样，利用快排思想