Java 十大排序算法之選擇排序刨析
選擇排序原理
①假設(shè)第一個索引處的元素為最小值，和其他值進行比較，如果當(dāng)前的索引處的元素大于其他某個索引處的值，則假定其他某個索引處的值為最小值，最后找到最小值所在的索引
②交換第一個索引處和最小值所在的索引處的值
選擇排序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=
((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)文章希望大家以后多多支持腳本之家！
- Java基礎(chǔ)之選擇結(jié)構(gòu)與循環(huán)結(jié)構(gòu)
- Java程序流程控制：判斷結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)原理與用法實例分析
- Java流程控制之循環(huán)結(jié)構(gòu)for,增強for循環(huán)
- Java流程控制之循環(huán)結(jié)構(gòu)while、do...while
- java循環(huán)結(jié)構(gòu)、數(shù)組的使用小結(jié)
- Java流程控制之選擇結(jié)構(gòu)
- java 排序算法之選擇排序
- Java選擇結(jié)構(gòu)與循環(huán)結(jié)構(gòu)的使用詳解
相關(guān)文章
這篇文章主要介紹了Java System類用法,結(jié)合具體實例形式分析了java使用System類獲取系統(tǒng)環(huán)境變量信息相關(guān)操作技巧,需要的朋友可以參考下2019-07-07
SpringBoot集成Druid實現(xiàn)多數(shù)據(jù)源的兩種方式
這篇文章主要介紹了SpringBoot集成Druid實現(xiàn)多數(shù)據(jù)源的兩種方式,集成com.baomidou的方式和基于AOP手動實現(xiàn)多數(shù)據(jù)源原生的方式,文中通過代碼示例講解的非常詳細,需要的朋友可以參考下2024-03-03
這篇文章主要介紹了用Java程序模擬實現(xiàn)新冠病毒傳染效果，本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-08-08
Java中的HashTable是一種線程安全的哈希表實現(xiàn),它可以高效地存儲和快速查找數(shù)據(jù),本文將介紹Java中的HashTable的實現(xiàn)原理、常用方法和測試用例,需要的小伙伴可以參考一下2023-09-09
這篇文章主要介紹了Java精確計算BigDecimal類的使用方法，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-12-12
這篇文章主要介紹了Java中的CountDownLatch使用解析,CountDownLatch初始化的時候必須指定一個count,await方法會一直阻塞直到調(diào)用countdown方法,count為0,當(dāng)count為0時,所有的等待線程都會被釋放,需要的朋友可以參考下2023-12-12
在本文中，我們將看到什么是 Java 枚舉，它們解決了哪些問題以及如何在實踐中使用 Java 枚舉實現(xiàn)一些設(shè)計模式。下面小編將為大家詳細介紹2021-09-09
SpringBoot整合Redis實現(xiàn)token緩存
于token通常會被多次使用,我們需要把它保存到緩存中,以減少頻繁地訪問數(shù)據(jù)庫,本文主要介紹了SpringBoot整合Redis實現(xiàn)token緩存,感興趣的可以了解一下2024-02-02
java socket接收保證能讀完數(shù)據(jù)的實例
這篇文章主要介紹了java socket接收保證能讀完數(shù)據(jù)的實例，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-10-10
這篇文章主要介紹了SpringBoot項目整合Redis教程詳解，Redis?是完全開源的，遵守?BSD?協(xié)議，是一個高性能的?key-value?數(shù)據(jù)庫。感興趣的小伙伴可以參考閱讀本文2023-03-03