选择排序
排序原理
设一个预留空间，存放每次选择的最小元素的下标。
开始循环：
- 记录当前最小元素的下标
- 从记录的最小元素下标的下一个元素开始：
- 如果存在一个元素小于可用最小元素下标的元素值。
- 将当前元素的下标给可用的最小元素下标，准备进行双方交换。
- 如果：
第i次选的最小元素下标不等于i,则将两个元素交换。
void selectsort(int a[ ],int n)
{
int i,j,k;
for(i=1,i<=n;i++)
{
k=i;
for(j=i+1;j<=n;j++)
if(a[j]<a[k]) k=j;
if(k!=i)
{
a[0]=a[k];
a[k]=a[j];
a[j]=a[0];
}
}
}
堆排序
排序原理
第一步：先建立heapify函数。
设置根结点i为max，设置左孩子为2*i+1,设置右孩子为2*i+2。
- 如果左孩子存在，且左孩子大于max，则将左孩子的值给max。
- 如果右孩子存在，且右孩子大于max，则将右孩子的值给max。
- 如果max不是根结点，交换max与根结点i的值。
- 递归执行heapify本身。
第二步：进行堆排序
从根结点i开始，循环建堆。
从最后一个叶子结点开始，交换叶子结点与根结点的值，递归执行heapify堆化函数。
void heapify(int a[],int n,int i)
{
int max=i;
int Lson=2*i+1;
int Rson=2*i+2;
if(Lson <n && Lson > max)
max=Lson;
if(Rson <n && Rson >max)
max=Rson;
if(max!=i)
{
swap(&a[max],&a[i]);
}
heapify(a,n,i);
}
void heapsort(int a[],int n)
{
int i;
for(i=n/2-1;i>=0;i--)
//从根开始，对每一个存在的子堆进行堆化
heapify(a,n,i);
for(i=n-1;i>=0;i++)
{
swap(&a[0],&a[i]);
heapify(a,n,i);
}
}
