快速排序

最近看了算法图解这本书，讲讲里面的快速排序：

快速排序的精髓在于 基准值和分而治之思想；

快速排序的基本步骤：

1. 选择基准值；
2. 将数组分成两个子数组：小于基准值的元素和大于基准值的元素；(把小于基准值的数 挪到基准值的左边， 大于基准值的数挪到基准值的右边)；
3. 对这个两个子数组进行快速排序。

起初对快速排序还是一脸懵逼，不知道比较基准值后数组元素该如何放置，之后参考其他网上的例子，原来在基准值左右两边的值与基准值比较后，然后左边与右边的值对调；

image.png

如果5是基准值，分别从开头和结尾进行比较，开头比较大于5的，发现7比5大，7拎出来，结尾比较小于5的 3比5小，3拎出来，然后把7和3对调，变成 “5 4 3 2 8 7” 完成一轮对调，然后按这个步骤完成5基准值的对调，以此下去。

话不多说，贴按两头遍历的快速排序代码：

package main.java;


import java.util.Arrays;

/**
 * 快速排序
 *
 *
*/
public class QuickSort {

    public static void main(String[] args) {
        int[] a = {5,4,7,2,8,3};
        System.out.println(Arrays.toString(a));
        quickSort(a);
        System.out.println(Arrays.toString(a));
    }


    private static void quickSort(int[] a) {
        if(a.length  > 0) {
            quickSort(a, 0, a.length -1);
        }
    }

    private static void quickSort(int[] a, int low , int high) {

        if (low > high) {
            return;
        }

        int i = low;
        int j = high;

        int key = a[low];

        while (i < j) {
            // 右边比基准小的, 跳出循环
            while (i < j && a[j] > key) {
                j--;
            }

            // 左边比基准大的, 跳出循环
            while (i < j && a[i] <= key) {
                i++;
            }

            if(i < j) {
                // 置换
                int p = a[i];
                a[i] = a[j];
                a[j] = p;


            }




        }

        int p = a[low];
        a[low] = a[i];
        a[i] = p;

        quickSort(a, low, i -1);
        quickSort(a, i + 1, high);

    }

}