[정렬] 기수정렬 ( Radix Sort )

int get_Max_radix(vector<int> &v, int n) {// 가장 큰 값을 찾고 그 값의 자릿수 리턴
	int max_val = 0;
	int i;
	for (i = 0;i < n;i++) {
		if (max_val < v[i]) max_val = v[i];
	}
	int max_radix = 1;
	while (max_val / 10 > 0) {
		max_val /= 10;
		max_radix *= 10;
	}
	return max_radix;
}

void radixSort(vector<int>& v, int n) {
	int max_radix = get_Max_radix(v, n);
	queue<int> q[10];//0~9

	for (int i = 1; i <= max_radix;i*=10) {//자릿수 값을 증가시키면서 정렬순회
		for (int j = 0;j < n;j++) {
			int k = 0;// 자리수
			if (v[j] >= i) k = (v[j] / i) % 10;
			q[k].push(v[j]);
		}
		int idx = 0;
		for (int j = 0;j < 10;j++) {
			while (!q[j].empty()) {
				v[idx] = q[j].front();
				q[j].pop();
				idx++;
			}
		}
	}
}

제자리성 : 제자리 정렬 x (추가 자료구조 사용)

 

안정성 : 안정 (순서대로 뒤쪽 레코드 부터 가장 뒤쪽에 배치)

 

시간 복잡도

평균 시간복잡도 = O(n)

 

음수에는 사용 불가능