欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

快速排序具体实现

程序员文章站 2022-12-20 15:14:30
不稳定但是论文级别可以做到稳定排序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) {...

不稳定但是论文级别可以做到稳定排序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