计数排序+基数排序

这几天一直在写排序算法，从插入，冒泡，选择到归并和快速再到计数和基数排序。今天来写下计数排序和基数排序吧。
计数排序：对于一组小于k的数组，进行排序。这里要保证输入的关键值在[0..k]之间。貌似很简单，我们先不管什么是计数排序CountSort(A,1,n)，先来看一下一段代码。
CountPrint(int *A,int n,int k)代码：

void CountPrint(int *A,int n,int k){//输入数组A，每个元素都小于k
    //C[i]用来计算i出现的次数，起初C[i]=0
    int *C=new int[k+1];
    memset(C,0,(k+1)*sizeof(int));
    for(int i=1;i<=n;i++){
        C[A[i]]++;
    }
    for(int i=0;i<=k;i++){
        //cout<<C[i]<<endl;
        while(C[i]--){
            cout<<i<<" ";
        }
    }
    cout<<endl;
    delete C;
}

输入：4 2 5 6 2 6 1 7
输出：1 2 2 4 5 6 6 7

注意看这段代码执行后的结果，我们并没有对数组的元素进行排序，输入的结果却是有序的。怎么会这样呢？我们知道数组的所有值都在[0..k]之间，首先记录了每一值出现的次数，然后在从0–>k扫描，输出某个i存在的个数，就输出几个。其实这就是所为的计数排序的主要代码，我们只需要在将输出的排序值，输入到原数组A中，即可，我们已经知道每个值有几个，当然也就可以累加知道每个值在数组排序后在第几位，我们只是需要用一个辅助数组B暂时储存排序值，在复制到原数组中。

代码：

void CountSort(int *A,int n,int k){//这里的K可以使用A中的最大值
    int *B=new int[n+1];//排好序的数组暂时放到B中，再复制到A中
    int *C=new int[k+1];//同上，C[i]记录每一个i出现的次数,初始为0
    memset(C,0,(k+1)*sizeof(int));

    for(int i=1;i<=n;i++){
        C[A[i]]++;
    }
    for(int j=1;j<=k;j++){
        C[j]=C[j]+C[j-1];//此时，C[j]中用来存放小于j的数的个数，
                         //也就是说C[j]现在表示j所在的有序序列下标
    }

    for(int j=n;j>=1;j--){
        B[C[A[j]]]=A[j];
        C[A[j]]--;//可能会有重复元素，每当将一个值A[j]放入数组，
                  //都要减小C[A[j]]的值，这会使下一个等于A[j]的值，
                  //直接进入数组B中的A[j]的前一个位置
    }
    //Copy :B-->A
    for(int i=1;i<=n;i++){
        A[i]=B[i];
    }
    delete B;
    delete C;
}

测试注代码：

int main()
{
    int A[9]={0,4,2,5,6,2,6,1,7};
    //CountPrint(A,8,10);
    PT(A,8);
    CountSort(A,8,10);
    PT(A,8);
    return 0;
}

基数排序：
*基数排序，对于给定的n个d位数进行的排序,
*当然我们可以对任意数排序，不足d位前面补0即可
*什么是基数排序，我们不用担心，下面来看这个例子进行了
*329 720
*457 355
*657 436
*839–按每个数的个位数进行排序->457—->
*436 657
*720 329
*355 839
*
*720 720
*355 329
*436 436
*457–按每个数的十位数进行排序->839—>
*657 355
*329 457
*839 657
*
*720 329
*329 355
*436 436
*839–按每个数的百位数进行排序->457—>
*355 657
*457 720
*657 839
*
*进过3次对每一位数上的数字进行排序，已完成的排序
*这就是基数排序，通过对关键字的基数排序，达到最终排序
*读者可能会问可以从高位到低位进行排序吗？不可以！！
*对于一个数而言，其权位越高对这个数的大小影响越大，
*因此当低位进行排序后，通过高位的排序改变低位排序的
*结果，是合理的，然而如果是通过低位排序改变高位的排序结果
*是不合理的。
*注意：对每一位排序的时候，所有值都在0~9之间，我们可以用到
*计数排序(CountSort)的方法

计数排序辅助排序的代码函数，类似计数排序，也稍有不同，

代码：

void CountSort(int *A,int *T,int n){
    int *B=new int[n+1];//排好序的数组暂时放到B中，再复制到A中
    int *C=new int[10];//同上，C[i]记录每一个i出现的次数,初始为0
    memset(C,0,(10)*sizeof(int));

    for(int i=1;i<=n;i++){
        C[T[i]]++;
    }
    for(int j=1;j<=9;j++){
        C[j]=C[j]+C[j-1];//此时，C[j]中用来存放小于j的数的个数，
                         //也就是说C[j]现在表示j所在的有序序列下标
    }

    for(int j=n;j>=1;j--){
        B[C[T[j]]]=A[j];
        C[T[j]]--;//通过T对A排序,可能会有重复元素，每当将一个值A[j]放入数组，
                  //都要减小C[T[j]]的值，这会使下一个等于A[j]的值，
                  //直接进入数组B中的A[j]的前一个位置
    }
    //Copy :B-->A
    for(int i=1;i<=n;i++){
        A[i]=B[i];
    }
    delete B;
    delete C;

}

基数排序主代码：

/**
 *调用RadixSort(A,n):A[1..n]
 *n个d为数进行排序
 */
void RadixSort(int *A,int n){//
    //为了方便取到每一位的数字，将A[i]写到字符串
    int d=0,x=A[1];
    while(x){//计算每个数的位数d
        d++;
        x/=10;
    }
    //cout<<d<<endl;

    //申请二维数组空间
    char **S=new char*[n+1];
    for(int i=0;i<=n;i++){
        S[i]=new char[d];
    }
    for(int i=1;i<=n;i++){
        sprintf(S[i],"%d",A[i]);
        //printf("%s\n",S[i]);
    }
    --d;
    int *T=new int[n+1];//存储相同位权上的每一位数
    while(d!=-1){//低位到高位模拟排序
        //对[0..9],调用计数排序
        for(int i=1;i<=n;i++){
            T[i]=S[i][d]-‘0‘;
        }
        CountSort(A,T,n);//通过B的顺序对A排序
        for(int i=1;i<=n;i++){//重新将排序的A写入字符串，
                              //因为计数排序与位置有关
            sprintf(S[i],"%d",A[i]);
            //printf("%s\n",S[i]);
        }
        --d;
    }
    delete T;
    for(int i=0;i<=n;i++){
        delete S[i];
    }
    delete S;
}

测试主函数：

int main()
{
    int A[8]={0,329,457,657,839,436,720,355};
    PT(A,7);
    RadixSort(A,7);
    PT(A,7);

    return 0;
}

注：

#define PT(A,n) for(int i=1;i<=n;i++) cout<<A[i]<<" "; cout<<endl;