同样，递减的简单选择排序代码如下：

/*简单选择排序（递减）*/
void SelectSort2(int r[],int n) {int i,j,max,temp;for(i=0; i	//for循环进行n-1趟 max=i;	//max变量记录最小元素的位置 for(j=i+1; j	//从无序序列中选择一个最大的元素if(r[j]>r[max])max=j;}	temp=r[i];	//将最大元素与无序序列的第一个关键字进行交换 r[i]=r[max];r[max]=temp;}
}

例如，对于一个序列{-2，0，7，1，4，3}进行简单选择排序，输出其递增和递减序列，代码如下：

#include
#define MAXSIZE 100
/*创建函数*/
void Create(int r[],int n) {for(int i=0; iprintf("输入第%d个元素：",i+1);scanf("%d",&r[i]);}
}/*输出函数*/
void Display(int r[],int n) {for(int i=0; iint i,j,min,temp;for(i=0; i	//for循环进行n-1趟 min=i;	//min变量记录最小元素的位置 for(j=i+1; j	//从无序序列中选择一个最小的元素 if(r[j]int i,j,max,temp;for(i=0; i	//for循环进行n-1趟 max=i;	//max变量记录最小元素的位置 for(j=i+1; j	//从无序序列中选择一个最大的元素if(r[j]>r[max])max=j;}	temp=r[i];	//将最大元素与无序序列的第一个关键字进行交换 r[i]=r[max];r[max]=temp;}
}/*主函数*/
int main() {int n;int r[MAXSIZE];printf("请输入排序表的长度：");scanf("%d",&n);Create(r,n);printf("已建立的序列为：\n");Display(r,n);SelectSort1(r,n);printf("\n");printf("递增排序后的序列为：\n");Display(r,n);SelectSort2(r,n);printf("\n");printf("递减排序后的序列为：\n");Display(r,n);
}

运行结果如下：

简单选择排序
1、第一趟简单选择排序，从左往右搜索最小的元素，找到-2，将该元素与第一个元素进行交换，由于-2本身处于第一个元素位置，未发生交换；

2、第二趟简单选择排序，在剩下的无序序列中，从左往右搜索最小的元素，找到0，将该元素与第二个元素进行交换，由于0本身处于第二个元素位置，未发生交换；

3、第三趟简单选择排序，在剩下的无序序列中，从左往右搜索最小的元素，找到1，将该元素与第三个元素7进行交换；

4、第四趟简单选择排序，在剩下的无序序列中，从左往右搜索最小的元素，找到3，将该元素与第四个元素7进行交换；

5、第五趟简单选择排序，在剩下的无序序列中，从左往右搜索最小的元素，找到4，未发生交换；

此时整个序列已经有序，可以得出，共进行n-1趟排序过程。

（二）算法分析

分析：
（1）空间复杂度：由于额外辅助空间只有一个temp变量，为参数级，所以简单选择排序的空间复杂度为O(1)；
（2）时间复杂度：元素之间的比较次数与初始序列无关，即每次的比较分别是n-1，n-2，……，2，1，即n(n-1)/2=n²/2，所以时间复杂度为O(n²)。
（4）稳定性：简单选择排序是一种不稳定的排序算法。
（5）适用性：简单选择排序可适用于顺序存储和链式存储的线性表。
（6）排序方式：简单选择排序是一种内部排序（In-place）。

二、堆排序

（一）排序思想

1、堆树和大、小根堆

堆排序是利用堆树来进行排序，可以将其视为一棵完全二叉树，树中每一个结点均大于或等于其两个子结点的值，根结点是堆树中的最小值或最大值，即对应小根堆和大根堆。

基于小根堆得到的序列为递减序列，基于大根堆得到的序列为递增序列。

2、调整根堆

顺序存储的完全二叉树（若结点为i）：
①i的左孩子结点，则为2i；
②i的右孩子结点，则为2i+1；
③i的父结点，则为⌊ i/2 ⌋。

以下以调整大根堆为例，
对于一个大根堆，检查所有非终端结点是否满足大根堆的要求（根结点≤左孩子,右孩子），不满足则进行调整：若当前结点的元素小于左、右孩子中较大者元素，则将当前结点与较大者元素进行交换，使该子树成为堆，若因元素交换破坏了下一级的堆顺序，使不满足堆的性质，则向下继续进行调整。
调整堆的代码如下：

/*堆调整*/
void Adjust(int r[],int low,int high) {int i=low,j=2*i;	//r[j]是r[i]的左孩子结点 int temp=r[i];while(j<=high) {if(jr[i]=r[j];	//将r[j]调整至双亲结点的位置上，互换 i=j;	//修改i和j的值，以便继续调整 j=2*i;} elsebreak;	//调整结束}r[i]=temp;		//将被调整的结点放到其应当的位置 
}

1、初始堆树如下：

2、根据完全二叉树的性质，由下至上进行调整

在顺序存储的完全二叉树中，非叶子结点的编号i≤⌊N/2 ⌋。

由于N=8，可得非叶子结点的编号i≤⌊N/2 ⌋=⌊8/2 ⌋=4，检查所有非终端结点是否满足大根堆的要求，即检查i≤4的结点，且按照从下往上的顺序依次检查。
3、i=4，结点32不满足要求：


4、i=3，结点19不满足要求：


5、i=2，结点21不满足要求：


6、i=1，结点15不满足要求：


7、由于经过以上的几轮交换后，可发现结点15不满足大根堆的要求，向下继续进行调整：

还需调整：

至此，该完全二叉树符合堆的定义。

3、堆排序

在建立根堆后，将堆中堆顶元素与堆的最后一个元素进行交换，堆顶元素进入有序序列到达最终位置（从无序序列中被排出，符合选择排序的过程），然后对剩下的无序序列继续进行调整，依次进行下去，……，直到无序序列中剩余最后一个元素，此时整个序列已经有序，堆排序结束。
堆排序的代码如下：

/*堆排序*/
void HeapSort(int r[],int n){int i,temp;for(i=n/2;i>=1;i--)		//建立初始堆 Adjust(r,i,n);for(i=n;i>1;i--){	//进行n-1次循环，完成堆排序 temp=r[1];	//将堆中最后一个元素与堆顶元素交换，将其放入最终位置 r[1]=r[i];r[i]=temp;Adjust(r,1,i-1); 	//对剩下的无序序列进行调整 }
}

1、第一趟，将堆顶元素与堆的最后一个元素进行交换，将堆顶元素加入有序子序列，即40与15交换：


可看出，此时序列中不满足大根堆的要求（不包括有序子序列40），所以需要恢复大根堆，剩下的无序序列调整为大根堆，调用函数Adjust(r,1,7)：


2、第二趟操作也是一样，将堆顶元素与堆的最后一个元素进行交换，将堆顶元素加入有序子序列，即38与19交换：

剩下的无序序列调整为大根堆，调用函数Adjust(r,1,6)：


3、第三趟，33与19交换：

剩下的无序序列调整为大根堆，调用函数Adjust(r,1,5)：


4、第四趟，32与19交换：

剩下的无序序列调整为大根堆，调用函数Adjust(r,1,4)：

5、第五趟，29与15交换：

剩下的无序序列调整为大根堆，调用函数Adjust(r,1,3)：

6、第六趟，21与19交换：

剩下的无序序列调整为大根堆，调用函数Adjust(r,1,2)：

7、第七趟，由于符合大根堆，不用交换：

剩下最后一个元素，结束，此时得到的序列即为最终结果：

整体代码如下：

#include
#define MAXSIZE 100
/*创建函数*/
void Create(int r[],int n) {for(int i=0; iprintf("输入第%d个元素：",i+1);scanf("%d",&r[i]);}
}/*输出函数*/
void Display(int r[],int n) {for(int i=0; iint i=low,j=2*i;	//r[j]是r[i]的左孩子结点 int temp=r[i];while(j<=high) {if(jr[i]=r[j];	//将r[j]调整至双亲结点的位置上，互换 i=j;	//修改i和j的值，以便继续调整 j=2*i;} elsebreak;	//调整结束}r[i]=temp;		//将被调整的结点放到其应当的位置 
}/*堆排序*/
void HeapSort(int r[],int n){int i,temp;for(i=n/2;i>=1;i--)		//建立初始堆 Adjust(r,i,n);for(i=n;i>1;i--){	//进行n-1次循环，完成堆排序 temp=r[1];	//将堆中最后一个元素与堆顶元素交换，将其放入最终位置 r[1]=r[i];r[i]=temp;Adjust(r,1,i-1); 	//对剩下的无序序列进行调整 }
}/*主函数*/
int main() {int n;int r[MAXSIZE];printf("请输入排序表的长度：");scanf("%d",&n);Create(r,n);printf("已建立的序列为：\n");Display(r,n);HeapSort(r,n);printf("\n");printf("排序后的序列为：\n");Display(r,n);
}

运行结果如下：

（二）算法分析

分析：
（1）空间复杂度：堆排序的空间复杂度为O(1)；
（2）时间复杂度：初始建堆的时间复杂度为O(n)，建堆过程中元素对比次数不超过4n，n-1趟交换和建堆过程中，根结点最多下坠h-1层，每下坠一层最多只需对比元素两次，每一趟不超过O(h)=O(log₂n)，即堆排序的时间复杂度为O(nlog₂n)，故堆排序的时间复杂度均为O(n)+O(nlog₂n)=O(nlog₂n)。
（3）稳定性：堆排序是一个不稳定的排序算法。
（4）适用性：堆排序只能用于顺序存储结构。
（5）排序方式：堆排序是一种内部排序（In-place）。

三、总结

两种交换排序与前面的插入排序的总结如下表：