選擇排序就是對數(shù)組進行掃描，每次掃描找出最小的元素，并將其提到元素的前面。

動圖

http://www.sorting-algorithms.com/animation/20/random-initial-order/selection-sort.gif

代碼

public?class?Selection { ????public?static?void?sort(Comparable[] li) { ????????for(int?i =?0; i < li.length; i++) { ????????????int?min = i; ????????????for(int?j = i+1; j < li.length; j++) { ????????????????if(SortUtil.less(li[j], li[min])) { ????????????????????min = j; ????????????????} ????????????} ????????????SortUtil.exch(li, min, i); ????????} ????} }

第6行：注意j=i+1。由于已經(jīng)將i賦值給min了。不是必需再將li[i]與li[j]比較。

命題

選擇排序使用了約N^2/2次比較。使用了N次交換。

長處

排序算法的執(zhí)行時間和輸入無關(guān)，都是N^2復(fù)雜度。

數(shù)據(jù)的交換次數(shù)是最少的，都是N次交換。

總結(jié)

以上是生活随笔為你收集整理的普林斯顿公开课 算法2-2：选择排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。