选择排序
选择排序的思想是：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
假如待排数据为：9,6,2,3,10，那么每趟选择排序之后（从小到大），数据的变化情况为：
2,6,9,3,10
2,3,9,6,10
2,3,6,9,10
2,3,6,9,10
简单选择排序的时间复杂度为O(n^2)，它是不稳定排序。
void selectsort(int a[], int n)
{
int i, j, k, tmp;
for (i = 0; i < n-1; i++)
{
k = i;
for (j = i + 1; j < n; j++)
{
if (a[j] < a[k])
k = j;
}
if (k != i)
{
tmp = a[i];
a[i] = a[k];
a[k] = tmp;
}
}
}
6.2.1 堆排序
堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
void sfilter(int a[], int l, int m)
{
int i, j x;
i
= l;
j = 2 * i;
x = a[i];
while ( j <= m)
{
if (j < m && a[j] < a[j+1])
j++;
if (x < a[j])
{
a[i] = a[j];
i = j;
j = 2 * i;
}
else
{
j = m + 1;
}
}
a[i] = x;
}
void heapsort(int a[], int n)
{
int i, w;
for (i = n/2; i >= 1; i--)
sfilter(a, i, n);
for (i = n; i >= 2; i--)
{
w = a[i];
a[i] = a[1];
a[1] = w;
sfilter(a, 1, i - 1);
}
}
堆排序的时间复杂度为O(nlogn)，它是不稳定排序。
