快速排序、归并排序以及partition和merge的别用

算法分析还有三周考试。。感觉有必要整理一下基础知识,以便通过考试hhhhh。

快速排序

影响快排性能的几个因素,边看代码,边看这里的总结。

  • pivot的选取
    如果pivot直接去选l下标的元素,那么在数组近乎有序的情况下,递归树的高度可能接近n,就导致最后的复杂到到了O(n^2),这是不可接受的,所以在选取pivot时候,我们用random随机数的方法,这样出现上述情况的概率会小很多。如partition中那样写就可以了,nums[l+1.....j]<pivot,用一个i遍历,发现小于pivot的就和j+1位置swap即可。

  • 数组本身属性 是否近乎有序 /是否有重复元素
    实际上上面pivot的选取也可以归到这一点,因为就是为了避免当数组近乎有序的情况下递归深度过大,才随机选取的pivot。那么上述的pivot也只能解决近乎有序的情况。而如果数组中存在大量重复元素,在partition中,我们是把数组分成了两半,这样就导致一个问题,大量重复元素集中于右侧(左侧都是nums[i]<pivot,所以右侧集中了nums[i] == pivot的元素)那么依然会造成递归深度过大的情况,快排退化到O(n^2)了。

    所以partition1中提供了双路快排的思路。左侧遇到 nums[i] < pivot 一直右移i,右侧遇到nums[j] > pivot 一直左移j,那么右移结束的i的位置就是第一个大于等于pivot的数,而左移结束的j的位置就是第一个小于等于pivot的数,不管是等于还是大于小于,这时候交换i和j位置的数,循环结束时候,返回j的值作为partition的index,那么这样一来等于pivot的数集中于某一侧的概率就大大降低了。

    双路快排示意图

    真正是含有等于号的,这样即便是等号也会交换,也就避免了出现等于pivot的数集中在某一侧

当然还有更优化的做法,我们采用三路快排的思路,三路快排把数组分成了三个部分,根据pivot分为小于的和等于的还有大于的。用i去遍历,涉及分界点lt和gt nums[l....lt] < pivot nums[lt+1...i)==pivot i是正在遍历考察的元素 nums[gt.....r] > pivot,递归只针对第一个和第三个部分。哎,人类真是聪明.....下面是示意图。具体实现在代码qSortInThreeWays中。

三路快排示意图

  class QuickSort {
        public static void swap(int[] nums, int i , int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        public static int partition(int[] nums, int l, int r) {
            Random random = new Random();
            int randomIndex = random.nextInt(r-l+1)+l;
            swap(nums, l, randomIndex);
            int pivot = nums[l];
            int j = l;
            for(int i = l +1; i <= r; i++) {
                if (nums[i] < pivot) {
                    swap(nums, i, j+1);
                    j++;
                }
            }
            swap(nums, l, j);
            return j;
        }
        
        public static int partiton1(int[] nums, int l, int r) {
            Random random = new Random();
            int randomIndex = random.nextInt(r-l+1)+l;
            swap(nums, l, randomIndex);
            int pivot = nums[l];
            int i = l+1;
            int j = r;
            while(true) {
                while(i <= r && nums[i] < pivot) i++;
                while(j >= l+1 && nums[j] > pivot) j--;
                if (i>=j) {
                    break;
                }
                swap(nums, i, j);
                
                i++;
                j--;
            }
            swap(nums, l, j);
            return j;
        }
        
        public static void qSortInThreeWays(int [] nums, int l, int r) {
            if (l >= r) {
                return;
            }
            
            Random random = new Random();
            int randomIndex = random.nextInt(r-l+1)+l;
            swap(nums, l, randomIndex);
            
            int pivot = nums[l];
            
            int lt = l;//nums[l+1...lt]<pivot
            int gt = r+1;//nums[gt...r]>pivot
            int i = l+1;//nums[lt+1...i)==pivot
            
            while(i < gt) {
                if (nums[i]<pivot) {
                    swap(nums, i, lt+1);
                    lt++;
                    i++;
                }else if (nums[i] > pivot) {
                    swap(nums, i, gt-1);
                    gt--;
                }else {
                    i++;
                }
            }
            swap(nums, l, lt);
            qSortInThreeWays(nums, l, lt-1);
            qSortInThreeWays(nums, gt, r);
            
        }
        public static void qSort(int[] nums) {
            qSort(nums,0,nums.length-1);
        }
        
        public static void qSort(int[] nums,int l, int r) {
            if (l >= r) {
            return;
        }
            
            int index = partition(nums, l, r);
            qSort(nums,l,index-1);
            qSort(nums,index+1,r);
        }
    }

归并排序

归并排序的时间性能相对快排就要稳定许多,每次都是对半分,所以是稳定的O(nlogn),但是需要O(n)的辅助空间。copy辅助空间再copy回来,可以想象在复杂度表达式中,nlogn后面的其他项还是很多的,这也是为什么大多数情况下qSort会表现更优秀一些的原因。
MergeSort有两种实现方法,自顶向下的递归写法,和自底向上的迭代写法。
最最重要的就是那个merge函数。自顶向下的递归代码见下:

class MergeSort{
    private static void merge(int[] nums, int l, int mid, int r) {
        int[] assit = new int[r-l+1];
        
        int i = 0;
        int newMid = i + mid - l;
        int j = newMid+1;
        int assitIndex = 0;
        while(i<= newMid && j <= assit.length-1) {
            if (nums[l+i]<nums[l+j]) {
                assit[assitIndex++] = nums[l+i];
                i++;
            }else {
                assit[assitIndex++] = nums[l+j];
                j++;
            }
        }
        
        if (i > newMid && j > assit.length-1) {
            return;
        }
        
        if (i <= newMid) {
            while(i <= newMid) {
                assit[assitIndex++] = nums[l+i];
                i++;
            }
        } else {
            while(j <= assit.length-1) {
                assit[assitIndex++] = nums[l+j];
                j++;
            }
        }
        
        for(int k = 0; k < assitIndex; k++) {
            nums[l+k] = assit[k];
        }
    }
    
    public static void mergeSort(int[] nums) {
        mergeSort(nums, 0, nums.length-1);
    }
    
    public static void mergeSort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l) / 2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        merge(nums, l, mid, r);
    }
}

下面是自底向上的迭代写法:sz就是分割的数组长度

    public static void mergeSortBottomToUp(int[] nums) {
        //[i,....i+sz-1] [i+sz....i+2sz-1] [i+2sz....
        for(int sz = 1; sz <= nums.length; sz += sz) {
            for(int i = 0; i + sz < nums.length; i += 2*sz) {
                merge(nums,i, i+sz-1, Math.min(i+2*sz-1, nums.length-1));
            }
        }
    }

最后我们再谈两个qSort和mSort的partition和merge函数的其他用处。

使用partition函数在O(n)时间内找到数组中第K大的元素

想找到数组中第K大的元素,我们第一感觉就是降序排序,然后直接看下标k-1,这样的时间复杂度就是O(nlogn),而利用partition函数,我们可以在O(n)时间内解决这个问题。partition函数的作用就是把pivot归位到它本应该在的位置上面,我们的思路就是,对一个数组按照快排(降序)的模式进行partition,如果partition过程中得到的下标index+1和K相等,那么就找到了这个元素。而做到O(n)的关键是,我们会对每次partition返回的下标进行检查,+1后和K比较,如果大于K,那么我们知道要目标元素肯定在index左边,只去考察l到index-1即可。如果小于K,那么目标元素肯定在index右边,只去考察index+1到r即可。每次可以近似是n+n/2+n/4+n/8+n/16.....这样最后的结果用等比数列求和就是O(2n)

    public static int findTopK(int[] nums, int K) {
        if (K <= 0 || K > nums.length) {
            return -1;
        }
        return findTopK(nums, 0, nums.length - 1, K);
    }
    public static int findTopK(int[] nums, int l, int r, int K) {
        
        int ans = partition(nums, l, r) ;
        if (ans+1  == K) {
            return nums[ans];
        }else if(ans+1 < K){
            return findTopK(nums, ans+1,r,K);
        }else {
            return findTopK(nums, l,ans-1,K);
        }
    }

使用merge函数在O(nlogn)时间内解决逆序对问题

逆序对的定义百度吧,要找到逆序对,暴力解法就是O(n^2),一个一个去遍历。不过我们可以利用mergeSort,在merge的过程中就是找逆序对数的好时机。我们可以设置一个counter。由于merge操作的基本思想是认为merge的两段是排好序的。然后merge的时候,后半段如果先于前半段进入辅助空间,那么counter就要干活了,前半段包括目前正在考察的元素到mid之间全部都可以和后半段正在考察的这个元素构成逆序对,计算下标可以得出counter加的数值,而前半段如果先于后半段进入辅助空间,那么counter就不考虑++。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,558评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,002评论 3 387
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 159,036评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,024评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,144评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,255评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,295评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,068评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,478评论 1 305
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,789评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,965评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,649评论 4 336
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,267评论 3 318
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,982评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,223评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,800评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,847评论 2 351

推荐阅读更多精彩内容

  • <center>#1 Two Sum</center> link Description:Given an arr...
    铛铛铛clark阅读 2,143评论 0 3
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,743评论 0 33
  • 算法思想贪心思想双指针排序快速选择堆排序桶排序荷兰国旗问题二分查找搜索BFSDFSBacktracking分治动态...
    第六象限阅读 3,065评论 0 0
  • 排序算法几种分类方式: 1,稳定排序和不稳定排序 如果a==b, 当排序之前a在b的前面,排序后,a仍然在b...
    fly_ever阅读 411评论 0 0
  • 根据我自己几年来的炒股经历和总结经验,整理出10条小技巧,欢迎采纳借鉴。全干货哦~~~ 1、让盈利积累 获小利而回...
    财商实践传播者阅读 125评论 0 0