한 걸음 한 걸음 쓰기 알고리즘 (기수 정렬)

【 성명: 판권 소유, 전 재 를 환영 합 니 다. 상업 적 용도 로 사용 하지 마 십시오. 연락처: feixiaoxixing @ 163. com]
기수 정렬 은 다른 비교적 특색 있 는 정렬 방식 인 데 어떻게 정렬 합 니까?우 리 는 아래 의 숫자 에 따라 설명 할 수 있다. 12, 104, 13, 7, 9.
(1) 한 자릿수 순 서 는 12, 13, 104, 7, 9 이다.
(2) 10 위 에 따라 104, 7, 9, 12, 13 순 으로 정렬
(3) 백 자리 순 으로 7, 9, 12, 13, 104
여기 서 주의 하 세 요. 만약 에 한 사람의 숫자 가 같다 면 정렬 결 과 는 지난 라운드 의 배열 에 따라 확정 해 야 합 니 다. 예 를 들 어 07 과 09 는 10 분 에 0 이지 만 지난 라운드 에서 정렬 할 때 09 는 07 뒤에 있 습 니 다.마찬가지 로 예 를 들 어 12 와 13 은 10 분 에 1 이지 만 지난 라운드 12 는 13 앞 에 있 었 기 때문에 10 분 에 정렬 할 때 12 도 13 앞 에 서 야 했다.
그래서 일반적으로 10 기수 정렬 알고리즘 은 이렇게 해 야 합 니까?
(1) 데이터 가 여러분 의 크기 를 판단 하고 데 이 터 를 배열 합 니 다.
(2) 1 의 결과 에 따라 데이터 가 10 분 의 크기 에 있 는 지 판단 하고 데 이 터 를 배열 한다.만약 데이터 가 이 위치 에 있 는 나머지 가 같다 면 데이터 간 의 순 서 는 지난 라운드 의 배열 순서에 따라 확정 된다.
(3) 순서대로 유추 하여 데이터 가 100%, 1000% 에 있 는 지 계속 판단 합 니 다.....................................................................
이렇게 많아여러분 들 이 직접 해 보 셨 으 면 좋 겠 습 니 다.
a) 특정한 위치 에 계 산 된 데이터

int pre_process_data(int array[], int length, int weight)
{
	int index ;
	int value = 1;

	for(index = 0; index < weight; index++)
		value *= 10;

	for(index = 0; index < length; index ++)
		array[index] = array[index] % value /(value /10);

	for(index = 0; index < length; index ++)
		if(0 != array[index])
			return 1;

	return 0;
}

b) 특정한 위치 에 있 는 데 이 터 를 0 ~ 10 으로 정렬 합 니 다.

void sort_for_basic_number(int array[], int length, int swap[])
{
	int index;
	int basic;
	int total = 0;

	for(basic = -9; basic < 10; basic++){
		for(index = 0; index < length; index++){
			if(-10 != array[index] && basic == array[index] ){
				swap[total ++] = array[index];
				array[index] = -10;
			}
		}
	}

	memmove(array, swap, sizeof(int) * length);
}

c) b 의 정렬 결과 에 따라 실제 데 이 터 를 정렬 한다.

void sort_data_by_basic_number(int array[], int data[], int swap[], int length, int weight)
{
	int index ;
	int outer;
	int inner;
	int value = 1;

	for(index = 0; index < weight; index++)
		value *= 10;

	for(outer = 0; outer < length; outer++){
		for(inner = 0; inner < length; inner++){
			if(-10 != array[inner] && data[outer]==(array[inner] % value /(value/10))){
				swap[outer] = array[inner];
				array[inner] = -10;
				break;
			}
		}
	}

	memmove(array, swap, sizeof(int) * length);
	return;
}

d) a, b, c 를 조합 하여 기수 정렬 을 구성 하여 특정한 분 위의 데이터 가 0 일 때 까지 한다.

void radix_sort(int array[], int length)
{
	int* pData;
	int weight = 1;
	int count;
	int* swap;
	if(NULL == array || 0 == length)
		return;

	pData = (int*)malloc(sizeof(int) * length);
	assert(NULL != pData);
	memmove(pData, array, length * sizeof(int));

	swap = (int*)malloc(sizeof(int) * length);
	assert(NULL != swap);

	while(1){
		count = pre_process_data(pData, length, weight);
		if(!count)
			break;

		sort_for_basic_number(pData, length, swap);
		sort_data_by_basic_number(array, pData, swap, length, weight);
		memmove(pData, array, length * sizeof(int));
		weight ++;
	}

	free(pData);
	free(swap);
	return;
}

요약:
(1) 테스트 시 음수 에 주의
(2) 만약 에 특정한 데이터 가 같다 면 이전 데이터 정렬 의 상황 을 고려 해 야 한다.
(3) 코드 에서 여러 번 작은 공간 을 분배 하 는데 이 코드 는 최적화 되 어야 합 니 다.
보충:
(1) 10 월 15 일 저녁 에 나머지 수치 범 위 를 수정 하면 마이너스 도 정렬 에 참가 할 수 있다.
(2) 10 월 16 일 오전 에 swap 메모리 분 배 를 추가 하여 메모리 의 중복 분배 와 방출 을 피 했다.
(3) 10 월 16 일 오전 count 계 수 를 삭 제 했 습 니 다. 0 이 아 닌 데이터 가 발견 되면 1 로 되 돌아 갑 니 다. 모든 데 이 터 를 옮 겨 다 닐 필요 가 없습니다.