選擇排序：（Selection sort）是一種簡(jiǎn)單直觀的排序算法，也是一種不穩(wěn)定的排序方法。

選擇排序的原理

一組無(wú)序待排數(shù)組，做升序排序，我們先假定第一個(gè)位置上的數(shù)據(jù)就是最小的，我們用一個(gè)參數(shù)記錄這個(gè)最小的數(shù)，然后依次把后面的每個(gè)位置的數(shù)據(jù)和這個(gè)最小的比較，如果比這個(gè)數(shù)小就替換兩個(gè)位置數(shù)據(jù)，等到第一輪比較完成就能確定最小的數(shù)據(jù)排在第一位了，然后第二輪從第二個(gè)位置開(kāi)始，相同的方式比較，每次都能找到本輪最小的值，直至全部待排元素個(gè)數(shù)為0的時(shí)候，數(shù)組就排好順序了。

選擇排序流程圖

我們來(lái)進(jìn)行詳細(xì)解析看看

首先我們給個(gè)無(wú)序數(shù)組[4,6,15,9,12,3,32]進(jìn)行升序排序，因?yàn)樾枰_定每個(gè)數(shù)組的長(zhǎng)度，所以需要比較數(shù)組長(zhǎng)度-1輪，當(dāng)前面的元素都排好了之后，那么數(shù)組最后一個(gè)元素自然就確定了位置。

我們定義兩個(gè)值，minIndex，minNum用來(lái)分別表示每一輪的找到的最小值的下標(biāo)和值，后面未排序的值都和minNum比較，從而找出每一輪的最小值。

第一輪我們以下標(biāo)為1的第一位作為標(biāo)志位（也就是把第一個(gè)值當(dāng)做最小值），那么此時(shí)minIndex=0，minNum=4，經(jīng)過(guò)和 minNum 比較發(fā)現(xiàn)后面只有3比4小，那么3和4交換位置，minIndex=5，minNum=3，把4換到下標(biāo)為5的位置，如下圖所示：

第一輪我們得到的結(jié)果是[3,6,15,9,12,4,32]，本輪最小數(shù)是：3，所以3放到本輪標(biāo)志位，也就是第一位

第二輪：拿到第一輪排序的值作為初始值[3,6,15,9,12,4,32]，同第一輪一樣，此時(shí)6作為標(biāo)志位minNum=6，minNum和其他比較，只有4比6小，需要交換位置，如下圖所示

第二輪排序結(jié)果[3,4,15,9,12,6,32]，本輪最小數(shù)是：4

第三輪：初始值[3,4,15,9,12,6,32],這次標(biāo)志位15，minNum=15，minIndex=2，minNum先比和9比較，發(fā)現(xiàn)9比15小，minNum=9，minIndex=3，然后minNum和12比較，不需要替換minNum，再和6比較，minNum=6，minIndex=5,后面再比較已經(jīng)沒(méi)有比6小了，那么本輪就是初始標(biāo)志位15和下標(biāo)為5，值為6的數(shù)據(jù)換位置。

第三輪排序結(jié)果[3,4,6,9,12,15,32]，本輪最小數(shù)是：6

第四、五、六輪：初始值[3,4,6,9,12,15,32]，經(jīng)過(guò)前面的比較我們可以看到數(shù)組已經(jīng)排序完成，但是程序并不知道，會(huì)繼續(xù)比較下去，把下標(biāo)為4、5、6位置都作為標(biāo)志位比較一次，發(fā)現(xiàn)都不需要變動(dòng)位置，那么最終執(zhí)行完成之后就能排序完成

第四、五、六輪排序結(jié)果[3,4,6,9,12,15,32]

到這，我們已經(jīng)清楚了每個(gè)步驟做了什么，那么接下來(lái)上代碼驗(yàn)證一下：

Java代碼實(shí)現(xiàn)

?public?class?selectionSort?{
?????public?static?void?main(String[]?args){
??????????int[]?arr?=?new?int[]{4,6,15,9,12,3,32};
?????????for(int?i=0;i<arr.length-1;i++){//每次循環(huán)都會(huì)找出最小的數(shù)
?????????????//記錄最小數(shù)的下標(biāo)
?????????????int?minIndex?=?i;
?????????????//記錄最小數(shù)
?????????????int?minNum?=?arr[i];
?????????????//每次循環(huán)都會(huì)找出最小的數(shù)
?????????????for(int?j=i+1;j<arr.length;j++){
?????????????????if(arr[j]<minNum){//如果當(dāng)前數(shù)比最小數(shù)小，則更新最小數(shù)
?????????????????????minNum?=?arr[j];//更新最小數(shù)
?????????????????????minIndex?=?j;//更新最小數(shù)的下標(biāo)
?????????????????}
?????????????}
?????????????//將最開(kāi)始假定的小的數(shù)移動(dòng)到真實(shí)最小的位置
?????????????arr[minIndex]=arr[i];
?????????????arr[i]=minNum;//將標(biāo)志位放到最小數(shù)原來(lái)所在的位置
?????????????
?????????????//打印結(jié)果，方便查看
?????????????System.out.print("第"+(i+1)+"輪[");
?????????????for(int?a=0;a<arr.length;a++){
?????????????????System.out.print(arr[a]+"\t");
?????????????}
?????????????System.out.println?("]，本輪最小數(shù)是："+minNum);
?????????}
?????????System.out.print("最終結(jié)果[");
?????????for(int?i=0;i<arr.length;i++){
?????????????System.out.print(arr[i]+"\t");
?????????}
?????????System.out.println("]");
?????}
?}

輸出結(jié)果

  第1輪[3 6 15 9 12 4 32 ]，本輪最小數(shù)是：3
  第2輪[3 4 15 9 12 6 32 ]，本輪最小數(shù)是：4
  第3輪[3 4 6 9 12 15 32 ]，本輪最小數(shù)是：6
  第4輪[3 4 6 9 12 15 32 ]，本輪最小數(shù)是：9
  第5輪[3 4 6 9 12 15 32 ]，本輪最小數(shù)是：12
  第6輪[3 4 6 9 12 15 32 ]，本輪最小數(shù)是：15
  最終結(jié)果[3 4 6 9 12 15 32 ]

時(shí)間復(fù)雜度

我們通過(guò)上面的細(xì)節(jié)拆分發(fā)現(xiàn)，無(wú)論是否是已經(jīng)排好的還是沒(méi)排好的情況，我們都需要每個(gè)數(shù)字都比較到，那么就出現(xiàn)N個(gè)元素的數(shù)組，第一輪是n次比較，第二輪是從第二個(gè)位置開(kāi)始，那么就是n-1，第三輪就是n-2次... 最后是1，那么就出現(xiàn)了n+(n-1)+(n-2)+(n-3)...1,這是一個(gè)等差數(shù)列，求和為一個(gè)二次型多項(xiàng)式，因?yàn)榈炔顢?shù)列求和會(huì)出現(xiàn)二次型；我們?nèi)∽罡唠A就是n^2,所以時(shí)間復(fù)雜度就是O(n^2),而且最好和最壞的情況時(shí)間復(fù)雜度都是O(n^2)

到此這篇關(guān)于一文帶你了解Java選擇排序的原理與實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java選擇排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論