[转载]编程基本算法（三）

//简单选择排序
void SimpleSelect(int b[10])
{
    int temp;
    int i;
    for(i=0;i<9;i++)
    {
        for(int j=i+1;j<9;j++)
        {
            if(b[i]>b[j])
            {
                temp=b[i];
                b[i]=b[j];
                b[j]=temp;
            }
        }
    }
    cout<<"the sort is:";
    for(int i=0;i<10;i++)
    {
        cout<<b[i]<<" ";
    }
    cout<<endl;
}

//堆排序
void HeapSort(int b[10])
{
    void HeapAdjuest(int b[10],int min,int max);
    void Sawp(int *a,int *b);
    int i;
    //因为是完成二叉树，所以从最后一个非叶子节点开始堆转换
    for(i=9/2;i>=0;i--)
    {
        HeapAdjuest(b,i,9);
    }
    //拿出堆顶数据在从新堆排序
    for(i=9;i>0;i--)
    {
        Sawp(&b[i],&b[0]);
        HeapAdjuest(b,0,i-1);
    }
}

//堆调整(大顶堆)
//min 数据需要调整在数组中的开始位置
//max 数据需要调整在数据中的结束位置
void HeapAdjuest(int b[10],int min,int max)
{
    if(max<=min)return ;
    int temp;
    temp=b[min];
    int j;
    
    //延它的孩子节点循环
    for(j=2*min;j<=max;j*=2)
    {
        //选择它的大孩子
        if(j<max&&b[j]<b[j+1])
        {
            j++;
        }
        
        //堆顶小于它的孩子不做处理
        if(temp>b[j])
        {
            break;
        }
        
        //将大的数替换成小的数
        b[min]=b[j];
        min=j;    
    }
    b[min]=temp;
}

//交换函数
void Sawp(int *a,int *b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

//归并排序
void MergeSort(int b[10],int d[10],int min,int max)
{
    //用与存放中间分区域得到的序列
    int c[10];
    void Merge(int c[10],int d[10],int min,int mid,int max);
    if(min==max)d[min]=b[min];
    else
    {
        //平分成两个区域
        int mid=(min+max)/2;
        //将这个区域进行归并排序
        MergeSort(b,c,min,mid);
        //将这个区域进行归并排序
        MergeSort(b,c,mid+1,max);
        //两个区域归并
        Merge(c,d,min,mid,max);
    }
}

//将有序序列d[min-mid]与d[mid+1-max]归并成有序序列c[min-max]
void Merge(int c[10],int d[10],int min,int mid,int max)
{
    int i,j,k;
    for(i=j=min,k=mid+1;j<=mid&&k<=max;i++)
    {
        if(c[j]>c[k])
        {
            d[i]=c[k];
            k++;
        }
        else
        {
            d[i]=c[j];
            j++;
        }
    }
    if(j<=mid)
    {
        for(;j<=mid;j++,i++)
        {
            d[i]=c[j];
        }
    }
    if(k<=max)
    {
         for(;k<=max;k++,i++)
        {
            d[i]=c[k];
        }
    }
}