当前位置:编程学习 > C/C++ >>

一步一步写算法(之基数排序)

 

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】

 

 

 

 

    基数排序是另外一种比较有特色的排序方式,它是怎么排序的呢?我们可以按照下面的一组数字做出说明:12、104、13、7、9

 

 

    (1)按个位数排序是12、13、104、7、9

 

    (2)再根据十位排序104、7、9、12、13

 

    (3)再根据百位排序7、9、12、13、104

 

    这里注意,如果在某一位的数字相同,那么排序结果要根据上一轮的数组确定,举个例子来说:07和09在十分位都是0,但是上一轮排序的时候09是排在07后面的;同样举一个例子,12和13在十分位都是1,但是由于上一轮12是排在13前面,所以在十分位排序的时候,12也要排在13前面。

 

    所以,一般来说,10基数排序的算法应该是这样的?

 

    (1)判断数据在各位的大小,排列数据;

 

    (2)根据1的结果,判断数据在十分位的大小,排列数据。如果数据在这个位置的余数相同,那么数据之间的顺序根据上一轮的排列顺序确定;

 

    (3)依次类推,继续判断数据在百分位、千分位......上面的数据重新排序,直到所有的数据在某一分位上数据都为0。

 

    说了这么多,写上我们的代码。也希望大家自己可以试一试。

 

    a)计算在某一分位上的数据

 

 

int pre_process_data(int array[], int length, int weight) 

    int index ; 

    int value = 1; 

 

    for(index = 0; index < weight; index++) 

        value *= 10; 

 

    for(index = 0; index < length; index ++) 

        array[index] = array[index] % value /(value /10); 

 

    for(index = 0; index < length; index ++) 

        if(0 != array[index]) 

            return 1; 

 

    return 0;  

int pre_process_data(int array[], int length, int weight)

{

       int index ;

       int value = 1;

 

       for(index = 0; index < weight; index++)

              value *= 10;

 

       for(index = 0; index < length; index ++)

              array[index] = array[index] % value /(value /10);

 

       for(index = 0; index < length; index ++)

              if(0 != array[index])

                     return 1;

 

       return 0;

}    b)对某一分位上的数据按照0~10排序

 

void sort_for_basic_number(int array[], int length, int swap[]) 

    int index; 

    int basic; 

    int total = 0; 

 

    for(basic = -9; basic < 10; basic++){ 

        for(index = 0; index < length; index++){ 

            if(-10 != array[index] && basic == array[index] ){ 

                swap[total ++] = array[index]; 

                array[index] = -10; 

            } 

        } 

    } 

 

    memmove(array, swap, sizeof(int) * length); 

void sort_for_basic_number(int array[], int length, int swap[])

{

       int index;

       int basic;

       int total = 0;

 

       for(basic = -9; basic < 10; basic++){

              for(index = 0; index < length; index++){

                     if(-10 != array[index] && basic == array[index] ){

                            swap[total ++] = array[index];

                            array[index] = -10;

                     }

              }

       }

 

       memmove(array, swap, sizeof(int) * length);

}

 

 

    c)根据b中的排序结果,对实际的数据进行排序

 

void sort_data_by_basic_number(int array[], int data[], int swap[], int length, int weight) 

    int index ; 

    int outer; 

    int inner; 

    int value = 1; 

 

    for(index = 0; index < weight; index++) 

        value *= 10; 

 

    for(outer = 0; outer < length; outer++){ 

        for(inner = 0; inner < length; inner++){ 

            if(-10 != array[inner] && data[outer]==(array[inner] % value /(value/10))){ 

                swap[outer] = array[inner]; 

                array[inner] = -10; 

                break; 

            } 

        } 

    } 

 

    memmove(array, swap, sizeof(int) * length); 

    return; 

void sort_data_by_basic_number(int array[], int data[], int swap[], int length, int weight)

{

  &nb

补充:软件开发 , C语言 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,