北大青鳥(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é)校)