排序算法測試-基數排序

1、測試代碼

#include <iostream>

using namespace std;
int g_loop = 0;    /* 循環計數 */
int g_move = 0;    /* 資料移動次數 */

void output_info(int *buff,int len, int flag)
{
    int i;

    if(0 == flag)
    {
        cout << "before: ";
    }
    else
    {
        cout << "after:  ";
    }

    for(i = 0; i < len; ++i)
    {
        cout << *(buff + i) << " ";
    }

    cout << endl;
}

/* 擷取一個數的倒數第i位數字 */
int get_num(int num, int i)
{
    int temp;
    int base = 1;

    if(i <= 0)
    {
        return num;
    }

    while (--i)
    {
        base *= 10;
    }

    return num / base % 10;
}

void clean_barrel(int arr[],int **barrel,int pos[])
{
    int i,j,k;

    k = 0;
    for ( i = 0; i < 10; ++i)
    {
        for ( j = 0; j < pos[i]; ++j)
        {
            arr[k++] = barrel[i][j];
        }

        pos[i] = 0;
    }
}

/* 基數排序 */
void radix_sort(int arr[], int len)
{
    int max;
    int min;
    int i,j;
    int temp;
    int width = 1;
    int *barrel[10];   /* 桶指針 */
    int pos[10] = {0}; /* 儲存數組索引值 */

    max = min = arr[0];
    for(i = 1; i < len; ++i)
    {
        if(arr[i] > max)
        {
            max = arr[i];
        }

        if(arr[i] < min)
        {
            min =  arr[i];
        }
    }

    cout << "min=" << min << endl;
    cout << "max=" << max << endl;

    /* 計算最大數位數 */
    while (max / 10)
    {
        ++width;
        max /= 10;
    }

    cout << "width=" << width << endl;

    // 建立10個桶
    for(i = 0; i < 10; ++i)
    {
        barrel[i] =  new int[len]();
    }

    // 進行每一趟的排序，從個位數開始排
   for (i = 1; i <= width; ++i)
   {
       cout << "=====================" << endl;
       cout << "bit=" << i << endl;

       for (j = 0; j < len; ++j)
       {
           ++g_loop;

           // 擷取倒數第 i 位數
           temp = get_num(arr[j], i);

           barrel[temp][pos[temp]++] = arr[j];

           cout << "bucket=" << temp <<  " pos="<< pos[temp] << endl;
           output_info(barrel[temp], len, 1);
           cout << endl;
       }

       // 取出桶中的資料放回原數組
       cout << "==loop " << i << endl;
       output_info(arr, len, 0);
       clean_barrel(arr,barrel,pos);
       output_info(arr, len, 1);

       cout << endl;
   }

   // 釋放桶資源
   for(i = 0; i < 10; ++i)
   {
       delete[] barrel[i];
   }
}

int main(void)
{
    int array[10]= {20,190,18,1700,151,15,4,13,10,1};
    int len = sizeof(array) / sizeof(array[0]);

    radix_sort(array, len);

    cout << endl;
    output_info(array, len, 1);
    cout << "move=" << g_move << endl;
    cout << "loop=" << g_loop << endl;

    return 0;
}
           

2、測試log 

min=1
max=1700
width=4
=====================
bit=1
bucket=0 pos=1
after:  20 0 0 0 0 0 0 0 0 0

bucket=0 pos=2
after:  20 190 0 0 0 0 0 0 0 0

bucket=8 pos=1
after:  18 0 0 0 0 0 0 0 0 0

bucket=0 pos=3
after:  20 190 1700 0 0 0 0 0 0 0

bucket=1 pos=1
after:  151 0 0 0 0 0 0 0 0 0

bucket=5 pos=1
after:  15 0 0 0 0 0 0 0 0 0

bucket=4 pos=1
after:  4 0 0 0 0 0 0 0 0 0

bucket=3 pos=1
after:  13 0 0 0 0 0 0 0 0 0

bucket=0 pos=4
after:  20 190 1700 10 0 0 0 0 0 0

bucket=1 pos=2
after:  151 1 0 0 0 0 0 0 0 0

==loop 1
before: 20 190 18 1700 151 15 4 13 10 1
after:  20 190 1700 10 151 1 13 4 15 18

=====================
bit=2
bucket=2 pos=1
after:  20 0 0 0 0 0 0 0 0 0

bucket=9 pos=1
after:  190 0 0 0 0 0 0 0 0 0

bucket=0 pos=1
after:  1700 190 1700 10 0 0 0 0 0 0

bucket=1 pos=1
after:  10 1 0 0 0 0 0 0 0 0

bucket=5 pos=1
after:  151 0 0 0 0 0 0 0 0 0

bucket=0 pos=2
after:  1700 1 1700 10 0 0 0 0 0 0

bucket=1 pos=2
after:  10 13 0 0 0 0 0 0 0 0

bucket=0 pos=3
after:  1700 1 4 10 0 0 0 0 0 0

bucket=1 pos=3
after:  10 13 15 0 0 0 0 0 0 0

bucket=1 pos=4
after:  10 13 15 18 0 0 0 0 0 0

==loop 2
before: 20 190 1700 10 151 1 13 4 15 18
after:  1700 1 4 10 13 15 18 20 151 190

=====================
bit=3
bucket=7 pos=1
after:  1700 0 0 0 0 0 0 0 0 0

bucket=0 pos=1
after:  1 1 4 10 0 0 0 0 0 0

bucket=0 pos=2
after:  1 4 4 10 0 0 0 0 0 0

bucket=0 pos=3
after:  1 4 10 10 0 0 0 0 0 0

bucket=0 pos=4
after:  1 4 10 13 0 0 0 0 0 0

bucket=0 pos=5
after:  1 4 10 13 15 0 0 0 0 0

bucket=0 pos=6
after:  1 4 10 13 15 18 0 0 0 0

bucket=0 pos=7
after:  1 4 10 13 15 18 20 0 0 0

bucket=1 pos=1
after:  151 13 15 18 0 0 0 0 0 0

bucket=1 pos=2
after:  151 190 15 18 0 0 0 0 0 0

==loop 3
before: 1700 1 4 10 13 15 18 20 151 190
after:  1 4 10 13 15 18 20 151 190 1700

=====================
bit=4
bucket=0 pos=1
after:  1 4 10 13 15 18 20 0 0 0

bucket=0 pos=2
after:  1 4 10 13 15 18 20 0 0 0

bucket=0 pos=3
after:  1 4 10 13 15 18 20 0 0 0

bucket=0 pos=4
after:  1 4 10 13 15 18 20 0 0 0

bucket=0 pos=5
after:  1 4 10 13 15 18 20 0 0 0

bucket=0 pos=6
after:  1 4 10 13 15 18 20 0 0 0

bucket=0 pos=7
after:  1 4 10 13 15 18 20 0 0 0

bucket=0 pos=8
after:  1 4 10 13 15 18 20 151 0 0

bucket=0 pos=9
after:  1 4 10 13 15 18 20 151 190 0

bucket=1 pos=1
after:  1700 190 15 18 0 0 0 0 0 0

==loop 4
before: 1 4 10 13 15 18 20 151 190 1700
after:  1 4 10 13 15 18 20 151 190 1700


after:  1 4 10 13 15 18 20 151 190 1700
move=0
loop=40
           

3、算法分析 

• 非原地排序算法；
• 穩定排序算法；
• 空間複雜度 O（n+k）；
• 時間複雜度 O（kn）。