在待排序的n个记录中任取一个记录（通常取第一个元素）作为枢轴，设其关键字为key

经过一趟排序后，把所有关键字小于key的记录交换放到key前面，把所有关键字记录大于key的记录交换放到key后面，结果将待排序的记录分成了两个子表，最后将枢轴key放到分界处的位置

然后，分别对上面的左、右两个子表重复上述的过程，直至每一个子表只有一个元素时，则排序完成

其中一趟快速排序的具体步骤如下：

选择待排序表中的第一个记录作为枢轴, 将枢轴记录暂存在r[0]的位置上。附设两个指针low和high,初始时分别指向表的下界和上界(第一趟时，low= 1; high = L.length; )。

从表的最右侧位置依次向左搜索,找到第一个关键字小于枢轴关键字key的记录,将其移到low处。具体操作是：当low<high时，若high所指记录的关键字大于等于key,则向左移动指针high （执行操作–high）;否则将high所指记录移到low所指记录。

再从表的最左侧位置,依次向右搜索找到第-一个关键字大于key的记录和枢轴记
录交换。具体操作是:当low<high时，若low所指记录的关键字小于等于key,则向右移动
指针low (执行操作++low );否则将low所指记录与枢轴记录交换。

复步骤2和3，直至low与high相等为止。此时low或high的位置即为枢轴在此趟排
序中的最终位置，原表被分成两个子表。

在上述过程中，记录的交换都是与枢轴之间发生，每次交换都要移动3次记录，可以先将枢
轴记录暂存在r[0]的位置上，排序过程中只移动要与枢轴交换的记录，即只做r[low]或r[high]的
单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。

3.算法特点

由于记录是非顺次移动导致快速排序是不稳定排序

排序过程中需要定位表的下界和上界，所以适用于顺序结构，很少用于链式结构

当n较大时，在平均情况下快速排序是所有内部排序中速度最快的一种

故其适用于初始记录无序、n较大的情况

二、算法实践

1.Java代码

package TwentyOne_Challenge;

public class DayEight{
    public static void main(String[] args) {
        int a[]={7,13,6,50,25,78,11,100};
        System.out.println("原来无序序列为：");
        for (int i = 0; i < a.length ; i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
        System.out.println("经快速排序后：");
        //快速排序法
        quickSort(a);
        for (int i = 0; i < a.length ; i++) {
            System.out.print(a[i]+" ");
        }
    }
    private static void quickSort(int[] array) {
        quickSortFunc(array, 0, array.length-1);
    }
    private static void quickSortFunc(int[] array, int start, int end) {
        if (start >= end) return;
        //找基准值的下标
        int keyIndex = findKey(array, start, end);
        //对左子序列进行递归快速排序
        quickSortFunc(array, start, keyIndex-1);
        //对右子序列进行递归快速排序
        quickSortFunc(array, keyIndex+1, end);
    }
    private static int findKey(int[] array, int left, int right) {
        //取左边界元素为基准值，该位置“挖坑”
        int key = array[left];
        int start = left;
        int end = right;
        while (start < end) {
            //从右往左扫描，寻找比key小的记录
            while (start < end && array[end] >= key) {
                end--;
            }
            array[start] = array[end];
            //从左往右扫描，寻找比key大的记录
            while (start < end && array[start] <= key) {
                start++;
            }
            array[end] = array[start];
        }
        //start与end相等时的位置，即到达基准值位置
        array[start] = key;
        //返回基准值的下标
        return start;
    }
}