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