北大青鳥北京，北大青鳥學校學術部老師講解：什么是選擇排序？
北大青鳥北京，北大青鳥學校解答：選擇排序是常用內部排序的一種，常見的實現算法有直接選擇排序算法和堆排序算法，選擇排序的基本思想是每次從待排數據中選擇第n小的數據放到排序列表的第n個位置，假如共有N個數據待排，那么經過N-1次排序后，待排數據就已經按照從小到大的順序排列了。
直接選擇排序算法的思想比較簡單：（假設數據放在一個數組a中，且數組的長度是N）
1：從a[0]-a[N-1]中選出最小的數據，然后與a[0]交換位置
2：從a[1]-a[N-1]中選出最小的數據，然后與a[1]交換位置（第1步結束后a[0]就是N個數的最小值）
3：從a[2]-a[N-1]中選出最小的數據，然后與a[2]交換位置（第2步結束后a[1]就是N-1個數的最小值）
以此類推，N-1次排序后，待排數據就已經按照從小到大的順序排列了。
直接選擇排序的java實現如下：（北京北大青鳥學校）
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 }
北大青鳥學校講師提示：直接選擇排序算法的思路很清晰，實現起來也比較簡單，但是效率不是很高（O(n*n)）。
堆排序算法和直接選擇排序算法最大的不同在于，堆排序算法充分利用大頂堆和完全二叉樹的性質，保留每次排序后的結構，同時由于每次比較只是比較根節點和它的子節點，因此大大降低了比較的次數和交換的次數，從而提高效率，堆排序算法的時間復雜度是O(nlogn，以2為底)。
堆排序算法的思想是：（假設數據放在一個數組a中，且數組的長度是N）（北京北大青鳥學校）
1：以數組a為數據，建立一個大頂堆（這樣對于二叉樹的每個節點，根節點總是比子節點大，其實沒必要要求二叉樹的每個子樹也是大頂堆）
2：交換大頂堆的根節點和數組a中的最后一個節點（最后一個節點不在參與后邊的工作）
重復上邊的工作，經過N-1次后，數組a已經排好序。
堆排序算法的java實現如下：
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);//交換根節點和最后一個節點 （北京北大青鳥學校）
05 }
06 }
07
08 private static void buildHeap(int[] elements,int lastIndex){
09 int lastParentIndex = (lastIndex-1)/2;//獲得最后一個父節點
10 for(int i = lastParentIndex; i >=0; i--){
11 int parent = elements[i];
12 int leftChild = elements[i*2+1];//左節點肯定存在
13 int rightChild = leftChild;
14 if(i*2+2 <=lastIndex){
15 rightChild = elements[i*2+2];//右節點不一定存在
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 }
（北京北大青鳥學校）
