快速排序

快速排序（quickSort）的核心思想是分治算法.
它的思想是这样的:如果要排序数组下标从p到r的数据，那么我们取它们之间的任意数据作为分区点（pivot）。然后我们遍历从p到r的数据，将小于pivot的数据都放到pivot的左边，将大于pivot的数据都放到pivot的右边。这样，数据就被分成了三部分，pivot左边的都小于pivot, pivot， pivot右边的都大于pivot.通过这一步之后，pivot就站在了它该站的位置上面了，接下来我们再递归的对pivot左右和右边的数据分别做类似操作，即可完成整个数组的排序。

image.png

我们找出它的递推公式和退出条件如下：

递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)

终止条件：
p >= r

java实现代码如下：

package sort.basic;

import org.junit.Test;

public class QuickSort {
    public void quickSort(int[] data, int start, int end) {
        if (start >= end) return;
        int pivot = partition(data, start, end);
        quickSort(data, start, pivot - 1);
        quickSort(data, pivot + 1, end);
    }

    private int partition(int[] data, int start, int end) {
        int pivot = data[end];
        int index = start;
        for(int i = start; i <= end - 1; i++){
            if(data[i] <= pivot){
                int temp = data[i];
                data[i] = data[index];
                data[index] = temp;
                index++;
            }
        }
        data[end] = data[index];
        data[index] = pivot;
        return index;
    }

    @Test
    public void quickSortTest() {
        int[] data = new int[]{8,10,2,3,6,1,5};
        quickSort(data, 0, data.length - 1);
        output(data);
    }

    private void output(int[] data) {
        for(int i = 0; i < data.length; i++){
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }
}

这里我们解释一下partition部分，
它的思想和插入排序的思想类似，从头遍历start到end-1之间的数据，如果数据小于pivot,则和最前面大于pivot的数据交换，最后将pivot数据和最前面大于pivot的数据交换，返回pivot数据所在位置的index.
过程如下：

image.png

掌握了快速排序之后，下面给大家出一个思考题，如何找到一个无序数组中的第k大元素。欢迎留言讨论