首页 > 代码库 > 基数排序

基数排序

算法:

1、将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。

2、从最低位开始,依次进行一次排序。

3、这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

01.#include <stdio.h>   
02.#include <stdlib.h>   
03.void radixSort(int data[]) {  
04.    int temp[10][10] = {0};   
05.    int order[10] = {0};   
06.      
07.    int n = 1;   
08.    while(n <= 10) {   
09.          
10.        int i;  
11.        for(i = 0; i < 10; i++) {   
12.            int lsd = ((data[i] / n) % 10);   
13.            temp[lsd][order[lsd]] = data[i];   
14.            order[lsd]++;   
15.        }   
16.          
17.        // 重新排列  
18.        int k = 0;  
19.        for(i = 0; i < 10; i++) {   
20.            if(order[i] != 0)  {  
21.                int j;  
22.                for(j = 0; j < order[i]; j++, k++) {   
23.                    data[k] = temp[i][j];   
24.                }   
25.            }  
26.            order[i] = 0;   
27.        }   
28.        n *= 10;   
29.    }       
30.}  
31.int main(void) {   
32.    int data[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};   
33.        
34.    printf("\n排序前: ");   
35.    int i;  
36.    for(i = 0; i < 10; i++)   
37.        printf("%d ", data[i]);   
38.    putchar(‘\n‘);   
39.    radixSort(data);  
40.      
41.    printf("\n排序後: ");   
42.    for(i = 0; i < 10; i++)   
43.        printf("%d ", data[i]);   
44.    return 0;   
45.}   

 

基数排序