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

更新時間：2021年11月18日 09:42:12 作者：龍弟-idea

選擇排序是一種簡單直觀的排序算法，無論什么數(shù)據(jù)進去都是 O(n²) 的時間復(fù)雜度。所以用到它的時候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧

選擇排序原理

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

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

選擇排序API設(shè)計

類名

Selection

構(gòu)造方法

Selection():創(chuàng)建Selection對象

成員方法

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

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

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

選擇排序代碼實現(xiàn)

public class Selection {
    //對數(shù)組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));
    }
}

選擇排序的時間復(fù)雜度

選擇排序使用了雙層for循環(huán)，外層循環(huán)完成了數(shù)據(jù)交換，內(nèi)層循環(huán)完成了數(shù)據(jù)比較，所以分別統(tǒng)計：數(shù)據(jù)比較次數(shù)：(N-1)+(N-2)+(N-3)+...+2+1=

$\frac{}{}$

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

數(shù)據(jù)交換次數(shù)：N-1；

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

根據(jù)大O推導(dǎo)法則，保留最高階項，去除常數(shù)因子，時間復(fù)雜度為O（N^2）

到此這篇關(guān)于Java 十大排序算法之選擇排序刨析的文章就介紹到這了,更多相關(guān)Java 選擇排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

相關(guān)文章

如何使用JAVA調(diào)用SHELL
這篇文章主要介紹了如何使用JAVA調(diào)用SHELL，文中講解非常細致，代碼幫助大家更好的理解和學(xué)習，感興趣的朋友可以了解下
2020-06-06
Java Volatile關(guān)鍵字實現(xiàn)原理過程解析
這篇文章主要介紹了Java Volatile關(guān)鍵字實現(xiàn)原理過程解析,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習或者工作具有一定的參考學(xué)習價值,需要的朋友可以參考下
2020-03-03
JAVA中的動態(tài)代理使用詳解
這篇文章主要介紹了JAVA中的動態(tài)代理使用詳解,動態(tài)代理提供了一種靈活且非侵入式的方式,可以對對象的行為進行定制和擴展,它在代碼重用、解耦和業(yè)務(wù)邏輯分離、性能優(yōu)化以及系統(tǒng)架構(gòu)中起到了重要的作用,,需要的朋友可以參考下
2023-08-08
springBoot項目中使用@Value取值出現(xiàn)的問題及解決
這篇文章主要介紹了springBoot項目中使用@Value取值出現(xiàn)的問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2022-07-07
SpringBoot+MyBatis-Plus實現(xiàn)分頁功能
在SpringBoot項目中,結(jié)合MyBatis-Plus（簡稱MP）可以非常方便地實現(xiàn)分頁功能,MP為開發(fā)者提供了分頁插件PaginationInterceptor,只需簡單配置即可使用,本文給大家介紹了SpringBoot+MyBatis-Plus實現(xiàn)分頁功能,文中通過代碼示例給大家介紹的非常詳細,需要的朋友可以參考下
2024-01-01
spring整合redis消息監(jiān)聽通知使用的實現(xiàn)示例
在電商系統(tǒng)中，秒殺，搶購，紅包優(yōu)惠卷等操作，一般都會設(shè)置時間限制，本文主要介紹了spring整合redis消息監(jiān)聽通知使用，具有一定的參考價值，感興趣的可以了解一下
2021-12-12
總結(jié)一些Java常用的加密算法
今天給大家?guī)淼氖顷P(guān)于Java的相關(guān)知識,文章圍繞著Java加密算法展開,文中有非常詳細的介紹及代碼示例,需要的朋友可以參考下
2021-06-06
Java結(jié)構(gòu)型模式之橋接模式詳解
橋接模式是一種很實用的結(jié)構(gòu)型模式，如果系統(tǒng)中某個類存在兩個獨立變化的維度，通過橋接模式將這兩個維度分離出來，使兩者可以獨立擴展
2023-02-02
Java查看線程運行狀態(tài)的方法詳解
這篇文章主要為大家詳細介紹了Java語言如何查看線程運行狀態(tài)的方法，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學(xué)習一下
2022-08-08
springBoot無法解析yml問題
這篇文章主要介紹了springBoot無法解析yml問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2024-06-06