算法導(dǎo)論公開(kāi)課筆記（四）順序統(tǒng)計(jì)、中值

順序統(tǒng)計(jì)

問(wèn)題場(chǎng)景：給定具有n個(gè)元素的數(shù)組，已知數(shù)組是無(wú)序的，請(qǐng)找到第k小的元素并返回該元素（TOP K問(wèn)題）。
根據(jù)之前所學(xué)的算法我們可以得出一個(gè)原始方案：
使用運(yùn)行時(shí)間為Θ (nlgn)的排序算法（堆排序、歸并排序）進(jìn)行排序后返回?cái)?shù)組索引為K的元素。
該問(wèn)題當(dāng)K為如下特殊值的時(shí)候的情形：

  • K=1 : 最小值
  • K=n : 最大值

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


    k值表示的不同意義

隨機(jī)化分治法

  • 隨機(jī)化選擇法

用到了前面講的隨機(jī)化快速排序的子操作randomizedPartition。

方法的大致運(yùn)行流程是這樣的：
如果開(kāi)始位置和結(jié)束位置一樣時(shí)算法視為找到，返回開(kāi)始位置的元素；否則進(jìn)行隨機(jī)化分割，當(dāng)分割后的主元位置和需要查找的第index小的位置對(duì)應(yīng)時(shí)視為找到，當(dāng)前主元就是需要查找的元素。否則，將問(wèn)題劃分為更小規(guī)模的問(wèn)題，如果主元位置p>index那么在[left,p]范圍內(nèi)的數(shù)據(jù)進(jìn)行隨機(jī)化選擇操作；否則從主元的右側(cè)進(jìn)行隨機(jī)話選擇操作。方法介紹完畢，需要注意的是不同的分割導(dǎo)致index的變化是一個(gè)需要關(guān)注的點(diǎn)。

    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};
 *             
 *             ------------------------------------------------
 *             隨機(jī)化選擇第 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 隨機(jī)化的選擇算法，用于求解top k 問(wèn)題
 **/
public class RandomizedSelect {
    
    /**
     * @return 隨機(jī)化主元分割點(diǎn)位置
     * 
     * @param src
     *            待劃分的數(shù)組，分割后的結(jié)果保證，mid前的元素都是小于等于它的，右側(cè)的元素都是大于等于它的
     * @param left
     *            左邊界
     * @param right
     *            右邊界   
     */
    private static int randomizedPartition(int[] src, int left, int right) {

        /*隨機(jī)選取主元元素*/
        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];// 挖坑填數(shù)
            }

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

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

        // 這種情況下第一趟結(jié)束 i的坐標(biāo)都比他小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];//待分割的邊界到只有一個(gè)元素時(shí)，該元素作為結(jié)果返回
        
        int mid =randomizedPartition(src, left, right);//隨機(jī)化分割后，主元所在位置
        
        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問(wèn)題分解成top i-key
        
    }

}

該算法的最壞情況的運(yùn)行時(shí)間是Θ(n2);期望運(yùn)行時(shí)間為Θ（n）。

雖然，隨機(jī)化選擇算法的期望運(yùn)行時(shí)間是線性的，但是出現(xiàn)最壞的情況的話效率很低，盡管出現(xiàn)最壞的情況的概率是極其低的。

最終人類還是創(chuàng)造出最壞情況為線性的選擇算法。

最壞情況為線性的選擇算法

選擇算法概述

該算法是對(duì)隨機(jī)化選擇主元的優(yōu)化版本，最壞情況的運(yùn)行時(shí)間是線性的即O(n)。和隨機(jī)化的選擇排序一樣，快速選擇算法通過(guò)對(duì)輸入數(shù)組的遞歸劃分找出所需的元素，但是該算法那能給個(gè)保證得到對(duì)數(shù)組的一個(gè)好的劃分?？焖龠x擇算法使用的也是來(lái)自快速排序的確定性劃分算法PARTITION,做了部分修改，將劃分的主元也作為輸入?yún)?shù)。
代碼如下：

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}
 *             
 *             ------------------------------------------------
 *             最壞情況運(yùn)行時(shí)間為線性的選擇第 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 問(wèn)題
 **/
public class Select {
    
     int[] midianArray;//中位數(shù)數(shù)組

    
    /**
     * @return 隨機(jī)化主元分割點(diǎn)位置
     * 
     * @param src
     *            待劃分的數(shù)組，分割后的結(jié)果保證，mid前的元素都是小于等于它的，右側(cè)的元素都是大于等于它的
     * @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];// 挖坑填數(shù)
            }

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

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

        // 這種情況下第一趟結(jié)束 i的坐標(biāo)都比他小i的右邊都比他大
        return i;

    }
    
    
    /**
     *  最壞情況運(yùn)行時(shí)間為線性的選擇排序算法的入口方法
     * @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.尋找中位數(shù)的中位數(shù)
         * 2.進(jìn)行遞歸找到第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);//根據(jù)主元進(jìn)行劃分，返回主元?jiǎng)澐趾蟮奈恢?        
        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問(wèn)題分解成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];//范圍內(nèi)只有一個(gè)元素時(shí)，該元素作為結(jié)果返回

        /**
         * 1.元素分組：將輸入數(shù)組中的n個(gè)元素劃分為【n/5】個(gè)中位數(shù)，且至多只有一組由剩下的n mod 5個(gè)元素組成。
         * 2.尋找【n/5】個(gè)中位數(shù)：首先對(duì)沒(méi)組元素進(jìn)行插入排序，然后確定每組元素的中位數(shù)。
         * 3.找到中位數(shù)：找出中位數(shù)的中位數(shù)。
         */
        
        //1.元素分組
        //2.尋找【n/5】個(gè)中位數(shù)
        int index;
        for(index=left;index<right-5;index+=5){//分組整除部分的數(shù)據(jù)
            insertSort(src,index,4);
            int num=index - left;
            midianArray[num/5]=src[index+2];//中位數(shù)賦值
        }
        //分組余下的元素
        int remainNum=right-index+1;
        if(remainNum>0){
            insertSort(src,index,remainNum-1);
            int num=index - left;
            midianArray[num/5]=src[index+remainNum/2];//中位數(shù)賦值
        }
        //3. 遞歸找到中位數(shù)的中位數(shù)
        int elemAuxArray=(right-left)/5-1;
        if((right-left)%5!=0) elemAuxArray++;
        
        if(elemAuxArray==0) 
            return midianArray[elemAuxArray];
        else                
            return findMedian(midianArray,0,elemAuxArray);
    }


    /**
     * 子數(shù)組插入排序
     * @param src 母數(shù)組
     * @param left 開(kāi)始為止
     * @param loopLength 步長(zhǎng)
     */
    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;
        }
    }

}

測(cè)試代碼如下：

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("隨機(jī)化選快排的運(yùn)算過(guò)程");

        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("隨機(jī)化選擇第 index 小的元素");
        
        /**
         * 隨機(jī)化選擇第 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("最壞情況運(yùn)行時(shí)間為線性的選擇第 index 小的元素");

        /**
         * 最壞情況運(yùn)行時(shí)間為線性的選擇第 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+".");
        }

    }

控制臺(tái)打印

------------------------------------------------
隨機(jī)化選快排的運(yùn)算過(guò)程
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
------------------------------------------------
隨機(jī)化選擇第 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.
------------------------------------------------
最壞情況運(yùn)行時(shí)間為線性的選擇第 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.

算法系列文章，因?yàn)樗剿?，只做記錄，不做過(guò)多介紹。

以上，謝謝閱讀，希望你有所收獲！

以上，謝謝閱讀，希望你有所收獲！

算法導(dǎo)論公開(kāi)課筆記（一）算法分析與設(shè)計(jì)
算法導(dǎo)論公開(kāi)課筆記（二）快速排序和隨機(jī)化算法
算法導(dǎo)論公開(kāi)課筆記（三）線性時(shí)間排序
算法導(dǎo)論公開(kāi)課筆記（四）順序統(tǒng)計(jì)、中值
動(dòng)態(tài)規(guī)劃算法

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容