北大青鳥(niǎo)北京,北大青鳥(niǎo)學(xué)校學(xué)術(shù)部:Java的排序之“選擇排序”

北大青鳥(niǎo)北京,北大青鳥(niǎo)學(xué)校學(xué)術(shù)部老師講解:什么是選擇排序?

北大青鳥(niǎo)北京北大青鳥(niǎo)學(xué)校解答:選擇排序是常用內(nèi)部排序的一種,常見(jiàn)的實(shí)現(xiàn)算法有直接選擇排序算法和堆排序算法,選擇排序的基本思想是每次從待排數(shù)據(jù)中選擇第n小的數(shù)據(jù)放到排序列表的第n個(gè)位置,假如共有N個(gè)數(shù)據(jù)待排,那么經(jīng)過(guò)N-1次排序后,待排數(shù)據(jù)就已經(jīng)按照從小到大的順序排列了。

  直接選擇排序算法的思想比較簡(jiǎn)單:(假設(shè)數(shù)據(jù)放在一個(gè)數(shù)組a中,且數(shù)組的長(zhǎng)度是N)

  1:從a[0]-a[N-1]中選出最小的數(shù)據(jù),然后與a[0]交換位置

  2:從a[1]-a[N-1]中選出最小的數(shù)據(jù),然后與a[1]交換位置(第1步結(jié)束后a[0]就是N個(gè)數(shù)的最小值)

  3:從a[2]-a[N-1]中選出最小的數(shù)據(jù),然后與a[2]交換位置(第2步結(jié)束后a[1]就是N-1個(gè)數(shù)的最小值)

  以此類推,N-1次排序后,待排數(shù)據(jù)就已經(jīng)按照從小到大的順序排列了。

  直接選擇排序的java實(shí)現(xiàn)如下:(北京北大青鳥(niǎo)學(xué)校)

view sourceprint?01 public static void selectionSort(int[] elements){ 

02         for(int i = 0; i < elements.length-1; ++i){ 

03             int k = i; 

04             for(int j = i; j < elements.length; ++j){ 

05                 if(elements[k] > elements[j]){ 

06                     k = j; 

07                 } 

08             } 

09             if(k != i){//交換元素 

10                 int temp = elements[i]; 

11                 elements[i] = elements[k]; 

12                 elements[k] = temp; 

13             } 

14         } 

15 }

  北大青鳥(niǎo)學(xué)校講師提示:直接選擇排序算法的思路很清晰,實(shí)現(xiàn)起來(lái)也比較簡(jiǎn)單,但是效率不是很高(O(n*n))。

  堆排序算法和直接選擇排序算法最大的不同在于,堆排序算法充分利用大頂堆和完全二叉樹(shù)的性質(zhì),保留每次排序后的結(jié)構(gòu),同時(shí)由于每次比較只是比較根節(jié)點(diǎn)和它的子節(jié)點(diǎn),因此大大降低了比較的次數(shù)和交換的次數(shù),從而提高效率,堆排序算法的時(shí)間復(fù)雜度是O(nlogn,以2為底)。

  堆排序算法的思想是:(假設(shè)數(shù)據(jù)放在一個(gè)數(shù)組a中,且數(shù)組的長(zhǎng)度是N)(北京北大青鳥(niǎo)學(xué)校)

  1:以數(shù)組a為數(shù)據(jù),建立一個(gè)大頂堆(這樣對(duì)于二叉樹(shù)的每個(gè)節(jié)點(diǎn),根節(jié)點(diǎn)總是比子節(jié)點(diǎn)大,其實(shí)沒(méi)必要要求二叉樹(shù)的每個(gè)子樹(shù)也是大頂堆)

  2:交換大頂堆的根節(jié)點(diǎn)和數(shù)組a中的最后一個(gè)節(jié)點(diǎn)(最后一個(gè)節(jié)點(diǎn)不在參與后邊的工作)

  重復(fù)上邊的工作,經(jīng)過(guò)N-1次后,數(shù)組a已經(jīng)排好序。

  堆排序算法的java實(shí)現(xiàn)如下:

view sourceprint?01 public static void heapSort(int[] elements){ 

02         for(int i = elements.length-1; i > 0; i--){ 

03             buildHeap(elements,i);//建堆 

04             swap(elements,0,i);//交換根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)  (北京北大青鳥(niǎo)學(xué)校

05         } 

06 } 

07       

08 private static void buildHeap(int[] elements,int lastIndex){ 

09         int lastParentIndex = (lastIndex-1)/2;//獲得最后一個(gè)父節(jié)點(diǎn) 

10         for(int i = lastParentIndex; i >=0; i--){ 

11             int parent = elements[i]; 

12             int leftChild = elements[i*2+1];//左節(jié)點(diǎn)肯定存在 

13             int rightChild = leftChild; 

14             if(i*2+2 <=lastIndex){ 

15                 rightChild = elements[i*2+2];//右節(jié)點(diǎn)不一定存在 

16             } 

17             int maxIndex = leftChild<rightChild?i*2+2:i*2+1; 

18             if(parent < elements[maxIndex]){ 

19                 swap(elements,i,maxIndex); 

20             } 

21         } 

22 } 

23       

24 private static void swap(int[] elements,int firstIndex,int secondIndex){ 

25         int temp = elements[firstIndex]; 

26         elements[firstIndex] = elements[secondIndex]; 

27         elements[secondIndex] = temp; 

28 }
北京北大青鳥(niǎo)學(xué)校)

北大青鳥(niǎo)網(wǎng)上報(bào)名
北大青鳥(niǎo)招生簡(jiǎn)章