2021-10-10

快速排序是对冒泡排序算法的一种改进

原理：选择一个分界值，根据给定的排序规则将数据分为大于和小于分界值的两个部分，然后再分别对这两部分根据上述方法排序，直至排序完成

	//从小到大 快速排序
    public static void quickSort(int[] nums, int start, int end) {
        //函数出口
        if(start >= end) return;

        int value = nums[start];
        int i = start;
        int j = end;

        while(i < j) {
            //从后面开始寻找小于value的数据
            while (i < j && value <= nums[j]) j--;
            if(i < j) {
                nums[i] = nums[j];
                nums[j] = value;
                i++;
            }

            //从前面开始寻找大于value的数据
            while (i < j && value >= nums[i]) i++;
            if(i < j) {
                nums[j] = nums[i];
                nums[i] = value;
                j--;
            }
        }

        //对value左边的数据进行排序
        quickSort(nums, start, i-1);

        //对value右边的数据进行排序
        quickSort(nums, j+1, end);
    }

	//从大到小 快速排序
    public static void quickSort(int[] nums, int start, int end) {
        //函数出口
        if(start >= end) return;

        int value = nums[start];
        int i = start;
        int j = end;

        while(i < j) {
            //从后面开始寻找大于value的数据
            while (i < j && value >= nums[j]) j--;
            if(i < j) {
                nums[i] = nums[j];
                nums[j] = value;
                i++;
            }

            //从前面开始寻找小于value的数据
            while (i < j && value <= nums[i]) i++;
            if(i < j) {
                nums[j] = nums[i];
                nums[i] = value;
                j--;
            }
        }

        //对value左边的数据进行排序
        quickSort(nums, start, i-1);

        //对value右边的数据进行排序
        quickSort(nums, j+1, end);
    }