ソートアルゴリズム(三)



package sort;

public class RadixSort {
	public static void main(String[] args) {
		int A[] = {329,457,657,839,436,720,355};
		radixSort(A, 3);
		for (int j : A) {
			System.out.print(j + " ");
		}
		System.out.println();
	}
	
	public static void radixSort(int A[],int d){
		for(int i = 1;i<=d;i++){
			quickSort(A, i, 0, A.length -1);
		}
	}
	private static void quickSort(int A[],int d,int p,int r){
		if(p < r){
			int j = partition(A, d, p, r);
			
			quickSort(A, d, p, j-1);
			quickSort(A, d, j+1, r);
			
		}
		
	}
	private static int partition(int A[],int d, int p,int r){

		int[][] B = divide(A, d);
		
		int x = B[r][d-1];
		
		int i = p-1;
		
		for(int j = p; j < r;j++){
			if(B[j][d-1] <= x){
				i++;
				
				int temp = A[j];
				A[j] = A[i];
				A[i] = temp;
			}
		}

		int temp = A[r];
		A[r] = A[i+1];
		A[i+1] = temp;
		
		return i+1;
	}
	
	private static int[][] divide(int A[],int d){

		int C[] = new int[A.length];
		for (int k = 0; k < A.length;k++) {
			C[k] = A[k];
		}
		int B[][] = new int[A.length][d];
		for (int i = 0;i<A.length;i++){
			for(int j = 0;j<d;j++){
				B[i][j] = C[i]%10;
				C[i] /= 10;
			}
		}
	
		return B;
	}
}