~米漿牛奶~

之前參加地特考試，程式考題中有一題探討第k大數字的問題。

當時腦中馬上浮現選擇排序法(Selection Sort)，但是題目想要有O(n)效率。

所以這故事告訴我們，選擇排序法的O(n^2)效率其實不大好，希望能改善。((瞬間想翻桌

因此自己寫出兩個方法，使用同樣的陣列，以最後一個為max，每過一回都減少陣列範圍。

以下參考書為：2015資料結構 by 王致強

結果圖：

程式碼：

import java.util.Scanner;

public class Selection
{        
    String SelectionK(int s[],int k)
    {
        //題目要求O(n)的時間複雜度
        int max=0,count=0,temp;
        String ans;
        if(s.length<k){return "k值過大!";}
        else if(k==0){return "k值不能零!";}        
        else 
        {
            for (int i=1;i<=k;i++)
            {    
                max=s[s.length-i];//隨i值增加,max重新取得縮小的陣列範圍最後一個
                for (int j=0;j<s.length-i;j++)//隨i值增加,j的最大值會減少,也就是說比的陣列範圍會縮小
                {
                    if(max<s[j]){temp=s[j];s[j]=max;max=temp;}//有比max大就交換
                    count+=1;//計算效率
                }
                s[s.length-i]=max;//每比出的最大值存入最後一個
                //System.out.println("第"+i+"大為"+max);//顯示過程
                
            }
            System.out.println("第k大數字效率為"+count);//顯示效率
            //s陣列存入數與k影響效率為
            //n=1 效率0, n=2 效率1~1, n=3 效率2~3, n=4 效率3~6, n=5 效率4~10        
            ans="第"+k+"大為"+max;
            return ans;
        }
    }    
    void SelectionSort(int a[])
    {
        //Selection Sort的時間複雜度
        int max=0,count=0,temp;
        for (int i=a.length-1;i>0;i--)
        {                
            max=a[i];//隨i值減少,max重新取得縮小的陣列範圍最後一個
            for (int j=0;j<i;j++)//隨i值減少,j的最大值會減少,也就是說比的陣列範圍會縮小
            {
                if(max<a[j]){temp=a[j];a[j]=max;max=temp;}//有比max大就交換
                count+=1;//計算效率        
            }
            a[i]=max;//每比出的最大值存入最後一個
        }
        System.out.println("選擇排序法效率為"+count);//顯示效率
        //a陣列存入數影響效率為
        //n=1 效率0, n=2 效率1, n=3 效率3, n=4 效率6, n=5 效率10
    }
   public static void main(String args[])
   {    
        int s[] = {5,4,3,2,1};//第k大數字的陣列
        int a[] = {5,4,3,2,1};//選擇排序法的陣列
        System.out.print("第k大數字陣列：");
        for (int i=0;i<s.length;i++){System.out.print(s[i]+" ");}//顯示原本陣列
        System.out.println();
        System.out.print("選擇排序法陣列：");
        for (int j=0;j<a.length;j++){System.out.print(a[j]+" ");}//顯示原本陣列
        System.out.println();
        System.out.print("請輸入k值：");
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        System.out.println("輸入k值："+k); 
        Selection text = new Selection();
        System.out.println(text.SelectionK(s,k));
        text.SelectionSort(a);
        System.out.print("第k大數字陣列："); 
        for (int x=0;x<s.length;x++){System.out.print(s[x]+" ");}//顯示重整陣列
        System.out.println();
        System.out.print("選擇排序法陣列："); 
        for (int y=0;y<a.length;y++){System.out.print(a[y]+" ");}//顯示重整陣列
   }
}

SelectionK簡單流程如下：

如果k不等於0且k不大於陣列長度，就能進入雙迴圈。

第一個迴圈範圍為1~k，設max為s[陣列長-第一個迴圈值]，接著再入第二個迴圈。

第二個迴圈範圍為0~(陣列長-第一個迴圈值-1)，如果max小於s[j]就交換，count加一次，等第二個迴圈做完s[陣列長-第一個迴圈值]設為max。

執行完雙迴圈，最後顯示效率與第k大數字。

以n=5,k=1效率為  4(i=1)=4次 

以n=5,k=5效率為  4(i=1)+3(i=2)+2(i=3)+1(i=4)=10次

SelectionSort簡單流程如下：

直接進入雙迴圈，不需要管k值。

第一個迴圈範圍為(陣列長-1)~1，設max為a[i]，接著再入第二個迴圈。

第二個迴圈範圍為0~(第一個迴圈值-1)，如果max小於a[j]就交換，count加一次，等第二個迴圈做完a[i]設為max。

執行完雙迴圈，最後顯示效率。

以n=5效率為  4(i=4)+3(i=3)+2(i=2)+1(i=1)=10次

結論：

雖然兩者在最糟情況都10次，不過第k大數字最佳只有n-1次，運作原理跟"找出最大值"同樣的時間複雜度。

而且當k=陣列長，剛好把數字從小排到大，運作原理跟"選擇排序法"同樣的時間複雜度。

第k大數字能接受使用者點菜(啥)、顯示第k大、時間複雜度n-1~n^2、從小排到大等等這麼多好處，我們乾脆忘了選擇排序法。((遭毆

其實題目要用c++寫，但個人私心用java寫。