侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 102 篇文章
  • 累计创建 14 个标签
  • 累计收到 14 条评论

算法练习(22) - 快排:原址排序

惊羽
2022-03-10 / 0 评论 / 0 点赞 / 430 阅读 / 912 字
温馨提示:
本文为原创作品,感谢您喜欢~

1. 思路

将一个数组的最后一位数字(a[q])作为"元",从头a[p]开始跟这个数字比较(索引从i(i=p)开始),使用一个变量作为指针(point) , 如果a[i] 小于 a[q] ,将其与a[point] 互换; 同时 point 向前移动(point++),这样使得比"元"小的数值都放到了a[p] ~ a[point] 之中; 最后将 a[point+1] 与a[q]互换,最后的结果就是以a[point+1] 为界, 左边全小于"元",右边全大于"元";最后左右两边递归调用以上方法即可完成原址排序

2. code

public class QuickSortTest {

    @Test
    public void quickSort_test() {
        int[]  a = {1,9,3,4,7,2,9,10,14,16};
        quickSort(a,0,a.length-1);

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
            System.out.print(",");
        }
    }

    private void quickSort(int[] a, int p, int q) {
       if(p<q){
           int r = partition(a,  p,  q);
           quickSort(a,p,r-1);
           quickSort(a,r+1,q);
       }
    }

    private int partition(int[] a, int p, int q) {

        int x = a[q];
        int point = p-1;
        for (int i = p; i < q; i++) {
            if(a[i] < x){
                point ++;
                int temp = a[i];
                a[i] = a[point];
                a[point] = temp;
            }
        }

        int temp = a[point+1];
        a[point + 1 ] = a[q];
        a[q] = temp;
        return point +1;
    }

}

3. 复杂度分析

递归调用,复杂度记为$O(lgn)$ ,每次partition 为$O(n)$ , 整体复杂度为 $O(nlgn)$
当然,这个值并不准确,在极端坏的情况下为$O(n^2)$ ,极端好的情况下为$O(lgn)$

0
广告 广告

评论区