简单选择排序
基本思想：
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
排序示例如下：
操作方法：
第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推.....
第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，
直到整个序列按关键码有序。
简单选择排序算法原理：
每次从左至右扫描序列，记下最小值的位置。
程序示例
/*简单选择排序*/
#include<stdio.h>
void easy_px(int *p,int n);
int main()
{
int a[]={1,6,4,8,7,9,2,10};
int n;
n=sizeof(a)/sizeof(a[0]);
easy_px(a,n);
}
//按从小到大的顺序排列
void easy_px(int *p,int n)
{
int i,j,k;
int temp;
for(i=0;i<n;i++)
{
k=i; //得到每次要排序的元素的下标
for(j=i+1;j<n;j++) //与后面的元素进行比较
{
if(p[k]>p[j])
{
k=j; //找出最小值，并保存下标
}
}
if(k!=i) //如果下标不相等，则交换位置
{
temp=p[i];
p[i]=p[k];
p[k]=temp;
}
}
for(i=0;i<n;i++)
printf("%d ",p[i]);
printf("\n");
}
2）简单选择排序的改进——二元选择排序
简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：
/*简单选择排序之二元排序*/
#include<stdio.h>
void implict_celect_px(int *s,int n);
int main()
{
int a[]={1,1,1,8,3,4,6,1,45,67,12,34,90,1};
int n;
int i;
n=sizeof(a)/sizeof(a[0]);
printf("排序之前：\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
implict_celect_px(a,n);
printf("排序之后：\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void implict_celect_px(int *s,int n)
{
int max,min;
int pmax,pmin;
int i,j;
for(i=0;i<n/2;i++)
{
min=max=i;
for(j=i;j<n-i;j++)
{
if(s[min]>s[j])
{
min=j;
continue;
}
if(s[max]<s[j])
max=j;
}
pmax=s[max];
pmin=s[min];
if(max==i)
{
s[max]=s[n-1-i];
s[min]=s[i];
}
else if(min==n-1-i)
{
s[min]=s[i];
s[max]=s[n-1-i];
}
else
{
s[min]=s[i];
s[max]=s[n-1-i];
}
s[i]=pmin;
s[n-1-i]=pmax;
}
}
3）选择排序—堆排序（Heap Sort）（待定，不常用）
什么是堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
定义
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
(1) ki≤K2i且ki≤K2i+1或
(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
堆的意义
堆排序是一种排序方法，但在实践中由于堆排序不如快速排序，所以很少用。
主要用来最快的找到最大值和最小值。
#include <stdio.h>
//array是待调整的堆数组，i是待调整的数组元素的位置，nlength是数组的长度
//本函数功能是：根据数组array构建大根堆
void HeapAdjust(int array[],int i,int nLength)
{
int nChild;
int nTemp;
for(;2*i+1<nLength;i=nChild)
{
//子结点的位置=2*（父结点位置）+1
nChild=2*i+1;
//得到子结点中较大的结点
if(nChild<nLength-1&&array[nChild+1]>array[nChild])++nChild;
//如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
if(array[i]<array[nChild])
{
nTemp=array[i];
array[i]=array[nChild];
array[nChild]=nTemp;
}
else break; //否则退出循环
}
}
//堆排序算法
void HeapSort(int array[],int length)
{
int i;
//调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
//length/2-1是最后一个非叶节点，此处"/"为整除
for(i=length/2-1;i>=0;--i)
HeapAdjust(array,i,length);
//从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for(i=length-1;i>0;--i)
{
//把第一个元素和当前的最后一个元素交换，
//保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
array[i]=array[0]^array[i];
array[0]=array[0]^array[i];
array[i]=array[0]^array[i];
//不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
HeapAdjust(array,0,i);
}
}
int main()
{
int i;
int num[]={9,8,7,6,5,4,3,2,1,0};
HeapSort(num,sizeof(num)/sizeof(int));
for(i=0;i<sizeof(num)/sizeof(int);i++)
{
printf("%d ",num[i]);
}
printf("\nok\n");
return 0;
}