程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於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)

{

       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;

}

 

    d)把a、b、c組合起來構成基數排序,直到某一分位上的數據為0

 

 

void radix_sort(int array[], int length) 

    int* pData; 

    int weight = 1; 

    int count; 

    int* swap; 

    if(NULL == array || 0 == length) 

        return; 

 

    pData = (int*)malloc(sizeof(int) * length); 

    assert(NULL != pData); 

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

 

    swap = (int*)malloc(sizeof(int) * length); 

    assert(NULL != swap); 

 

    while(1){ 

        count = pre_process_data(pData, length, weight); 

        if(!count) 

            break; 

 

        sort_for_basic_number(pData, length, swap); 

        sort_data_by_basic_number(array, pData, swap, length, weight); 

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

        weight ++; 

    } 

 

    free(pData); 

    free(swap); 

    return; 

void radix_sort(int array[], int length)

{

       int* pData;

       int weight = 1;

       int count;

       int* swap;

       if(NULL == array || 0 == length)

              return;

 

       pData = (int*)malloc(sizeof(int) * length);

       assert(NULL != pData);

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

 

       swap = (int*)malloc(sizeof(int) * length);

       assert(NULL != swap);

 

       while(1){

              count = pre_process_data(pData, length, weight);

              if(!count)

                     break;

 

              sort_for_basic_number(pData, length, swap);

              sort_data_by_basic_number(array, pData, swap, length, weight);

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

              weight ++;

       }

 

       free(pData);

       free(swap);

       return;

}

 

 

總結:

 

    (1)測試的時候注意負數的情形

 

    (2)如果在某一位數據相同,那麼需要考慮上一輪數據排序的情況

 

    (3)代碼中多次分配小空間,此處代碼待優化

 

 

 

 

 

補充:

 

    (1)10月15日晚上修改了余數取值范圍,這樣負數也可以參加排序

 

    (2)10月16日上午增加了一個swap內存分配,避免了內存的重復分配和釋放

 

    (3)10月16日上午刪除了count計數,一旦發現有不等於0的數據直接返回為1,不需要全部遍歷數據

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved