알고리즘 서론 제8 장 선형 시간 정렬
1. 비교 정렬
비교 정렬 이란 입력 요소 간 의 비 교 를 통 해 각 요소 의 순 서 를 확정 하 는 정렬 알고리즘 을 말한다.
모든 비교 정렬 은 최 악의 경우 O (nlgn) 차 비교 로 정렬 해 야 한다.
정렬 과 쌓 기 정렬 을 합 치 는 것 이 가장 좋 습 니 다.
2. 비교 정렬
비교 정렬 이란 비교 되 지 않 은 조작 을 사용 하여 정렬 순 서 를 정 하 는 정렬 알고리즘 을 말한다.
비교 정렬 이 아 닌 경우, 하계 O (nlgn) 는 적용 되 지 않 습 니 다.
계수 정렬 은 안정 적 인 정렬 입 니 다. n 개 데이터 의 수치 범위 가 [0. k] 이면 실행 시간 은 O (n + k) 이 고 실행 공간 은 O (n + k) 입 니 다.
기수 정렬 도 안정 적 인 정렬 입 니 다. 다른 안정 적 인 정렬 을 바탕 으로 해 야 합 니 다. n 개의 d 자릿수 가 있 으 면 각각 k 가지 수치 가 있 을 수 있 습 니 다. 사용 하 는 안정 적 인 정렬 운행 시간 은 O (n + k) 이 고 기수 정렬 시간 은 O (d (n + k) 입 니 다.
통 정렬 도 안정 적 인 정렬 이 고 입력 데이터 가 균일 한 분포 에 부합 할 때 통 정렬 은 선형 시간 으로 운행 할 수 있다.설 치 된 모든 원 소 는 구간 [0, 1) 에 골 고루 분포 하고 구간 [0, 1) 을 n 개의 같은 크기 의 서브 구간 (통) 으로 나 누 어 각 통 의 수 를 정렬 하여 각 통 의 원 소 를 순서대로 나열 한다.
코드
#include <iostream>
#include <cmath>
using namespace std;
int length_A, digit;
void Print(int *A, int start, int end)
{
int i;
for(i = start; i <= end; i++)
{
if(i == start)cout<<'{';
else cout<<' ';
cout<<A[i];
}
cout<<'}'<<endl;
}
//
void Counting_Sort(int *A, int *B, int k)
{
int i, j;
// C 0，
int *C = new int[k+1];
for(i = 0; i <= k; i++)
C[i] = 0;
//C[j] j A
for(j = 1; j <= length_A; j++)
C[A[j]]++;
//C[i] <=i
for(i = 1; i <= k; i++)
C[i] = C[i] + C[i-1];
// B 0，B
for(i = 1; i <= length_A; i++)
B[i] = 0;
for(j = length_A; j >= 1; j--)
{
// <=A[j] x, A[j] x ， B[x]=A[j]
B[C[A[j]]] = A[j];
C[A[j]]--;
}
delete C;
}
//
void Stable_Sort(int *A, int *B, int k, int d)
{
int i, j;
// C 0，
int *C = new int[k+1];
for(i = 0; i <= k; i++)
C[i] = 0;
int *D = new int[length_A+1];
for(j = 1; j <= length_A; j++)
{
//D[j] [j] i
D[j] = A[j] % (int)pow(10.0, d) / (int)pow(10.0, d-1);
//C[j] D[j] A
C[D[j]]++;
}
//C[i] <=i
for(i = 1; i <= k; i++)
C[i] = C[i] + C[i-1];
// B 0，B
for(i = 1; i <= length_A; i++)
B[i] = 0;
for(j = length_A; j >= 1; j--)
{
// <=D[j] x, A[j] x ， B[x]=A[j]
B[C[D[j]]] = A[j];
C[D[j]]--;
}
delete []C;
delete []D;
}
//
void Radix_Sort(int *A, int *B)
{
int i, j;
// ，
for(i = 1; i <= digit; i++)
{
Stable_Sort(A, B, 9, i);
// A， B，
for(j = 1; j <= length_A; j++)
A[j] = B[j];
}
}
int main()
{
cin>>length_A>>digit;
int *A = new int[length_A+1];
int *B = new int[length_A+1];
int i;
// length_A digit
for(i = 1; i <= length_A; i++)
{
A[i] = 0;
while(A[i] < (int)pow(10.0, digit-1))
A[i] = rand() % (int)pow(10.0, digit);
}
Print(A, 1, length_A);
// Counting_Sort(A, B, 9);
Radix_Sort(A, B);
Print(A, 1, length_A);
delete []A;
delete []B;
return 0;
}연습
8.1 정렬 알고리즘 시간의 하계
8.1-1
<span style="line-height: 20px; ">n-1， n-1 </span>
8.1-2
8.1-3
， 。 ， 。
n ， n! ， n! 。
， 。
， ， ， 。 。 。 。
n! ： O(n)
n ， n! ， m ， k = m/(n!)
k<=1/2， 。
k 1/n、1/(2^n)
：
m m 。 h 2^h 。
2^h >= m =====> h >= lg(m)
m ， lg(m)
《 》P98 8.1 ，h>=O(nlgn)
lg(m) <= O(nlgn)， k 。
k 1/2、1/n、1/(2^n), m = k * (n!) ：
，
8.1-4
， 。 “ ” 。
：
(1)
(2) 。
(3) ，
(4)
， ：
(1) k ， k! 。
n/k ， (k!)^(n/k)
(2) (k!)^(n/k)
(3) h ， 2^h
2^h >= (k!)^(n/k) =====> h >= (n/2)lg(k/2)
(4) ， (n/2)lg(k/2)， O(nlgk)8.2 계수 정렬
8.2-1 [0,k]， B -1
A = {6 0 2 0 1 3 4 6 1 3 2}
==> C = {2 2 2 2 1 0 2}
==> C = {2 4 6 8 9 9 11}
==> B = {-1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1}
C = {2 4 5 8 9 9 11}
==> B = {-1 -1 -1 -1 -1 2 -1 3 -1 0 -1 -1}
C = {2 4 5 7 9 9 11}
==> B = {-1 -1 -1 1 -1 2 -1 3 -1 -1 -1}
C = {2 3 5 7 9 9 11}
==> B = {-1 -1 -1 1 -1 2 -1 3 -1 -1 6}
C = {2 3 5 7 9 9 10}
==> B = {-1 -1 -1 1 -1 2 -1 3 4 -1 6}
C = {2 3 5 7 8 9 10}
==> B = {-1 -1 -1 1 -1 2 3 3 4 -1 6}
C = {2 3 5 6 8 9 10}
==> B = {-1 -1 1 1 -1 2 3 3 4 -1 6}
C = {2 2 5 6 8 9 10}
==> B = {-1 0 1 1 -1 2 3 3 4 -1 6}
C = {1 2 5 6 8 9 10}
==> B = {-1 0 1 1 2 2 3 3 4 -1 6}
C = {1 2 4 6 8 9 10}
==> B = {0 0 1 1 2 2 3 3 4 -1 6}
C = {0 2 4 6 8 9 10}
==> B = {0 0 1 1 2 2 3 3 4 6 6}
C = {0 2 4 6 8 9 9}
8.2-2
C[j] i 。 ， 。 (L9)， 。
8.2-3
8.2-4
COUNTING-SORT(A, B, k) L1-L4 C，ans(a, b) = C[b] - C[a-1], C[-1]=08.3 기수 정렬
8.3-1
A = {COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX}
==> A = {SEA, TEA, MOB, TAB, DOG, RUG, DIG, BIG, BAR, EAR, TAR, COW, ROW, NOW, BOX, FOX}
==> A = {TAB, BAR, EAR, TAR, SEA, TEA, DIG, BIG, MOB, DOG, COW, ROW, NOW, BOX, FOX, RUB}
==> A = {BAR, BIG, BOX, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, TAB, TAR, TEA, SEA, RUB}8.3-2
안정 적 인 정렬: 정렬 삽입, 병합 정렬
방법: 모든 요소 에 최초의 위치 속성 을 추가 하지만 두 요소 의 value 가 같 을 때 position 를 비교 하면 같은 두 요소 가 없 을 것 입 니 다.
추가 공간: O (4n)
8.3-3
(1) d = 1 일 때 요 소 는 한 사람 만 있 고 이 사람 을 정렬 하면 전체 배열 에 정렬 하 는 것 과 같다.
(2) 1 부터 d - 1 까지 의 정렬 이 정확 할 때 d 비트 에 대한 정렬 도 정확 하 다 는 것 을 증명 한다.
(3) 배열 의 임 의 두 개의 수 a 와 b 에 대해 그들의 d 위 는 각각 ad 와 bd 라 고 가정 한다.
ad < bd, a 는 b 앞 에 있 습 니 다.
ad > bd 가 있 으 면 a 는 b 뒤로 줄 을 섭 니 다.
만약 ad = bd 라면 a 와 b 의 상대 적 인 위 치 는 변 하지 않 습 니 다. 안정 적 인 정렬 이기 때문에 이 점 은 보장 할 수 있 습 니 다.
8.3-4
정 수 를 n 진법 으로 바 꾸 고 정렬 합 니 다.
알고리즘 서론 8.3 - 4
8.3-5
최 악의 경우 d 번 필요
8.4 배럴 정렬
8.4-1
A = ｛0.79， 0.13， 0.16， 0.64， 0.39， 0.20， 0.89， 0.53， 0.71， 0.42｝
==> A = ｛0.13， 0.16， 0.20， 0.39， 0.42， 0.53， 0.64， 0.79， 0.71， 0.89｝
==> A = ｛0.13， 0.16， 0.20， 0.39， 0.42， 0.53， 0.64， 0.71， 0.79， 0.89｝
8.4-2
O(n^2)
： O(nlgn)
8.4-3
E(X^2)=1/4 * 0 + 1/2 * 1 + 1/4 * 4 = 3/2
E^2(X)=[1/4 * 0 + 1/2 * 1 + 1/4 * 2]^2 = 1^2 = 1
8.4-4
n
BUCKET-SORT(A)
1 n <- length[A]
2 for i <- 1 to n
3 do insert A[i] to list B[n*(A[i].x^2 + A[i].y^2)]
4 for i <- 0 to n-1
5 do sort list B[i] with insertion sort
6 concatenate the lists B[0], B[1], ……,B[n-1] together in order
8.4-5아니요, 인터넷 에서 답 을 찾 았 는데 모 르 겠 어 요.
X 의 적절 한 분포 P 는 반드시 균일 한 분포 가 아니 라 한 계 를 모 릅 니 다. 그러나 P (x) 값 은 [0, 1] 에 속 하고 X 에 대해 엄격 하고 단조 로 운 증가, 정렬 P (x) 즉 정렬 X 입 니 다. P (x) 를 n 개의 항목 그룹 으로 나 누 었 습 니 다. X 는 무 작위 로 뽑 았 기 때문에 모든 한계 에 떨 어 질 확률 이 같 습 니 다.
만약 (i - 1) / n < = p (xi) < i / n 이 라면, 그것 을 i 번 째 통 에 넣는다.
http://www.mysjtu.com/page/M0/S696/696126.html
사고 문제
8 - 1 비교 정렬 의 평균 상황 하계
a)n n! ， n! ， 0。
n! ， 1/n1， 1/n!
b) T(n) n T ，RT(n)、LT(n) n T 、 。
T(n)=RT(n)+1 T(n)=LT(n)+1
D(T)=D(RT)+D(LT)+k
c) ， ， ， 8 - 2 선형 시간 제자리 로 정렬 변환
a)
b)
c)
d) （ 2）， O(bn) ， O(n)（ 1）， a
e)
COUNTING-SORT(A, k)
1 for i <- 0 to k
2 do C[i] <- 0
3 for j <-1 to length[A]
4 C[A[j]] <- C[A[j]] + 1
5 cnt <- 1
6 for i <- 1 to k
7 while C[i] > 0
8 A[cnt] <- i
9 C[i] <- C[j] - 1
10 cnt <- cnt + 18 - 3 긴 데이터 항목 정렬
보다.
알고리즘 서론 - 8 - 3 - 서로 다른 길이 의 데이터 항목 정렬
a) O(n)， O(n)
b) ， ， ，
， 8 - 4 주전자
a) ，
c) ， ，
step1：
step2：
step3： ，
step4： ，
step5： step1 step4 8 - 5 평균 정렬
보다.
알고리즘 서론 6.5 - 8 더미 정렬 - K 로 통합
a)1
b)1，3，2，4，5，7，6，8，9，10
c)
d)
step1： 1, 1+k, 1+2k, 1+3k,……;2, 2+k, 2+2k, 2+3k,……；……
step2： O(nlg(n/k))
e)
step1： d)step1
step2： k 8 - 6 정렬 된 목록 의 하 계 를 합 칩 니 다.
a)2n ， n ， C(2n,n)
b)2^h >= C(2n,n)
=====> h >= lg((2n)!) - 2lg(n!)
=====> h >= 2nlg2n - 2nlgn
=====> h >= 2nlg2
， ，
c)d) ， 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
