정렬 알고리즘 (4) 기수 정렬

이 블 로 그 는 순서 표를 바탕 으로 LSD, MSD 를 실현 하 는 두 가지 방식 을 소개 한다.
기본 적 인 사고: 배열 에서 가장 큰 값 의 자릿수 를 보 세 요. 예 를 들 어 최대 치 는 999 입 니 다. 바로 세 명의 K1K2K 3 입 니 다. 먼저 K3 에 따라 배열 을 스 캔 하고 K3 자리 가 0 인 개 수 를 기록 하 며 1 인 개 수 를 기록 합 니 다.........................................................................
계산 시작 주소: addr [idx] = addr [idx - 1] + count [idx - 1], 다시 스 캔 배열 은 addr 의 시작 위치 에 따라 원 소 를 순서대로 분류 합 니 다.
예 를 들 어 서열: 278, 109, 063, 930, 589, 184, 505, 269, 008, 083    0  1  2  3  4  5  6  7  8  9 count[]:1  0  0  2  1  1  0  0  2  3 Addr[] :0  1  1  1  3  4  5  5  5  7
첫 번 째 정렬 (개 비트): 278 을 예 로 들 어 addr [8] 를 5 로 하고 요 소 를 278 을 배열 5 번 위치 에 놓 은 다음 에 addr [8] + +
(1) LSD: 가장 낮은 자리 부터 정렬 하고 위의 동작 을 순환 하 며 높 은 위 치 를 정렬 한 다음 에 가장 높 은 위 치 를 정렬 합 니 다.
코드:

int GetMaxBit(int *arr,size_t size) //        
{
	int count = 0;
	int radix = 1;
	for (size_t i = 0; i < size; ++i)
	{
		while (arr[i] > radix)
		{
			count++;
			radix *= 10;
		}
	}
	return count;
}
void RadixSortLSD(int *arr, size_t size) //        
{
	size_t MaxBit = GetMaxBit(arr, size);
	int radix = 1;
	int* bucket = new int[size];
	for (size_t BitIdx = 1; BitIdx <= MaxBit; ++BitIdx)
	{

		//               
		int count[10] = { 0 };
		for (size_t idx = 0; idx < size; ++idx)
		{
			count[arr[idx]/radix % 10]++;
		}

		//          :          +          
		int Addr[10] = { 0 };
		for (size_t j = 1; j < 10; ++j)
		{
			Addr[j] = Addr[j - 1] + count[j - 1];
		}
		//    ，  

		for (size_t index = 0; index < size; ++index)
		{
			int k = arr[index] / radix % 10;//  
			bucket[Addr[k]] = arr[index];
			Addr[k]++;
		}
		memcpy(arr, bucket, size*sizeof(bucket[0]));
		radix *= 10;		
	}
	delete[] bucket;
}

(2) MSD 가 가장 높 은 위치 로 정렬 하 는 것 은 재 귀 과정 이다.
   ① 가장 높 은 위 치 를 정렬 하여 count [] 배열 중 1 이상 을 찾 아 라.
   ② 개수 가 1 보다 많은 것 을 다시 정렬 합 니 다.최 하위 까지.
코드 에 설명 이 있 습 니 다:

void _RadixSortMSD(int *arr, size_t left, size_t right, int* bucket, int bit) //[)
{
	if (bit == 0)
		return;
	int radix = (int)pow(10,bit -1);

	//   (   )            
	int count[10] = { 0 };
	for (size_t idx = left; idx < right; ++idx)
	{
		count[arr[idx] / radix % 10]++;
	}

	//          :          +          
	int Addr[10] = { 0 };
	for (size_t j = 1; j < 10; ++j)
	{
		Addr[j] = Addr[j - 1] + count[j - 1];
	}
	//    ，  

	for (size_t index = left; index < right; ++index)
	{
		int k = arr[index] / radix % 10;//  
		bucket[left + Addr[k]] = arr[index];
		Addr[k]++;
	}
	memcpy(arr + left, bucket + left, (right - left)*sizeof(bucket[0]));

	//  count         1   
	size_t m = 0;
	for (; m < 10; ++m)
	{
		if (count[m] <= 1)
			continue;
		else
		{
			int begin = left + Addr[m] - count[m];
			int end = begin + count[m];
			_RadixSortMSD(arr, begin, end, bucket, bit - 1);
		}
	}
	
}


void RadixSortMSD(int *arr,size_t size)
{
	size_t bit = GetMaxBit(arr, size);
	int * bucket = new int[size];
	_RadixSortMSD(arr, 0, size, bucket, bit);
	delete[] bucket;
}