快速排序算法 Java实现

快速排序也学了几年了，一直学一直忘，最近在刷LeetCode的时候发现有几道快速选择的题目要用到快速排序的思想，现在来复习一下快速排序。

时间复杂度：
O(NlogN)

稳定性：
不稳定

思想：

• 从数组中随机选择一个数组作为切点，第一轮排序完之后要让切点左边的数都小于这个切点，让切点右边的数都大于这个切点。
• 之后递归的排序切点左边的数组，再递归的排序切点右边的数组。完成排序。

通俗来讲，可以把快速排序这个过程看成挖坑和填坑，首先选择切点，相当于在切点所在数组的位置挖了一个坑，然后开始从右边开始遍历数组，找到比数组小的那个数字来填上这个坑，这个数字填完这个坑之后，自己本身在的位置又出现一个坑，需要从左边来找大于切点的数来填上这个坑。以此类推，直到low == high，循环结束，然后把切点放在low这个指针处，就保证了切点左边的都小于切点，切点右边的都大于切点。

具体来看代码：

public class Test {
    public void quickSort(int[] nums, int i, int j) {
        if (i > j) {
            return;
        }

        int p = nums[i];// 我们这里选择数组第一个数作为切点
        int low = i;
        int high = j;

        while (low < high) {
            /*
                从数组的右边开始遍历，直到遇见小于切点p的数字
             */
            while (low < high && p < nums[high]) {
                high--;
            }
            /*
                找到这个数字之后，把这个数字赋值给我们我们切点的位置
             */
            if (low < high) {
                nums[low++] = nums[high];
            }
            /*
                同理，我们从数组左边开始遍历，找到小于切点P的数字为止
             */
            while (low < high && p > nums[low]) {
                low++;
            }
            /*
                找到这个数字之后，把这个数字赋值给 刚才拿到前面来的那个数字 的位置
             */
            if (low < high) {
                nums[high--] = nums[low];
            }
        }
        /*
            遍历完成之后，把切点赋值到low或者high指针处，这样就保证了切点左边的数字都小于切点，切点右边的数字都大于切点
         */
        nums[low] = p;
        /*
            递归遍历切点两边的数组
         */
        quickSort(nums, i, low - 1);
        quickSort(nums, low + 1, j);
    }

    public static void main(String[] args) {
        int[] nums = {4,7,9,2,1,8,5,6,3};
        new Test().quickSort(nums,0,8);
        for (int i : nums){
            System.out.println(i);
        }
    }
}