C语言——计数排序

• 待排序的数组A
• 从数组中取出最大值k
• 新建一个数组B，用于存储排序的输出
• 新建一个数组C，C.length = k+1，用于临时存储空间

原理：
如果A中出现数m的次数为n，则C[m] = n，在依据C对A输出到B中。

实现：

/****************************************************************
 *                              计数排序
 ****************************************************************/


/****************************************************************
 * function     : getMaxIndex
 * description  : 获取数组中最大值
 * input        : int A[],int length
 * output       : N/A
 * return value : int
 * author       : HanyoungXue
 * date         : 2018-4-18
 *****************************************************************/


int getMax(int A[],int length){
    int max = A[0];

    for (int i = 1; i < length; i++) {
        if (A[i]>max){
            max = A[i];
        }
    }
    return max;
}


/*****************************************************************
 * function     : countingSort
 * description  : 计数排序
 * input        : int A[],int B[],int k,int length
 * output       : int B[]
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-18
 ******************************************************************/

void countingSort(int A[],int B[],int k,int length){
    int C[k+1];
    for (int i = 0; i < k+1; ++i) {
        C[i] = 0;
    }

    for (int j = 0; j < length; ++j) {
        C[A[j]]+=1;
    }

    for (int i = 1; i < k+1; ++i) {
        C[i] +=C[i-1];
    }

    for (int j = 0; j < length; ++j) {
        B[--C[A[j]]] = A[j];
    }
}

/**********************************************************
 * function     : print_array
 * description  : 打印一个数组
 * input        : int A[],int length, char *print_string
 * output       : N/A
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-15
 ***********************************************************/

void print_array(int A[],int length,char *print_string){
    printf("%s\n", print_string);
    for (int i = 0; i < length ; ++i){
        printf("%d\t",A[i]);
    }
    printf("\n");
}



void initARandom(int A[],int length){
    srand(time(NULL));
    for (int i = 0; i < length; ++i) {
        A[i] = rand()%60;
    }
}

int main(int argc, char const *argv[])
{
    int length = 12;
    int A[length];
    /*****************************************
     * 计数排序测试
     *****************************************/

    initARandom(A,length);
    print_array(A,length,"before counting sort:");
    int B[length];
    countingSort(A,B,getMax(A,length),length);
    print_array(B,length,"after counting sort:");


    return 0;
}