北大青鳥北京，北大青鳥學(xué)校學(xué)術(shù)部老師講解：什么是選擇排序？
北大青鳥北京，北大青鳥學(xué)校解答：選擇排序是常用內(nèi)部排序的一種，常見的實(shí)現(xiàn)算法有直接選擇排序算法和堆排序算法，選擇排序的基本思想是每次從待排數(shù)據(jù)中選擇第n小的數(shù)據(jù)放到排序列表的第n個(gè)位置，假如共有N個(gè)數(shù)據(jù)待排，那么經(jīng)過N-1次排序后，待排數(shù)據(jù)就已經(jīng)按照從小到大的順序排列了。
直接選擇排序算法的思想比較簡單：（假設(shè)數(shù)據(jù)放在一個(gè)數(shù)組a中，且數(shù)組的長度是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)如下：（北京北大青鳥學(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 }
北大青鳥學(xué)校講師提示：直接選擇排序算法的思路很清晰，實(shí)現(xiàn)起來也比較簡單，但是效率不是很高（O(n*n)）。
堆排序算法和直接選擇排序算法最大的不同在于，堆排序算法充分利用大頂堆和完全二叉樹的性質(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ù)組的長度是N）（北京北大青鳥學(xué)校）
1：以數(shù)組a為數(shù)據(jù)，建立一個(gè)大頂堆（這樣對于二叉樹的每個(gè)節(jié)點(diǎn)，根節(jié)點(diǎn)總是比子節(jié)點(diǎn)大，其實(shí)沒必要要求二叉樹的每個(gè)子樹也是大頂堆）
2：交換大頂堆的根節(jié)點(diǎn)和數(shù)組a中的最后一個(gè)節(jié)點(diǎn)（最后一個(gè)節(jié)點(diǎn)不在參與后邊的工作）
重復(fù)上邊的工作，經(jīng)過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) （北京北大青鳥學(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 }
（北京北大青鳥學(xué)校）
