算法导论公开课笔记(四)顺序统计、中值

顺序统计

问题场景:给定具有n个元素的数组,已知数组是无序的,请找到第k小的元素并返回该元素(TOP K问题)。
根据之前所学的算法我们可以得出一个原始方案:
使用运行时间为Θ (nlgn)的排序算法(堆排序、归并排序)进行排序后返回数组索引为K的元素。
该问题当K为如下特殊值的时候的情形:

  • K=1 : 最小值
  • K=n : 最大值
  • K=(n-1)/2: 中值


    k值表示的不同意义

随机化分治法

  • 随机化选择法

用到了前面讲的随机化快速排序的子操作randomizedPartition

方法的大致运行流程是这样的:
如果开始位置和结束位置一样时算法视为找到,返回开始位置的元素;否则进行随机化分割,当分割后的主元位置和需要查找的第index小的位置对应时视为找到,当前主元就是需要查找的元素。否则,将问题划分为更小规模的问题,如果主元位置p>index那么在[left,p]范围内的数据进行随机化选择操作;否则从主元的右侧进行随机话选择操作。方法介绍完毕,需要注意的是不同的分割导致index的变化是一个需要关注的点。

    package me.ziuo.ai.intro;

import java.util.Random;

/**
 *            
 *             {48,6,57,88,60,42,83,73,49,85,99,1424,35,242,6567,34,2,5};
 *             
 *             ------------------------------------------------
 *             随机化选择第 index 小的元素
 *             top 1 is 2.
 *             top 2 is 5.
 *             top 3 is 6.
 *             top 4 is 34.
 *             top 5 is 35.
 *             top 6 is 42.
 *             top 7 is 48.
 *             top 8 is 49.
 *             top 9 is 57.
 *             top 10 is 60.
 *             top 11 is 73.
 *             top 12 is 83.
 *             top 13 is 85.
 *             top 14 is 88.
 *             top 15 is 99.
 *             top 16 is 242.
 *             top 17 is 1424.
 *             top 18 is 6567.
 *          
 * @author eboy
 *
 * @description 随机化的选择算法,用于求解top k 问题
 **/
public class RandomizedSelect {
    
    /**
     * @return 随机化主元分割点位置
     * 
     * @param src
     *            待划分的数组,分割后的结果保证,mid前的元素都是小于等于它的,右侧的元素都是大于等于它的
     * @param left
     *            左边界
     * @param right
     *            右边界   
     */
    private static int randomizedPartition(int[] src, int left, int right) {

        /*随机选取主元元素*/
        Random random = new Random();
        int random_index = random.nextInt(right-left+1)+left;
        
        //感兴趣的话,可以打印一下主元的位置
//      System.out.println("random_index="+random_index);
    
        /**
         * 交换
         */
        int temp = src[random_index];
        src[random_index] = src[left];
        src[left]=temp;
        
        int key = src[left];//挖坑
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && src[j] > key) {
                j--;
            }
            
            if (i < j) {
                src[i++] = src[j];// 挖坑填数
            }

            while (i < j && src[i] < key) {
                i++;
            }
            
            if (i < j) {
                src[j--] = src[i];// 挖坑填数
            }

        }
        src[i] = key;//填空

        // 这种情况下第一趟结束 i的坐标都比他小i的右边都比他大
        return i;

    }
    
    /**
     * 
     * @param src
     * @param left
     * @param right
     * @param index
     * @return 返回 第 index 小的元素
     */
    public static int  randomizedSelect(int[] src, int left, int right, int index) {
        
        if(left==right) return src[left];//待分割的边界到只有一个元素时,该元素作为结果返回
        
        int mid =randomizedPartition(src, left, right);//随机化分割后,主元所在位置
        
        int key=mid-left+1;
        
        if(index==key) return src[mid];
        else if(index<key) return randomizedSelect(src, left, mid-1, index);
        else return randomizedSelect(src, mid+1, right, index-key);//top i问题分解成top i-key
        
    }

}

该算法的最坏情况的运行时间是Θ(n²);期望运行时间为Θ(n)。

虽然,随机化选择算法的期望运行时间是线性的,但是出现最坏的情况的话效率很低,尽管出现最坏的情况的概率是极其低的。

最终人类还是创造出最坏情况为线性的选择算法。

最坏情况为线性的选择算法

选择算法概述

该算法是对随机化选择主元的优化版本,最坏情况的运行时间是线性的即O(n)。和随机化的选择排序一样,快速选择算法通过对输入数组的递归划分找出所需的元素,但是该算法那能给个保证得到对数组的一个好的划分。快速选择算法使用的也是来自快速排序的确定性划分算法PARTITION,做了部分修改,将划分的主元也作为输入参数。
代码如下:

package me.ziuo.ai.intro;

import java.util.Random;

/**
 *            
 *             {7,9,8,6,3,5,2,4,1
                ,18,10,15,17,10,12,19,14,13
                ,34,58,79,21,16,53,23,22,11
                ,23,48,29,16,55,37,28,51,50
                ,22,18,27,35,53,27,96,88,101}
 *             
 *             ------------------------------------------------
 *             最坏情况运行时间为线性的选择第 index 小的元素
 *             top 1 is 1.
 *             top 2 is 2.
 *             top 3 is 3.
 *             top 4 is 4.
 *             top 5 is 5.
 *             top 6 is 6.
 *             top 7 is 7.
 *             top 8 is 8.
 *             top 9 is 9.
 *             top 10 is 10.
 *             top 11 is 10.
 *             top 12 is 11.
 *             top 13 is 12.
 *             top 14 is 13.
 *             top 15 is 14.
 *             top 16 is 15.
 *             top 17 is 16.
 *             top 18 is 16.
 *             top 19 is 17.
 *             top 20 is 18.
 *             top 21 is 18.
 *             top 22 is 19.
 *             top 23 is 21.
 *             top 24 is 22.
 *             top 25 is 22.
 *             top 26 is 23.
 *             top 27 is 23.
 *             top 28 is 27.
 *             top 29 is 27.
 *             top 30 is 28.
 *             top 31 is 29.
 *             top 32 is 34.
 *             top 33 is 35.
 *             top 34 is 37.
 *             top 35 is 48.
 *             top 36 is 50.
 *             top 37 is 51.
 *             top 38 is 53.
 *             top 39 is 53.
 *             top 40 is 55.
 *             top 41 is 58.
 *             top 42 is 79.
 *             top 43 is 88.
 *             top 44 is 96.
 *             top 45 is 101.
 *          
 * @author eboy
 *
 * @description 确定性划分算法的选择算法,用于求解top k 问题
 **/
public class Select {
    
     int[] midianArray;//中位数数组

    
    /**
     * @return 随机化主元分割点位置
     * 
     * @param src
     *            待划分的数组,分割后的结果保证,mid前的元素都是小于等于它的,右侧的元素都是大于等于它的
     * @param left
     *            左边界
     * @param right
     *            右边界   
     */
    private  int partition(int[] src, int left, int right,int pivotIndex) {


        /**
         * 交换
         */
        int temp = src[pivotIndex];
        src[pivotIndex] = src[left];
        src[left]=temp;
        
        int key = src[left];//挖坑
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && src[j] > key) {
                j--;
            }
            
            if (i < j) {
                src[i++] = src[j];// 挖坑填数
            }

            while (i < j && src[i] < key) {
                i++;
            }
            
            if (i < j) {
                src[j--] = src[i];// 挖坑填数
            }

        }
        src[i] = key;//填空

        // 这种情况下第一趟结束 i的坐标都比他小i的右边都比他大
        return i;

    }
    
    
    /**
     *  最坏情况运行时间为线性的选择排序算法的入口方法
     * @param src
     * @param left
     * @param right
     * @param key
     * @return
     */
    public int qSelect(int[] src, int left, int right, int key){
        midianArray=new int[src.length/5 + 1];
        
        return select(src, left, right, key);
    }

    /**
     * 
     * @param src
     * @param left
     * @param right
     * @param key
     * @return 返回 第 index 小的元素
     */
    private  int  select(int[] src, int left, int right, int key) {
        
        
        /**
         * 1.寻找中位数的中位数
         * 2.进行递归找到第k小的元素
         */
        
        int median=findMedian(src,left,right);
//      System.out.println("median is "+median);

        int medianIndex=findMedianIndex(src, left, right, median);
//      System.out.println("medianIndex is "+medianIndex);

        int pivotIndex =partition(src, left, right,medianIndex);//根据主元进行划分,返回主元划分后的位置
        
        int index=pivotIndex-left+1;
        
        if(key==index) return src[pivotIndex];
        else if(key<index) return select(src, left, pivotIndex-1, key);
        else return select(src, pivotIndex+1, right, key-index);//top i问题分解成top i-key
        
    }
    
    private int findMedianIndex(int[] src ,int left,int right,int median){
        
        for(int i=left;i<=right;i++){
            if(src[i]==median) 
                return i;
        }
        return -1;
    }
    

    private  int findMedian(int[] src, int left, int right) {

        if(left==right) return src[left];//范围内只有一个元素时,该元素作为结果返回

        /**
         * 1.元素分组:将输入数组中的n个元素划分为【n/5】个中位数,且至多只有一组由剩下的n mod 5个元素组成。
         * 2.寻找【n/5】个中位数:首先对没组元素进行插入排序,然后确定每组元素的中位数。
         * 3.找到中位数:找出中位数的中位数。
         */
        
        //1.元素分组
        //2.寻找【n/5】个中位数
        int index;
        for(index=left;index<right-5;index+=5){//分组整除部分的数据
            insertSort(src,index,4);
            int num=index - left;
            midianArray[num/5]=src[index+2];//中位数赋值
        }
        //分组余下的元素
        int remainNum=right-index+1;
        if(remainNum>0){
            insertSort(src,index,remainNum-1);
            int num=index - left;
            midianArray[num/5]=src[index+remainNum/2];//中位数赋值
        }
        //3. 递归找到中位数的中位数
        int elemAuxArray=(right-left)/5-1;
        if((right-left)%5!=0) elemAuxArray++;
        
        if(elemAuxArray==0) 
            return midianArray[elemAuxArray];
        else                
            return findMedian(midianArray,0,elemAuxArray);
    }


    /**
     * 子数组插入排序
     * @param src 母数组
     * @param left 开始为止
     * @param loopLength 步长
     */
    private  void insertSort(int[] src, int left, int loopLength) {

        for(int j=left; j<left+loopLength;j++){
            int key=src[j];
            int i=j-1;
            while(i>left && src[i]>key){
                src[i+1]=src[i];
                i--;
            }
            src[i+1]=key;
        }
    }

}

测试代码如下:

public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] arr ={48,6,57,88,60,42,83,73,49,85};

        /**
         *  random_index=9
         *  random_index=3
         *  random_index=1
         *  random_index=2
         *  random_index=6
         *   =4
         *  random_index=5
         *  sorted is {6,42,48,49,57,60,73,83,85,88}
         */
        
        System.out.println("------------------------------------------------");
        System.out.println("随机化选快排的运算过程");

        RandomizedQuickSort.randomizedQuickSort(arr,0, arr.length-1);
        for(int i=0;i<arr.length;i++){
            if(i==arr.length-1) System.out.print(arr[i]);
            else System.out.print(arr[i]+",");
        }
        
        System.out.println("");
        System.out.println("------------------------------------------------");
        System.out.println("随机化选择第 index 小的元素");
        
        /**
         * 随机化选择第 index 小的元素
         */
        int[] arr2 ={48,6,57,88,60,42,83,73,49,85,99,1424,35,242,6567,34,2,5};

        for(int i=0;i<arr2.length;i++){
            int indexMin=RandomizedSelect.randomizedSelect(arr2, 0, arr2.length-1, i+1);
            System.out.println("top "+(i+1)+" is "+indexMin+".");
        }

        System.out.println("------------------------------------------------");
        System.out.println("最坏情况运行时间为线性的选择第 index 小的元素");

        /**
         * 最坏情况运行时间为线性的选择第 index 小的元素
         */
        int[] arr3 ={7,9,8,6,3,5,2,4,1
                ,18,10,15,17,10,12,19,14,13
                ,34,58,79,21,16,53,23,22,11
                ,23,48,29,16,55,37,28,51,50
                ,22,18,27,35,53,27,96,88,101};
        for(int i=0;i<arr3.length;i++){
            Select select=new Select();
            int indexMin=select.qSelect(arr3, 0, arr3.length-1, i+1);
            System.out.println("top "+(i+1)+" is "+indexMin+".");
        }

    }

控制台打印

------------------------------------------------
随机化选快排的运算过程
random_index=4
random_index=1
random_index=3
random_index=2
random_index=2
random_index=8
random_index=8
6,42,48,49,57,60,73,83,85,88
------------------------------------------------
随机化选择第 index 小的元素
top 1 is 2.
top 2 is 5.
top 3 is 6.
top 4 is 34.
top 5 is 35.
top 6 is 42.
top 7 is 48.
top 8 is 49.
top 9 is 57.
top 10 is 60.
top 11 is 73.
top 12 is 83.
top 13 is 85.
top 14 is 88.
top 15 is 99.
top 16 is 242.
top 17 is 1424.
top 18 is 6567.
------------------------------------------------
最坏情况运行时间为线性的选择第 index 小的元素
top 1 is 1.
top 2 is 2.
top 3 is 3.
top 4 is 4.
top 5 is 5.
top 6 is 6.
top 7 is 7.
top 8 is 8.
top 9 is 9.
top 10 is 10.
top 11 is 10.
top 12 is 11.
top 13 is 12.
top 14 is 13.
top 15 is 14.
top 16 is 15.
top 17 is 16.
top 18 is 16.
top 19 is 17.
top 20 is 18.
top 21 is 18.
top 22 is 19.
top 23 is 21.
top 24 is 22.
top 25 is 22.
top 26 is 23.
top 27 is 23.
top 28 is 27.
top 29 is 27.
top 30 is 28.
top 31 is 29.
top 32 is 34.
top 33 is 35.
top 34 is 37.
top 35 is 48.
top 36 is 50.
top 37 is 51.
top 38 is 53.
top 39 is 53.
top 40 is 55.
top 41 is 58.
top 42 is 79.
top 43 is 88.
top 44 is 96.
top 45 is 101.

算法系列文章,因为水平所限,只做记录,不做过多介绍。

以上,谢谢阅读,希望你有所收获!

以上,谢谢阅读,希望你有所收获!

算法导论公开课笔记(一)算法分析与设计
算法导论公开课笔记(二)快速排序和随机化算法
算法导论公开课笔记(三)线性时间排序
算法导论公开课笔记(四)顺序统计、中值
动态规划算法

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

推荐阅读更多精彩内容