1、序言
这是《漫谈经典排序算法系列》第一篇，该篇从最简单的选择排序算法谈起，由浅入深的详细解析两种选择排序算法的过程及性能比较。逐步揭露选择排序的本质及其基本思想。
各种排序算法的解析请参考如下：
《漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析》
《漫谈经典排序算法:二、各种插入排序解析及性能比较》
《漫谈经典排序算法:三、冒泡排序 && 快速排序》
《漫谈经典排序算法:四、归并排序》
《漫谈经典排序算法:五、线性时间排序(计数、基数、桶排序)》
《漫谈经典排序算法:六、各种排序算法总结》
注：为了叙述方便，本文以及源代码中均不考虑A[0],默认下标从1开始。
2、提出问题
（1）简单选择排序和堆排序的基本思想是什么？
（2）选择排序的本质是什么？
相信看完这篇文章，读者一定可以找到答案。
3、漫谈简单选择排序 3.1 从一个简单问题谈起
给定待排序序列A[ 1…..n ]，选择出A中最小的记录（也可以理解为求一个无序数组A中的最小的元素）。下面给出代码如下：
//选择待排序序列a中的最小记录,其下标为indexfor(index=i=1;i<=n;i++){if(a[i]<a[index])index=i;}
3.2 简单选择排序的过程
描述：给定待排序序列A[ 1……n ] ，选择出第i小元素，并和A[i]交换，这就是一趟简单选择排序。
代码：
//简单选择排序void simpleSelectionSort1(int *a,int n){int i,j,index;//1.进行n-1趟选择，每次选出第i小记录for(i=1;i<n;i++){index=i;//2.选择第i小记录为a[index]for(j=i+1;j<=n;j++)if(a[j]<a[index])index=j;//3.与第i个记录交换if(index!=i){a[i]=a[i]+a[index];a[index]=a[i]-a[index];a[i]=a[i]-a[index];}}}
示例：假设给定数组A[1……6]={ 3,5,8,9,1,2 }，我们来分析一下A数组进行选择排序的过程
第一趟：i=1，index=5， a[1] 和 a[5] 进行交换。得到序列：{ 1,5,8,9,3,2 }
第二趟：i=2，index=6， a[2] 和 a[6] 进行交换。得到序列：{ 1,2,8,9,3,5 }
第三趟：i=3，index=5， a[3] 和 a[5] 进行交换。得到序列：{ 1,2,3,9,8,5 }
第四趟：i=4，index=6， a[3] 和 a[5] 进行交换。得到序列：{ 1,2,3,5,8,9 }
第五趟：i=5，index=5， 不用交换。得到序列：{ 1,2,3,5,8,9 }
（6-1）趟选择结束，得到有序序列：{ 1,2,3,5,8,9 }
3.3 性能分析
坏还是最佳情况下，比较次数都是一样的，所以简单选择排序平均时间、最坏情况、最佳情况 时间复杂度都为O（n^2）。同时简单选择排序是一种稳定的原地排序算法。当然稳定性还是要看具体的代码，在此就不做深究。
3.4 简单选择排序引发的思考
第一趟排序后：{ 1,5,8,9,3,2 }，此时A[ 1 ]已经有序，我们可以把待排序序列缩减到A[ 2……6 ]
第二趟排序后：{ 1,2,8,9,3,5 }，此时A[ 1…2 ]已经有序，我们可以把待排序序列缩减到A[ 3……6 ]
第三趟排序后：{ 1,2,3,9,8,5 }，此时A[ 1…3 ]已经有序，我们可以把待排序序列缩减到A[ 4……6 ]
第四趟排序后：{ 1,2,3,5,8,9 }，此时A[ 1…4 ]已经有序，我们可以把待排序序列缩减到A[ 5……6 ]
第五趟排序后：{ 1,2,3,5,8,9 }，此时A[ 1…5 ]已经有序，我们可以把待排序序列缩减到A[ 6……6 ]
//递归函数进行简单选择排序void simpleSelectionSort2(int *a,int n){int index,i;if(n==1)return;//1.选择待排序序列a中的最小记录,其下标为indexfor(index=i=1;i<=n;i++){if(a[i]<a[index])index=i;}//2.最小记录与待排序序列首元素进行交换if(index!=1){a[1]=a[1]+a[index];a[index]=a[1]-a[index];a[1]=a[1]-a[index];}//3.待排序序列元素个数减少，递归对剩下的无序序列排序simpleSelectionSort2(a+1,n-1);}
看到这里，不知大家是否还记得上文3.1中谈到的简单的问题。由此可以看出这个简单的问题正是简单选择排序的本质所在。
4、深入堆排序4.1 堆排序的引入 4.2 什么是堆
首先堆是一种数据结构，是一棵完全二叉树且满足性质：所有非叶子结点的值均不大于或均不小于其左、右孩子结点的值，如下是一个堆得示例：
9>8,9>5;8>3,8>1;5>2 由此发现非叶子结点的值均不小于左右孩子结点的值，所以这是个大顶堆，即堆顶的值是这个堆中最大的一个。
下面的问题是我们怎么样在计算机中存储这个堆呢？也许有人会想到树的存储，确实，刚看这个堆我也是这么想的。然而事实并非如此，这个堆可以看成是一个一维数组A[6]={9,8,5,3,1,2}，那么相应的这个数组需满足性质：A[i]<=A[2*i] && A[i]<=A[2*i+1] 。其中A[i]对应堆中的非叶子结点，A[2*i]和A[2*i+1]对应于左右孩子结点。并且最后一非叶子结点下标为[n/2]向下取整。
为什么是[n/2]向下取整呢？在这里我简单的说明一下：设n1表示完全二叉树中有一个孩子的结点，n2表示表示完全二叉树中有两个孩子的结点，d表示非叶子结点的个数，那么总的结点个数：n=n1+2*n2+1。
（1）当n为奇数时，n1=0，n2=(n-1)/2，d=n2+n1=(n-1)/2
（2）当n为偶数时，n1=1，n2=n/2-1，d=n2+n1=n/2
由此可以看出d=[n/2]向下取整.
注：请大家一定要结合完全二叉树形式的堆以及堆的数组存储形式来看下面的内容，这样才能真正理解堆排序的过程及其本质。
4.3筛选法调整堆
（1）引出：
现给定一个大顶堆：
即：A[6]={9,8,5,3,1,2}，如果我们稍做破坏，把9跟2互换，同时把a[6]这个结点从堆中去掉，于是得到下面这个完全二叉树：
A[5]={2,8,5,3,1}
（2）代码：
//调整堆，保持大顶堆的性质,参数i指向根结点void maxHeap(int *a,int n,int i){//left、right、largest分别指向//左孩子、右孩子、{a[i],a[left]}中最大的一个int left,right,largest;largest=left=2*i;if(left>n)return;right=2*i+1;if(right<=n && a[right]>a[left]){largest=right;}if(a[i]<a[largest]){//根结点的值不是最大时,交换a[i]，a[largest]a[i]=a[i]+a[largest];a[largest]=a[i]-a[largest];a[i]=a[i]-a[largest];//自上而下调整堆maxHeap(a,n,largest);}}
（3）示例
以这个完全二叉树为例：
A[5]={2,8,5,3,1}
第一次筛选：2和8交换
A[5]={8,2,5,3,1}
第二次筛选：2和3交换
A[5]={8,3,5,2,1}
筛选完毕，得到大顶堆A[5]={8,3,5,2,1}。
（4）时间代价分析
每一次筛选的过程就是调用一次maxHeap函数，需要的时间是O（1）。那么要执行多少次筛选呢？从上述中可以看出，，每一次筛选根结点都往下沉，所以筛选次数不会超过完全二叉树的深度：（[log2n]向下取整+1），其中n为结点个数,2为底数,即时间复杂度为O（log2n）
为什么n个结点的完全二叉树的深度是([log2n]向下取整+1)呢？这里给出简单的说明：
深度为h的完全二叉树至多有2^h-1个结点，即2^(h-1)<=n<2^h,推出h-1<=log2n<h;由于h是一个整数，所以h=[log2n]向下取整+1 .
4.4建堆
4.3中叙述了堆的筛选过程，但是给定一个待排序的序列，怎样通过筛选使这个序列满足堆的性质呢？
给定待排序序列
A[6]={3,5,8,9,1,2},怎样使它变成一个堆呢？
仔细想一想筛选法的前提条件是什么：根结点的左右子树已经是堆。那么这棵树中哪个结点的左右子树是堆呢，很自然的发现是最后一个非叶子结点，所以我们在这里需要自下而上的调整这个完全二叉树。
（2）代码：
//建堆void creatHeap(int *a,int n){int i;//自下而上调整堆for(i=n/2;i>=1;i–)maxHeap(a,n,i);}
（3）示例
待排序序列：
A[6]={3,5,8,9,1,2},
以8为根结点调整堆后：因为8>2，此处不进行记录移动操作
以5为根结点调整堆后：5<9,5跟9互换
A[6]={3,9,8,5,1,2}
以3为根结点调整堆后：3<9,3跟9互换
A[6]={9,3,8,5,1,2}
以9为根的左子树不满足大顶堆的性质，所以以3为跟调整堆,即交换3和5，得A[6]={9,5,8,3,1,2}
（4）时间代价分析
从最后一个非叶子结点到第二个结点，总共循环了n/2-1次，每次调用maxHeap函数，4.3中已经分析过maxHeap时间复杂度为O（log2n）。所以建堆的时间复杂度为O（n*log2n）
4.5堆排序
（1）堆排序过程
也许有的朋友想问：不是讲堆排序吗，为什么不直接讲呢，而是先叙述筛选法和建堆呢？因为筛选法和建堆就构成了堆排序，讲到这里，堆排序可以说是水到渠成。所以一定要理解筛选法和建堆的过程。
过程描述：1、建堆 2、将堆顶记录和堆中最后一个记录交换 3、筛选法调整堆，堆中记录个数减少一个，重复第2步。整个过程中堆是在不断的缩减。
（2）代码
//堆排序void heapSort(int *a,int n){int i;creatHeap(a,n);//建堆for(i=n;i>=2;i–){//堆顶记录和最后一个记录交换a[1]=a[1]+a[i];a[i]=a[1]-a[i];a[1]=a[1]-a[i];//堆中记录个数减少一个，筛选法调整堆maxHeap(a,i-1,1);}}
（3）示例 0.待排序序列：
A[6]={3,5,8,9,1,2},
1.建堆后（建堆过程参见4.4）：
A[6]={9,3,8,5,1,2}
2.9和2交换，然后把9从堆中去掉后：
A[6]={2,3,8,5,1,9}
3.筛选法调整堆A[5]={2,3,8,5,1}后（调整过程参见4.3）：
A[6]={8,3,2,5,1,9}
4.堆顶记录与最后一个记录互换，重复第二步，但是堆顶记录和最后一个记录的值变了
（4）堆排序性能分析
堆排序时间=建堆时间+调整堆时间。从上文中知道建堆时间复杂度为O（n*log2n）。筛选法调整堆（maxHeap函数）时间O（log2n），总共循环了n-1次maxHeap函数，所以调整堆时间复杂度为O（n*log2n）。得出堆排序时间复杂度O（n*log2n）。
熟悉了堆排序的过程后，可以发现堆排序不存在最佳情况，待排序序列是有序或者逆序时，并不对应于堆排序的最佳或最坏情况。且在最坏情况下时间复杂度也是O（n*log2n）。此外堆排序是不稳定的原地排序算法。
4.6 反思堆排序 —— 揭开选择排序的本质和基本思想
仔细回想一下筛选法调整堆的过程我们发现，第i次调整堆，其实就是把A中的第i大元素放到首位置A[1]，然后A[1]和A[n-i+1]互换.这样A[(n-i+1)…n]就已经有序，于是又把A[1…n-i]看成一个堆再进行排序，如此重复。
还记得3.1中提到那个简单的问题（选择出A中最小的记录）吗？调整堆不就是选择出待排序序列中的最大值吗？所以堆排序的本质和选择排序的本质是一样的。选择一个待排序序列中的最小（大）值，这就是选择排序的本质。
叙述到此，相信大家已然知道开篇提出的两个问题的答案了吧。选择排序的基本思想是：每一趟从n-i+1个记录中选择最小（大）记录和第i（n-i+1）个记录交换。
5、附件5.1 附件1
参考文献：《数据结构》严蔚敏版 《算法导论》第二版
5.2 附件2
本文涉及的源代码免积分下载地址：
5.3 附件3
源代码
simple_selection_sort.c
#include<stdio.h>//简单选择排序void simpleSelectionSort1(int *a,int n){int i,j,index;//1.进行n-1趟选择，每次选出第i小记录for(i=1;i<n;i++){index=i;//2.选择第i小记录为a[index]for(j=i+1;j<=n;j++)if(a[j]<a[index])index=j;//3.与第i个记录交换if(index!=i){a[i]=a[i]+a[index];a[index]=a[i]-a[index];a[i]=a[i]-a[index];}}}//递归函数进行简单选择排序void simpleSelectionSort2(int *a,int n){int index,i;if(n==1)return;//1.选择待排序序列a中的最小记录,其下标为indexfor(index=i=1;i<=n;i++){if(a[i]<a[index])index=i;}//2.最小记录与待排序序列首元素进行交换if(index!=1){a[1]=a[1]+a[index];a[index]=a[1]-a[index];a[1]=a[1]-a[index];}//3.待排序序列元素个数减少，递归对剩下的无序序列排序simpleSelectionSort2(a+1,n-1);}
heap_sort.c
#include<stdio.h>//调整堆，保持大顶堆的性质,参数i指向根结点void maxHeap(int *a,int n,int i){//left、right、largest分别指向//左孩子、右孩子、{a[i],a[left]}中最大的一个int left,right,largest;largest=left=2*i;if(left>n)return;right=2*i+1;if(right<=n && a[right]>a[left]){largest=right;}if(a[i]<a[largest]){//根结点的值不是最大时,交换a[i]，a[largest]a[i]=a[i]+a[largest];a[largest]=a[i]-a[largest];a[i]=a[i]-a[largest];//自上而下调整堆maxHeap(a,n,largest);}}//建堆void creatHeap(int *a,int n){int i;//自下而上调整堆for(i=n/2;i>=1;i–)maxHeap(a,n,i);}//堆排序void heapSort(int *a,int n){int i;creatHeap(a,n);//建堆for(i=n;i>=2;i–){//堆顶记录和最后一个记录交换a[1]=a[1]+a[i];a[i]=a[1]-a[i];a[1]=a[1]-a[i];//堆中记录个数减少一个，筛选法调整堆maxHeap(a,i-1,1);}}人若软弱就是自己最大的敌人
