기수정렬 구현

1 C++

#include<iostream>
using namespace std;
void count_sort(int arr[], int size, int exp) {
	int i, index, output[size], count[10] = {0};
	for(i=0; i<size; i++) count[(arr[i]/exp)%10]++;
	for(i=1; i<10; i++) count[i] += count[i-1];
	for(i=size-1; i>-1; i--) {
		index = arr[i]/exp;
		output[count[index%10]-1] = arr[i];
		count[index%10]--;
	}
	for(i=0; i<size; i++) arr[i] = output[i];
}
void radix_sort(int arr[], int size) {
	int max = arr[0];
	for(int i=1; i<size; i++) if(arr[i]>max) max=arr[i];	
	for(int exp=1; max/exp>0; exp*=10) count_sort(arr, size, exp);
}
int main() {
	int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
	int size = sizeof(arr)/sizeof(arr[0]);
	radix_sort(arr, size);
	for(int i=0; i<size; i++) cout << arr[i] << " ";
	// 0 1 2 3 4 5 6 7 8 9 10 100 
}

2 Java

Java 기수정렬 구현 문서를 참고하십시오.

import java.util.Collections;
import java.util.Arrays;
public class MyClass {
    static void radix_sort(Integer a[]) {
        radix_sort(a, 10);
    }
    static void radix_sort(Integer a[], int base) {
        int max = Collections.max(Arrays.asList(a));
        int exp, i, j, size = a.length;
        for(exp=1; exp<=max; exp*=base) {
            int count[] = new int[base];
            int output[] = new int[size];
            for(i=0; i<size; i++) count[(a[i]/exp)%base]++;
            for(i=1; i<base; i++) count[i]+=count[i-1];
            for(i=size-1; i>-1; i--) {
                j = (a[i]/exp)%base;
                output[count[j]-1] = a[i];
                count[j]--;
            }
            for(i=0; i<size; i++) a[i]=output[i];
        }
    }
    public static void main(String args[]) {
		Integer arr[] = {9,1,22,4,0,1,22,100,10};
		radix_sort(arr);
		for(int x: arr) System.out.format("%d ",x);
		// 0 1 1 4 9 10 22 22 100 
    }
}

3 PHP

PHP 기수정렬 구현 문서를 참고하십시오.

<?php
function radix_sort(&$a, $base=10) {
    $maxval = max($a);
    $size = count($a);
    for($exp=1; $exp<=$maxval; $exp*=$base) {
    	$count = array_fill(0,$base,0);
    	$output = array_fill(0,$size,0);
    	for($i=0; $i<$size; $i++) {
    	    $index = intdiv($a[$i],$exp);
    		$count[$index%$base]++;
    	}
    	for($i=1; $i<$base; $i++) $count[$i]+=$count[$i-1];
    	for($i=$size-1; $i>-1; $i--) {
    		$index = intdiv($a[$i],$exp);
    		$output[$count[$index%$base]-1] = $a[$i];
    		$count[$index%$base]--;
    	}
    	for($i=0; $i<$size; $i++) $a[$i]=$output[$i];
    }
}
$arr = [9,1,22,4,0,1,22,100,10];
radix_sort( $arr );
print( implode(' ',$arr) );
# 0 1 1 4 9 10 22 22 100

4 Python

Python 기수정렬 구현 문서를 참고하십시오.

def radix_sort(a, base=10):
    from math import log
    size = len(a)
    for i in range(int(log(max(a),base))+1):
        exp = base ** i
        output = [0]*size
        count = [0]*base
        for i in range(size):
        	index = int(a[i]/exp)
        	count[index%base] += 1
        for i in range(1,base): count[i]+=count[i-1]
        for i in range(size-1,-1,-1):
        	index = int(a[i]/exp)
        	output[count[index%base]-1] = a[i]
        	count[index%base] -= 1
        for i in range(size): a[i]=output[i]
arr = [9,1,22,4,0,1,22,100,10]
radix_sort( arr )
print( arr )
# [0, 1, 1, 4, 9, 10, 22, 22, 100]

5 같이 보기

6 참고

https://www.geeksforgeeks.org/radix-sort/