- 选择排序
- 简单选择排序
- 堆排序
选择排序的基本思想：每一趟(如第i趟)在后面n-i+1个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下1个，就不用再选了。
简单选择排序基本思想：在待排序的数据中选出最大(小)的元素放在最终的位置。
基本操作：
- 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换
- 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
- 重复上述操作，共进行n-1趟排序后，排序结束。
//选择排序
void SelectSort(int a[],int n){
int temp,min,count1=0,count2=0;
for(int i =0;ia[j]){
min = j;// 找出最小的值的下标
}
}
if(min!=i){// 对所有元素都进行比较之后，和i比较，如果一样则i是最小，不一样则互换
count2++;
temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
printf("总共进行了%d次比较，进行了%d次移动！",count1,count2);
}
int main()
{
int i ,a[10] = {5,2,6,0,3,9,1,7,4,8};
SelectSort(a,10);
printf("排序后的结果是：");
for(i = 0;i < 10 ;i++){
printf("%d",a[i]);
}
printf("nn");
return 0;
}
简单选择排序算法的性能分析：
空间效率：仅使用常数个辅助单元，故空间效率为O(1)
时间效率：从上述代码中可得，在简单选择排序的过程中，元素移动的操作次数很少，不会超过3(n-1)次，最好的情况是0次，此时对应的表已经有序，但元素间比较的次数与序列的初始状态无关，始终是n(n-1)/2，因此时间复杂度始终都是O(n^2)
稳定性：在第i趟找到最小元素之后，和第i个元素进行交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生变化。因此，简单选择排序是一种不稳定的排序方法。
堆的定义：若n个元素的序列{a1,a2,…an}满足（ai<=a2i且ai<=a2i+1）或（ai>=a2i且ai>=a2i+1）则分别称该序列（a1,a2,…an）为小根堆和大根堆。
从堆的定义可以看出，堆的实质是满足如下性质的完全二叉树：二叉树任一非叶子结点均小于(大于)他的孩子结点。
堆排序：若在输出堆顶的最小值(最大值)后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值(次大值)…如此反复，便能的到一个有序序列，这个过程称为堆排序。
小根堆：
- 输出堆顶元素之后，以堆中到最后一个元素代之；
- 然后将根结点值与左右子树的根结点值进行比较，并从其中小者进行交换；
- 重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为”筛选“
大根堆就是找大的，操作过程和小根堆类似。
下面是建立大根堆的算法
void BulidMaxHeap(ElemType A[], int len){
for(int i = len/2 ; i>0 ;i--){ //从i = n/2 到1 ，反复调整堆
HeadAdjust(A,i,len);
}
}
void HeadAdjust(Elemtype A[],int k . int len){
//函数HeadAdjust将元素k为根的子树进行调整
A[0] = A[k];//A[0]暂存子树的根结点
for(i= 2*k;i<=len ;i*=2){//沿k较大的子节点向下筛选
if(i
调整的时间与树高有关为O(h)。在建含n个元素的堆时，关键字的比较总次数不超过4n，时间复杂度为O(n)，这说明可以在线性时间内将一个无序数组组建成一个堆。
下面书堆排序算法：
void HeapSort(Elemtype A[],int len){
BulidMaxHeap(A,len);//初始建堆
for(i=len;i>1;i--){//n-1趟的交换和建堆过程
Swap(A[i],A[1]);//输出堆顶元素(和堆底元素交换)
HeadAdjust(A,1,i-1)；//调整，把剩余的i-1个元素整理成堆
}
}
同时，堆也支持插入操作。对堆进行插入操作时，先将新结点放在对的末尾，在对这个新结点向上执行调整操作。
堆排序适合关键字较多的情况，例如，在1亿个数中先出前100个最大值？首先使用一个大小为100的数组，读入前100个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中100个数即为所求。
堆排序算法的性能分析如下：
空间效率：仅使用了常数个辅助单元，所以空间复杂度为O(1)
时间效率：建堆时间为O(n)，之后有n-1次向下调整操作，每次调整的时间复杂度为O(h)，故在最好，最坏和平均情况下，堆排序的时间复杂度为O(nlog2n)。
稳定性：进行筛选时，有可能把后面相同的关键字调整到前面，所以堆排序时一种不稳定的排序方法。
