기본 정렬 계열 의 계수 정렬

약술 계수 정렬
              많은 사람들 이 쓴 계산 순 서 를 보고 오랫동안 알 아 보지 못 했 습 니 다. 오 랜 만 에 이렇게 간단 한 데 몇 시간 이 걸 렸 다 는 것 을 알 게 되 었 습 니 다. 그래서 여기에 저 와 같은 초보 자 들 이 더 이상 길 을 돌 지 않 았 으 면 좋 겠 다 고 썼 습 니 다.
1. 계산 정렬 의 사상 을 약술 한다.
         정렬 된 배열 을 A 로 설정 하고 정렬 한 후에 B, C 를 임시 배열 로 저장 합 니 다.계산 이란 먼저 하나의 배열 C [i] 를 통 해 크기 가 i 와 같은 요소 의 개 수 를 계산 하 는 것 입 니 다. 이 과정 은 한 번 의 순환 으로 옮 겨 다 니 면 됩 니 다.이 를 바탕 으로 i 보다 작 거나 같은 요소 의 개 수 를 계산 하 는 것 도 반복 하면 완성 된다.다음 단 계 는 관건 이다. 역순 으로 순환 하고 length [A] 에서 1 까지 A [i] 를 B 중 C [A [i] 의 위치 에 놓는다.원 리 는 C [A [i] 는 a [i] 와 같은 요소 의 개 수 를 나타 내 는데 바로 A [i] 가 정렬 한 후에 있어 야 할 위치 이다.또한 length [A] 에서 1 역순 으로 순환 하면 같은 요소 간 의 상대 적 인 순서 가 변 하지 않 는 것 도 계수 정렬 안정성 의 표현 이다.배열 A 에 부속품 속성 이 있 을 때 안정성 이 매우 중요 하 다.
2. 약술:
         사실 계수 정렬 은 대량의 메모리 공간 을 낭비 하고 음수 의 서열 에 대해 여기 서 토론 하 는 것 도 해결 할 수 없 는 문제 이 며 정렬 된 서열 의 책 은 0 - k 사이 에 있어 야 하지만 그 알고리즘 은 복잡 도가 작은 O (n + k) 즉 알고리즘 의 복잡 도 이 며 이 알고리즘 은 안정 적 인 알고리즘 이다.우리 가 정렬 을 하 는 데 는 두 가지 상황 이 있 는데, 하 나 는 중복 되 지 않 은 수의 정렬 이 고, 다른 하 나 는 이런 상황 이 있다.
         위 에서 말 한 것 은 알 아 볼 수 없 는 것 입 니 다. 보통 점 은 a [10] = {2, 2, 3, 4, 5, 6, 7, 9, 0, 6} 과 같은 배열 을 만 드 는 것 입 니 다. 우 리 는 임시 배열 을 만들어 서 저장 하 는 것 입 니 다. 또한 이 알고리즘 의 조작 경전 입 니 다. 즉, 우 리 는 c [k] 와 같은 배열 을 만 듭 니 다. 여기 서 k 는 조건 이 바로 이 알고리즘 을 사용 하려 면 반드시 만족 해 야 하 는 조건 을 표시 합 니 다.그러면 배열 a 의 요 소 는 모두 0 - k 사이 에 있어 야 한 다 는 것 이다.우 리 는 배열 c 아래 표 시 를 통 해 우리 가 정렬 해 야 할 배열 a 의 요 소 를 기록 한 다음 에 출력 으로 이 아래 표 시 를 기록 하면 됩 니 다.만약 중복 되 지 않 은 서열 에 대해 우 리 는 이러한 배열 의 서열 을 쉽게 얻 을 수 있다. 예 를 들 어 a [5] = {2, 4, 6, 7, 9, 0}
아래 표
0
1
2
3
4
5
6
7
8
9
배열 c
1
0
1
0
1
0
1
1
0
1
아래 표 시 를 떼 어 정렬 한 후
0
2
4
6
7
9
그리고 우 리 는 정렬 된 숫자 를 새로운 숫자 b [5] = {0, 0, 0, 0, 0, 0} 에 넣 을 것 이다.
받다 ={0, 2, 4, 6, 7, 9} 이렇게 해서 우 리 는 이 서열 을 얻 었 다.
중복 되 는 경우:
우 리 는 몇 번 의 중복 만 기록 하면 된다. 위의 표 에서 두 번 째 줄 은 바로 이 문 제 를 해결 하 는 데 쓰 인 다. 우 리 는 몇 번 의 중복 을 기록 하여 이 정렬 문 제 를 철저히 해결 할 수 있다.
이 부분의 코드 는 여기에 붙 입 니 다:

     int j=0，temp;
     for(int i=0;i<=k;i++){//      c[i]    1
           temp=c[i];//   0
           while(temp-->0){//         
                  b[j++]=i;//i         
           }
	 }

우 리 는 c 라 는 배열 을 통 해 똑 같은, 즉 반복 되 는 수 를 기록 합 니 다.
모든 코드 붙 이기:
이상 코드 경험 증!