【常用排序算法】快速排序

##快速排序

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法

• 先从数列中取出一个数作为基准数pivot。
• 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 再对左右区间重复第二步，直到各区间只有一个数。

package com.xiaoyg.algorithm.sort;
import java.util.Arrays;
public class QuickSort {
    public static void main(String[] args) {
        int[] values = {17,14,13,29,25,8,4};
        System.out.println("values数组原始顺序："+ Arrays.toString(values));
        quickSort(values, 0, values.length - 1);
        System.out.println("values数组排序后顺序："+ Arrays.toString(values));
    }
    private static void quickSort(int[] values, int left,int right) {
        //如果左值>=右值，不需要进行排序。
        if (left >= right) return;
        //取出基准值
        int pivot = values[left];
        //定义左值和右值
        int le = left;
        int ri = right;
        //左值下标小于右值下标示时，开始循环比较
        while (le < ri){
            //右值大于等于中值，不需要交换值，只需要将右标左移
            while (le < ri && values[ri] >= pivot){
                ri --;
            }
            //右值小于中值时，将右标值赋给左标值，即将小于中值的放到左边。
            if (le < ri){
                values[le] = values[ri];
            }
            //左值小于等于中指，说明不需要交换值，将左标右移
            while (le < ri && values[le] <= pivot){
                le ++;
            }
            //左值大于中值，需要将左值赋给右标值。
            if (le < ri){
               values[ri] = values[le];
            }
            //本轮比较结束，将中值放在当前游标的位置，这样，左边都是小于中值的，右边都是大于中值的。
            if (le <= ri){
                values[le] = pivot;
            }
        }
        //递归中值左边的操作，重复上方的逻辑
        quickSort(values, left, ri - 1);
        //递归中值右边的操作，重复上面的逻辑。
        quickSort(values, ri + 1, right);
    }
}