JAVA十大排序算法之選擇排序詳解
選擇排序
1.找到數(shù)組中最大(或最?。┑脑?/p>
2.將它和數(shù)組的第一個(gè)元素交換位置(如果第一個(gè)元素就是最大(?。┰啬敲此秃妥约航粨Q)
3.在剩下的元素中找到最大(?。┑脑?,將它與數(shù)組的第二個(gè)元素交換位置。如此往復(fù),直到將整個(gè)數(shù)組排序。
代碼實(shí)現(xiàn)
對(duì)下面數(shù)組實(shí)現(xiàn)排序:{87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9}
動(dòng)圖演示
代碼實(shí)現(xiàn)
public class SelectionSort { public static final int[] ARRAY = {87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9}; public static int[] sort(int[] array) { if (array.length == 0) { return array; } for (int i = 0; i < array.length; i++) { //最小數(shù)的下標(biāo),每個(gè)循環(huán)開始總是假設(shè)第一個(gè)數(shù)最小 int minIndex = i; for (int j = i; j < array.length; j++) { //找到最小索引 if (array[j] < array[minIndex]) { //保存最小索引 minIndex = j; } } //最小索引的值 int temp = array[minIndex]; array[minIndex] = array[i]; array[i] = temp; } return array; } public static void print(int[] array) { for (int i : array) { System.out.print(i + " "); } System.out.println(""); } public static void main(String[] args) { print(ARRAY); System.out.println("============================================"); print(sort(ARRAY)); } }
時(shí)間復(fù)雜度
很明顯,和冒泡排序相比,在查找最?。ɑ蜃畲螅┰氐乃饕?,比較次數(shù)仍然保持為O(n2)
,但元素交換次數(shù)為O(n)。
算法穩(wěn)定性
選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的,比如給第一個(gè)位置選擇最小的,在剩余元素里面給第二個(gè)元素選擇第二小的,依次類推,直到第n-1個(gè)元素,第n個(gè)元素不用選擇了,因?yàn)橹皇O滤粋€(gè)最大的元素了。那么,在一趟選擇,如果一個(gè)元素比當(dāng)前元素小,而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面,那么交換后穩(wěn)定性就被破壞了。舉個(gè)例子,數(shù)組5,8,5,2,9,我們知道第一遍選擇第1個(gè)元素5會(huì)和2交換,那么原序列中兩個(gè)5的相對(duì)前后順序就被破壞了,所以選擇排序是一個(gè)不穩(wěn)定的排序算法。
總結(jié)
本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
詳解如何在項(xiàng)目中應(yīng)用SpringSecurity權(quán)限控制
本文主要介紹了如何在項(xiàng)目中應(yīng)用SpringSecurity權(quán)限控制,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06springboot實(shí)現(xiàn)全局異常捕獲的使用示例
任何系統(tǒng),我們不會(huì)傻傻的在每一個(gè)地方進(jìn)行異常捕獲和處理,整個(gè)系統(tǒng)一般我們會(huì)在一個(gè)的地方統(tǒng)一進(jìn)行異常處理,本文主要介紹了springboot實(shí)現(xiàn)全局異常捕獲的使用示例,感興趣的可以了解一下2023-11-11Java Email郵件發(fā)送簡(jiǎn)單實(shí)現(xiàn)介紹
電子郵件從用戶電腦的郵件軟件,例如Outlook,發(fā)送到郵件服務(wù)器上,可能經(jīng)過若干個(gè)郵件服務(wù)器的中轉(zhuǎn),最終到達(dá)對(duì)方郵件服務(wù)器上,收件方就可以用軟件接收郵件2022-11-11