QuickSort

快速排序

在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。

这种思路就叫做分治法。

每次把数列分成两部分，究竟有什么好处呢？

• 假如给定8个元素的数列，一般情况下冒泡排序需要比较8轮，每轮把一个元素移动到数列一端，时间复杂度是O（n^2）。在分治法的思想下，原数列在每一轮被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。这样一共需要多少轮呢？平均情况下需要logn轮，因此快速排序算法的平均时间复杂度是 O（nlogn）。

基准元素的选择

基准元素，英文pivot，用于在分治过程中以此为中心，把其他元素移动到基准元素的左右两边。

• 最简单的方式是选择数列的第一个元素：这种选择在绝大多数情况是没有问题的，但是对于一个已经存在顺序的数组这种效果就比较差了；

• 随机选择一个元素作为基准元素。这样一来，即使在数列完全逆序的情况下，也可以有效地将数列分成两部分。

元素的移动

1.挖坑法

• 首先，我们选定基准元素Pivot，并记住这个位置index，这个位置相当于一个“坑”。并且设置两个指针left和right，指向数列的最左和最右两个元素： 如下图

• 从right指针开始，把指针所指向的元素和基准元素做比较。如果比pivot大，则right指针向左移动；如果比pivot小，则把right所指向的元素填入坑中。

第一轮开始
Pivot = 3，left = 0, right = 7

algorithm-Fast-Sort-1.png

第二轮开始
Pivot = 8，left = 3, right = 7

algorithm-Fast-Sort-2.png

第三轮开始
Pivot = 7，left = 3, right = 5

algorithm-Fast-Sort-3.png

1.挖坑法代码实现如下

/**
 *
 *
 * @description
 * @see
 * @author maozhengwei
 * @data 2019-05-23 10:49
 * @version V1.0.0
 **/
public class QuickSort1 {

    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        // 递归结束条件：startIndex大等于endIndex的时候
        if(startIndex >= endIndex) {
            return;
        }
        // 得到基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);
        // 用分治法递归数列的两部分
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
}

    private static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个位置的元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;
        // 坑的位置，初始等于pivot的位置
        int index = startIndex;
        //大循环在左右指针重合或者交错时结束
        while ( right >= left  ){
            //right指针从右向左进行比较
            while ( right >= left ) {
                if (arr[right] < pivot) {
                    arr[left] = arr[right];
                    index = right;
                    left++;
                    break;
                }
                right--;
            }
            //left指针从左向右进行比较
            while ( right >= left ) {
                if (arr[left] > pivot) {
                    arr[right] = arr[left];
                    index = left;
                    right--;
                    break;
                }
                left++;
            }
        }
        arr[index] = pivot;
        return index;
}

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

2. 指针交换法
指针交换开始都填坑法是一样的，只是元素的交换方式不一样：

• 从right指针开始，把指针所指向的元素和基准元素做比较。如果大于等于pivot，则指针向左移动；如果小于pivot，则right指针停止移动，切换到left指针。

• 轮到left指针行动，把指针所指向的元素和基准元素做比较。如果小于等于pivot，则指针向右移动；如果大于pivot，则left指针停止移动：left和right指向的元素进行交换**。
  下面是图解：

第一轮：

algorithm-Fast-Sort-4.png

第二轮：

algorithm-Fast-Sort-5.png

第三轮：

algorithm-Fast-Sort-6.png

代码实现：

/**
 * 指针交换
 * @see
 * @author mzw
 * @data 2019-05-23 14:42
 * @version V1.0.0
 **/
public class QuickSort2 {

    public static void quickSort2(int[] arr, int startIndex, int endIndex) {
        // 递归结束条件：startIndex大等于endIndex的时候
        if(startIndex >= endIndex) {
            return;
        }
        // 得到基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);
        // 根据基准元素，分成两部分递归排序
        quickSort2(arr, startIndex, pivotIndex - 1);
        quickSort2(arr, pivotIndex + 1, endIndex);
    }

    private static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个位置的元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while ( right != left  ){
            //right指针从右向左进行比较,小于则终止循环
            while ( left < right && arr[right] > pivot ) {
                right--;
            }
            //left指针从左向右进行比较，大于则准则循环
            while ( left < right && arr[left] <= pivot ) {
                left++;
            }
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        //指针重合
        int p = arr[left];
        arr[left] = arr[startIndex];
        arr[startIndex] = p;
        return left;
    }

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