快速排序具体实现

不稳定但是论文级别可以做到稳定排序01 stable sort

普通快速排序

/**
 * @description：快速排序
 * @Author MRyan
 * @Date 2020/5/2 15:47
 * @Version 1.0
 */
public class Quick_Sort {
    private static int[] nums = {2, 3, 0, 1, 5, 10};

    public static final void main(String[] args) {
        quickSort(0, nums.length - 1);
        print_nums(nums);

    }

    public static void quickSort(int l, int r) {
        if (l < r) {
            int i, j, x;
            i = l;
            j = r;
            x = nums[i];
            while (i < j) {
                //如果不符合j就--继续找直到找到为止
                while (i < j && nums[j] >= x) {
                    /*确定j的位置*/
                    j--;
                }
                /*确定满足为止就挖坑在填坑*/
                if (nums[j] < x) {
                    nums[i] = nums[j];
                }
                /*如果不符合i就++继续找直到找到为止*/
                while (i < j && nums[i] <= x) {
                    /*确定i的位置*/
                    i++;
                }
                /*确定满足为止就挖坑在填坑*/
                if (nums[i] > x) {
                    nums[j] = nums[i];
                }
            }
            nums[i] = x;
            /* 递归调用 */
            quickSort(l, i - 1);
            /* 递归调用 */
            quickSort(i + 1, r);
        }
    }

    public static void print_nums(int[] nums) {
        for (int i : nums) {
            System.out.print(i + " ");
        }
    }
}

递归版：随机选择排序

/**
 * @description：快速排序
 * @Author MRyan
 * @Date 2020/5/2 15:47
 * @Version 1.0
 */
public class Quick_Sort {
    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 5, 7, 6, 5, 4, 5};
        sort(nums, 0, nums.length - 1);
        print_nums(nums);
    }

     public static void sort(int[] nums, int l, int r) {
        if (l < r) {
            swap(nums, l + (int) (Math.random() * (r - l + 1)), r);
            int[] solve = partition(nums, l, r);
            //solve[0]表示小于区边界
            sort(nums, l, solve[0]);
            //solve[1] + 1 表示去除相等元素的大于区边界
            sort(nums, solve[1] + 1, r);
        }

    }

    /**
     * @param nums
     * @param l
     * @param r
     */
    public static int[] partition(int[] nums, int l, int r) {
        //  ）2 3 1 5 7 6 5 4 （5
        //小于区边界 初始化任何元素都不在小于区
        int left = l - 1;
        //大于区边界  初始化将最后一个元素放入大于区
        int right = r;
        //当前值索引超过大于区边界退出结束
        while (l < right) {
            //当前值nums[l] 等于 划分值nums[r]
            if (nums[l] == nums[r]) {
                //当前值位置后移
                l++;
            }
            //当前值nums[l] 小于 划分值nums[r]
            else if (nums[l] < nums[r]) {
                //小于区下一个元素和当前值交换 并且 小于区边界后移  当前值位置后移
                swap(nums, ++left, l++);
            }
            //当前值nums[l] 大于 划分值nums[r]
            else if (nums[l] > nums[r]) {
                //大于区前一个元素和当前值交换 并且 大于区边界前移  下次循环继续比较当前值和划分值大小
                swap(nums, --right, l);
            }
        }
        //因为最开始初始化将划分值归入大于区中，所以最后将划分值和大于区第一个值交换
        swap(nums, right, r);
        return new int[]{left + 1, right};
    }

    public static void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }


    public static void print_nums(int[] nums) {
        for (int i : nums) {
            System.out.print(i + " ");
        }
    }
}

复杂度

平均时间复杂度：O（nlogn）
最优时间复杂度：O（nlogn）
最差时间复杂度：O（n方）
最优空间复杂度：O（logn）
最差空间复杂度：O（n）

本文地址：https://blog.csdn.net/qq_35416214/article/details/107459392