Java 十大排序算法之選擇排序刨析

Posted on by

選擇排序原理

①假設第一個索引處的元素為最小值，和其他值進行比較，如果當前的索引處的元素大於其他某個索引處的值，則假定其他某個索引處的值為最小值，最後找到最小值所在的索引

②交換第一個索引處和最小值所在的索引處的值

選擇排序API設計

類名 Selection
構造方法 Selection():創建Selection對象
成員方法

1.public static void sort(Comparable[] a):對數組內的元素進行排序

2.private static boolean greater(Comparable v,Comparable w):判斷v是否大於w

3.private static void exchange(Comparable[] a,int i,int j):交換a數組中，索引i和索引j處的值

選擇排序代碼實現

public class Selection {
    //對數組a中的元素進行排序
    public static void sort(Comparable[] a){
        for(int i=0;i<a.length-2;i++){
            int minIndex=i;
            for(int j=i+1;j<a.length;j++){
                if(greater(a[minIndex],a[j])){
                    minIndex=j;
                }
            }
            exchange(a,i,minIndex);
        }
    }
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    private static void exchange(Comparable[] a,int i,int j ){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
class Test{
    public static void main(String[] args) {
        Integer[] a={4,6,8,7,9,2,10,1};
        Selection.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

選擇排序的時間復雜度

選擇排序使用瞭雙層for循環，外層循環完成瞭數據交換，內層循環完成瞭數據比較，所以分別統計：數據比較次數：(N-1)+(N-2)+(N-3)+…+2+1=

\frac{}{}

((N-1)+1)*(N-1)/2=N^2/2-N/2;

數據交換次數：N-1；

時間復雜度： N^2/2-N/2+(N-1)=N^2/2+N/2-1;

根據大O推導法則，保留最高階項，去除常數因子，時間復雜度為O（N^2）

到此這篇關於Java 十大排序算法之選擇排序刨析的文章就介紹到這瞭,更多相關Java 選擇排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：