北大青鸟北京，北大青鸟学校学术部老师讲解：什么是选择排序？
北大青鸟北京，北大青鸟学校解答：选择排序是常用内部排序的一种，常见的实现算法有直接选择排序算法和堆排序算法，选择排序的基本思想是每次从待排数据中选择第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 }
（北京北大青鸟学校）
