快捷導(dǎo)航

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

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

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

選擇排序原理

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

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

選擇排序API設(shè)計(jì)

類名

Selection

構(gòu)造方法

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

成員方法

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

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處的值

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

public class Selection {
    //對(duì)數(shù)組a中的元素進(jìn)行排序
    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));
    }
}

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

選擇排序使用了雙層for循環(huán)，外層循環(huán)完成了數(shù)據(jù)交換，內(nèi)層循環(huán)完成了數(shù)據(jù)比較，所以分別統(tǒng)計(jì)：數(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；

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

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

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

您可能感興趣的文章:

相關(guān)文章

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