[알고리즘 학습] 선형 시간 정렬 - 계수 정렬, 기수 정렬 과 통 정렬 상세 및 프로 그래 밍 실현
7745 단어 데이터 구조 와 알고리즘
계수 정렬 은 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) 입 니 다. 통 (링크) 을 저장 하기 위해 보조 배열 이 필요 합 니 다.
입력 이 균일 한 분 포 를 만족 시 키 지 못 하 더 라 도 통 의 순 서 는 선형 시간 으로 운행 할 수 있다. 이러한 조건 을 만족 시 키 기만 하면 각 통 사이즈 의 제곱 과 전체적인 요 소 는 선형 관 계 를 나타 낸다.
통 정렬 은 안정 적 인 정렬 알고리즘 이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.