选择，堆排序，基数排序

选择排序

排序原理

设一个预留空间，存放每次选择的最小元素的下标。
开始循环：

• 记录当前最小元素的下标
• 从记录的最小元素下标的下一个元素开始：
  • 如果存在一个元素小于可用最小元素下标的元素值。
  • 将当前元素的下标给可用的最小元素下标，准备进行双方交换。
  • 如果：
    第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);
    }
}

基数排序

排序原理