[알고리즘 학습] 선형 시간 정렬 - 계수 정렬, 기수 정렬 과 통 정렬 상세 및 프로 그래 밍 실현

계수 정렬
계수 정렬 은 n 개의 입력 요소 중 하나 가 0 에서 k 사이 의 정수 라 고 가정 합 니 다.이 곳 k 는 특정한 정수 입 니 다. (입력 데 이 터 는 작은 범위 내 에 있 습 니 다.)
알고리즘 사상
계수 정렬 의 기본 사상 은 모든 입력 요소 x 에 대해 x 보다 작은 요소 의 개 수 를 확정 하 는 것 이다.그리고 x 를 최종 출력 배열 의 위치 에 직접 놓 습 니 다.
배열 에 같은 수가 있 을 수 있 으 므 로 처리 할 때 주의해 야 합 니 다.
시간 복잡 도와 공간 복잡 도 분석
알고리즘 총 시간Θ(k + n)。k = O (n) 일 때 정렬 된 운행 시간 은?Θ(n)。
공간 복잡 도 는 O (n + k) 입 니 다.두 개의 보조 배열 이 필요 합 니 다. 정렬 결 과 를 저장 하 는 배열 B [n], 임시 결 과 를 저장 하 는 C [k].
계수 정렬 은 안정 적 인 정렬 알고리즘 이다.
프로 그래 밍 구현 (CPP)

//    -《    （   ）》P98 8.2    
//Author：    
//E-Mail：[email protected]

#include 
#include 

using namespace std;

void CountSort(int *a,const int num,int *result)
{
	int MaxVal = -99999;
	for(int i = 0;i < num;++i)
	{
		if(MaxVal < *(a + i))
			MaxVal = *(a + i);
	}
	int *tempResult = new int[MaxVal + 5];//      
	for(int i = 0;i < MaxVal  + 5;++i)
		*(tempResult + i) = 0;
	//result[i]        i      
	for(int i = 0;i < num;++i)
		*(tempResult + *(a + i)) = *(tempResult + *(a + i)) + 1;
	//result[i]          i      
	for(int i = 1;i < MaxVal + 5;++i)
		*(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1);
	//  ，            
	//                
	for (int i = num - 1;i >= 0;--i)
	{
		*(result + *(tempResult + *(a + i))) = *(a + i);
		*(tempResult + *(a + i)) = *(tempResult + *(a + i)) - 1;
	}

	delete[] tempResult;
}

int main()
{
	 int num = 7;
	int *a = new int[num];
	for(int i = 0;i < num;++i)
		*(a + i) = rand();

	cout << "Before sort: " << endl;
	for(int i = 0;i < num;++i)
		cout << *(a + i) << " ";
	cout << endl;

	int *result = new int[num + 5];

	CountSort(a,num,result);

	cout << "After sort: " << endl;
	for(int i = 1;i <= num;++i)
		cout << *(result + i) << " ";
	cout << endl;

	delete[] a;
	delete[] result;
}

기수 정렬
알고리즘 사상
기수 정렬 은 낮은 위치 에서 높 은 위치 로 모든 수 를 순서대로 정렬 하 는 것 이다.모든 수의 최고 자릿수 가 d 라면 가장 낮은 유효 비트 숫자 에 따라 정렬 하여 결 과 를 얻 을 수 있 습 니 다.그리고 높 은 자리 로 이 과정 을 반복 한다.
주의해 야 할 것 은 위치 에 따라 정렬 하 는 것 이 안정 적 인 정렬 알고리즘 이 어야 한 다 는 것 이다.자주 사용 하 는 것 은 계수 정렬 이다.
프로 그래 밍 구현 (CPP)

//    
//《    （   ）》P100 8.3     
//Author：    
//E-Mail:[email protected]

#include 
#include 
#include 

using namespace std;

//       i    
int getDigitNun(int a,int digit);
//    
void DigitSort(int *a,int n,int digit,int *result);
//      
void RadixSort(int *a,int n,int d);

int main()
{
	int n = 7,i;
	int *a = new int[n];
	srand(time(NULL));
	for(i = 0;i < n;++i)
		*(a + i) = rand();
	//         
	int MaxVal = -1,d = 0;
	cout << "Before sort : " << endl;
	for(i = 0;i < n;++i)
	{
		cout << *(a + i) << " ";
		MaxVal = MaxVal < *(a + i) ? *(a + i) : MaxVal;
	}
	cout << endl;
	while(MaxVal > 0)
	{
		++d;
		MaxVal /= 10;
	}

	RadixSort(a,n,d);

	cout << "After sort : " << endl;
	for(i = 0;i < n;++i)
		cout << *(a + i) << " ";
	cout << endl;
}

//      
void RadixSort(int *a,int n,int d)
{
	int *result = new int[n + 5];
	//          
	for (int i =1;i <= d;++i)
	{
		DigitSort(a,n,i,result);
		for (int j = 0;j < n;++j)
		{
			*(a + j) = *(result + j + 1);
		}
	}

	delete[] result;
}

//       i    
int getDigitNun(int a,int digit)
{
	while(--digit)
	{
		a /= 10;
	}

	return a % 10;
}

//    
//        
void DigitSort(int *a,int n,int digit,int *result)
{
	//      
	const int num = 15;
	int *tempResult = new int[num];
	for(int i = 0;i < num;++i)
		*(tempResult + i) = 0;//   

	//tempResult[i]       i     
	for(int i = 0;i < n;++i)
		*(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) + 1;

	//tempResult[i]         i     
	for(int i = 1;i < num;++i)
		*(tempResult + i) = *(tempResult + i) + *(tempResult + i - 1);

	//             
	for(int i = n - 1;i >= 0;--i)
	{
		*(result + *(tempResult + getDigitNun(*(a + i),digit))) = *(a + i);
		*(tempResult + getDigitNun(*(a + i),digit)) = *(tempResult + getDigitNun(*(a + i),digit)) - 1;
	}

	delete[] tempResult;
}

시간 복잡 도와 공간 복잡 도 분석
n 개의 d 비트 를 지정 합 니 다. 모든 비트 는 k 를 추출 할 수 있 습 니 다. 만약 에 사용 하 는 안정 적 인 비트 별 정렬 시간 복잡 도 는?Θ(n + k), 기수 정렬 시간 복잡 도 는?Θ(d(n+k))。공간 복잡 도 O (n + k).
d 가 상수 이 고 k = O (n) 일 때 기수 정렬 은 선형 시간 복잡 도가 있다.
모든 키 워드 를 몇 개의 숫자 로 분해 하 는 방법 에 대해 또 다른 정리 가 있 습 니 다.
n 개의 b 차원 수 와 그 어떠한 정수 r < = b 를 지정 하면 기수 정렬 은Θ(b / r) (n + 2 ^ r) 시간 내 에 이 숫자 들 을 정렬 합 니 다.
여기 서 하나의 값 r < = b 에 대해 모든 키 워드 를 d = floor (b / r) 개의 숫자 로 보고 모든 숫자 에 r 비트 를 포함 한 다음 에 계산 정렬 을 합 니 다.
상술 한 식 은 유도 할 수 있다.Θ복잡 도
그러나 이것 은 기수 정렬 이 비교 에 기반 한 정렬 알고리즘, 예 를 들 어 빠 른 정렬 보다 더 좋다 는 것 을 의미 하지 않 는 다!기호 에 포 함 된 상수 인 자 는 다 르 기 때문이다.어떤 정렬 알고리즘 이 더 좋 은 지 는 바 텀 기기 의 실현 특성 에 달 려 있다. 예 를 들 어 빠 른 배열 = 배열 은 보통 하드웨어 캐 시 를 더욱 효과적으로 이용 할 수 있다.입력 데이터 에 도 달 려 있다.그리고 계수 순 서 를 중간 으로 안정 적 으로 정렬 하 는 것 은 제자리 정렬 이 아니다.
통 정렬
입력 데이터 가 균일 분포 에 부합 할 때 선형 기대 시간 으로 운행 할 수 있다.입력 이 선형 관 계 를 만족 시 키 지 않 더 라 도 통 정렬 은 선형 시간 으로 실 행 될 수 있다.이러한 성질 을 만족 시 키 기만 하면 각 통 사이즈 의 제곱 과 전체 원소 수 는 선형 관 계 를 나타 낸다.
통 정렬 사상:
구간 [0, 1) 을 n 개의 같은 크기 의 하위 구간 으로 나 누 거나 통 이 라 고 부 릅 니 다. 그리고 n 개의 입력 요 소 를 각 통 에 분포 합 니 다. 각 통 의 요 소 는 하나의 링크 로 저장 합 니 다.
프로 그래 밍 구현 (CPP)

//   
//《    （   ）》P102 8.4    
//Author：    （2013-03027）
//E-Mail:[email protected]

#include 
#include 
#include 
#include 

using namespace std;

//          
typedef struct StructLinkNode{
	double elem;
	struct StructLinkNode *next;
}LinkNode,*LinkNodePtr;

//   
void BucketSort(double *a,int n);
//      
void deleteLinkList(LinkNodePtr head);

int main()
{
	srand(time(NULL));
	int n = 8;
	double *a = new double[n];
	for(int i = 0;i < n;++i)
		*(a + i) = rand() * 1.0 / RAND_MAX;

	cout << "Before sort : " << endl;
	for(int i = 0;i < n;++i)
		cout << *(a + i) << "  ";
	cout << endl;

	BucketSort(a,n);

	cout << "After sort : " << endl;
	for(int i = 0;i < n;++i)
		cout << *(a + i) << "  ";
	cout << endl;
}

//   
void BucketSort(double *a,int n)
{
	//       
	LinkNodePtr *linkListArr = new LinkNodePtr[n];
	//   
	for (int i = 0;i < n;++i)
	{
		linkListArr[i] = new LinkNode;
		linkListArr[i]->elem = -1;
		linkListArr[i]->next = NULL;
	}

	// n         n   
	for (int i = 0;i < n;++i)
	{
		LinkNodePtr newNode = new LinkNode;
		newNode->elem = *(a + i);
		newNode->next = NULL;

		//                 
		int index = floor(n * *(a + i));
		LinkNodePtr loopPtr = linkListArr[index]->next;
		LinkNodePtr prevPtr = linkListArr[index];
		while(loopPtr != NULL && *(a + i) > loopPtr->elem)
		{
			prevPtr = loopPtr;
			loopPtr = loopPtr->next;
		}
		newNode->next = loopPtr;
		prevPtr->next = newNode;
	}

	int count = 0;
	for (int i = 0;i < n;++i)
	{
		LinkNodePtr loopPtr = linkListArr[i]->next;
		while(loopPtr != NULL)
		{
			*(a + count) = loopPtr->elem;
			++count;
			loopPtr = loopPtr->next;
		}
	}

	for (int i = 0;i < n;++i)
		deleteLinkList(linkListArr[i]);
}

//      
void deleteLinkList(LinkNodePtr head)
{
	if (NULL == head)
	{
		return;
	}
	deleteLinkList(head->next);
	delete head;
}

시간 과 공간 복잡 도 분석
시간 복잡 도 는 O (n) 이다.
공간 복잡 도 는 O (n) 입 니 다. 통 (링크) 을 저장 하기 위해 보조 배열 이 필요 합 니 다.
입력 이 균일 한 분 포 를 만족 시 키 지 못 하 더 라 도 통 의 순 서 는 선형 시간 으로 운행 할 수 있다. 이러한 조건 을 만족 시 키 기만 하면 각 통 사이즈 의 제곱 과 전체적인 요 소 는 선형 관 계 를 나타 낸다.
통 정렬 은 안정 적 인 정렬 알고리즘 이다.