기본 아이디어
RadixSort는 버킷 분류를 기반으로 개발되었으며 두 분류는 할당 정렬의 고급 구현입니다. DistributiveSort의 기본 아이디어 : 정렬 프로세스는 키워드를 비교할 필요가 없지만 "배포"및 "수집"프로세스를 정렬하는 것을 구현합니다. 그들의 시간 복잡성은 선형 순서에 도달 할 수 있습니다 : o (n).
카디널리티 분류는 안정적인 정렬 알고리즘이지만 특정 제한 사항이 있습니다.
1. 키워드를 분해 할 수 있습니다.
2. 기록 된 키워드의 수는 더 작으며 밀도가 높으면 더 좋습니다. 3. 숫자라면 서명되지 않은 것이 가장 좋습니다. 그렇지 않으면 해당 매핑 복잡성이 증가합니다. 먼저 별도로 정렬 할 수 있습니다.
버킷 분류 (radixsort)를 살펴 보겠습니다.
버킷 분류는 박스 분류 (Binsort)라고도합니다. 기본 아이디어는 여러 버킷을 설정하고 레코드를 정렬 할 레코드를 스캔하고 R [0], R [1],…
예를 들어, <2 <… <j <q <k, 13 "버킷"을 포인트별로 섞은 52 개의 카드를 분류하려면 설정해야합니다. 정렬 할 때, 각 카드는 해당 버킷에 포인트별로 배치 된 다음 버킷을 순서대로 연결하여 점진적인 순서로 배열 된 카드 데크를 얻습니다.
버킷 분류에서 버킷 수는 키워드의 값 범위에 따라 다릅니다. 따라서 버킷 분류는 키워드 유형이 유한해야하므로 무제한 버킷이 필요할 수 있습니다.
일반적으로 말하면, 동일한 키워드가있는 레코드가 각 버킷에 저장되어 있는지는 예측할 수 없으므로 버킷 유형은 링크 된 목록으로 설계되어야합니다.
분류가 안정적이지 않도록하려면 포장 및 수집 프로세스 중 연결이 최초의 첫 번째 원칙에 따라 수행되어야합니다.
버킷 분류의 경우 할당 프로세스의 시간은 O (n)입니다. 수집 프로세스의 시간은 O (m)입니다 (링크 된 목록은 정렬 된 레코드로 입력을 저장하는 데 사용됩니다) 또는 O (M+N). 따라서 버킷 분류 시간은 O (M+N)입니다. 버킷 수의 크기 순서가 O (n) 인 경우 버킷 분류 시간은 선형, 즉 O (n)입니다.
위에서 언급 한 주요 분류 알고리즘의 복잡성은 대부분 O (N2)이며 일부 정렬 알고리즘은 O (Nlogn)입니다. 그러나 배럴 분류는 O (n)의 시간 복잡성을 달성 할 수 있습니다. 그러나 버킷 분류의 단점은 다음과 같습니다. 우선, 공간 복잡성이 비교적 높고 추가 오버 헤드가 필요합니다. 정렬에는 두 개의 공간 오버 헤드가 있으며, 하나는 정렬 할 배열을 저장하고 다른 하나는 소위 버킷입니다. 예를 들어, 정렬 할 값은 0에서 M-1까지이어서 M 버킷이 필요 하며이 버킷 어레이에는 최소한 m 공간이 필요합니다. 둘째, 정렬 할 요소는 특정 범위 내에 있어야합니다.
카디널리티 분류는 버킷 분류의 개선으로, "버킷 분류"는 성능을 향상시키지 않고 더 큰 요소 값 세트에 적합합니다.
카드 놀이의 예를 사용하여 설명합시다. 카드는 두 가지 키워드로 구성됩니다. Suit (Peach <Heart <Mei <Square) + 액면가 (a <2 <3 <4 <... ... <k). 카드의 크기가 소송에 의해 먼저 결정되고 같은 소송의 카드가 숫자에 따라 결정됩니다. 이 문제를 해결하기위한 두 가지 알고리즘이 있습니다.
즉, 슈트가 다른 경우, 액면가가 무엇이든, 양복 색상이 낮은 카드는 양복 색상이 더 높은 수는 더 작습니다. 동일한 소송 색상에서만 크기 관계는 액면가의 크기에 의해 결정됩니다. 이것은 여러 키 코드의 순서입니다.
분류 결과를 얻으려면 두 가지 정렬 방법에 대해 설명합니다.
방법 1 : 먼저 정장과 색상을 정렬하여 4 개의 그룹, 즉 Plum Blossom Group, Square Group, Red Heart Group 및 Black Heart Group으로 나눕니다. 그런 다음 각 그룹의 액면가로 정렬 한 다음 마지막으로 4 개의 그룹을 함께 연결하십시오.
방법 2 : 먼저, 13 개의 숫자 그룹 (No. 2, 3, ..., a) 13 개의 얼굴 값에 따라, 얼굴 값에 따라 순서대로 카드를 해당 숫자 그룹에 넣고 13 개의 더미로 나눕니다. 그런 다음 4 개의 번호 그룹 (매화 꽃, 사각형, 붉은 하트, 검은 심장)을 제공하고 그룹 2에서 카드를 꺼내어 해당 색상 그룹에 넣은 다음 그룹 3의 카드를 꺼내어 해당 색상 그룹에 넣고 4 개의 색상 그룹을 세면서에 주문합니다.
멀티 키 코드 정렬은 기본 키 코드에서 두 번째 키 코드 또는 두 번째 키에서 기본 키 코드로 순서대로 정렬되며 두 가지 방법으로 나뉩니다.
MSD 메소드라고하는 가장 중요한 비트 우선 순위 (대부분의 유의 한 디지 티 피트) 메소드 :
1) 먼저 K1로 분류하고 그룹화하고 시퀀스를 여러 후속으로 나눕니다. 동일한 시퀀스 그룹의 레코드에서 키 코드 K1은 동일합니다.
2) 그런 다음 각 그룹을 K2로 하위 그룹으로 분류하십시오. 그 후, 각 하위 그룹이 가장 2 차 키 코드 KD에 의해 정렬 될 때까지 이러한 방식으로 다음 키 코드를 계속 정렬하십시오.
3) 그런 다음 그룹을 연결하여 순서 시퀀스를 얻습니다. 정장 및 얼굴 값으로 정렬 카드에 도입 된 방법은 MSD 방법입니다.
LSD 방법이라고하는 가장 유의미한 디지 타이어 스토리 방법은 다음과 같습니다.
1) KD에서 정렬을 시작한 다음 KD-1을 정렬하고 K1에 따라 가장 작은 후속으로 나눌 때까지 반복합니다.
2) 마지막으로, 각 하위 시퀀스를 연결하여 순서 시퀀스를 얻습니다. 정장 및 액면가에 의해 정렬에 소개 된 두 번째 방법은 LSD 방법입니다.
숫자 또는 문자 유형의 단일 키워드는 여러 자리 또는 여러 문자로 구성된 다중 키워드로 간주 될 수 있습니다. 현재 "할당 수집"방법을 사용하여 정렬 할 수 있습니다. 이 프로세스는 카디널리티 분류 방법이라고하며 각 숫자 또는 문자에 대한 가능한 값 수를 카디널리티라고합니다. 예를 들어, 카드 놀이 정장의 기초는 4이고 액면가의 기초는 13입니다. 카드 놀이를 정렬 할 때는 먼저 스타일 또는 액면가로 먼저 구성 할 수 있습니다. 색상에 따라 정렬 할 때 먼저 빨간색, 검은 색, 정사각형 및 꽃의 순서대로 4 개의 스택 (분포)으로 나눈 다음이 순서로 함께 (수집)를 쌓은 다음 액면가 순서로 13 스택 (분포)으로 나눈 다음이 순서로 함께 쌓습니다. 이런 식으로, 보조 할당 및 컬렉션은 순서대로 카드를 준비 할 수 있습니다.
"할당 수집"프로세스 동안, 분류의 안정성을 보장해야합니다.
카디널리티 분류에 대한 아이디어는 데이터의 각 키워드 그룹을 순서대로 정렬하는 것입니다. 예를 들어, 다음 순서는 정렬 될 것입니다.
135, 242, 192, 93, 345, 11, 24, 19
각 값의 단일, 10 및 수백 자리를 세 가지 키워드로 나눕니다.
135-> k1 (단일 자릿수) = 5, k2 (10 자리) = 3, K3 (100 자리) = 1.
그런 다음 가장 낮은 단일 비트 (마지막 키워드부터 시작)부터 시작하면 모든 데이터의 모든 K1 키워드가 버킷 할당됩니다 (각 숫자는 0-9이므로 버킷 크기는 10이기 때문에 다음 시퀀스를 얻기 위해 버킷의 데이터를 순서대로 출력합니다.
(11), (242, 192), (93), (24), (135, 345), (19) (가장 키워드에서 시작하여 100 자리를 무시하고 단일 숫자에 따라 숫자에 따라 할당)
그런 다음 상기 시퀀스가 K2에 할당되고 출력 시퀀스는 다음과 같습니다.
(11, 19), (24), (135), (242, 345), (192, 93) (두 번째 키워드를 정렬하려면 가장 키워드를 참조하고 백 숫자를 무시하고 10 자리의 숫자에 따라 할당)
마지막으로 K3의 버킷 할당의 경우 출력 순서는 다음과 같습니다.
(011, 019, 024, 093), (135, 192), (242), (345) (가장 높은 키워드를 정렬하려면 두 번째 키워드를 참조하고 10 자리와 단일 숫자를 무시하고 백 자릿수의 숫자에 따라 할당)
정렬이 완료되었습니다.
Java 구현
public void radixSort () {int max = array [0]; for (int i = 0; i <array.length; i ++) {// 배열에서 최대 값을 찾으십시오 if (array [i]> max) {max = array [i]; }} int keysnum = 0; // 키워드 수, 우리는 키워드로 단일 자릿수, 10 자리 및 수백을 사용하므로 키워드 수는 최대 숫자이고 (max> 0) {max /= 10; Keysnum ++; } list <arraylist <integer >> 버킷 = new ArrayList <ArrayList <integer >> (); for (int i = 0; i <10; i ++) {// 각 숫자의 가능한 숫자는 0 ~ 9이므로 10 버킷 버킷을 설정합니다. // 버킷은 (int i = 0; i <keysnum; i ++) {// 가장 최근의 키워드로 시작하고 (int j = 0; j <array.length; j ++) {// 모든 배열 요소를 스캔하고 해당 요소에 해당하는 요소를 스캔하고 (int j = 0; j <array.length; 258과 같은 요소. 이제 10 자리 숫자에서 숫자를 꺼내야합니다. 258%100 = 58,58/10 = 5 int 키 = 배열 [j]%(int) math.pow (10, i+1)/(int) math.pow (10, i); Buckets.get (key) .add (배열 [j]); // 키워드 키를 사용 하여이 요소를 버킷에 넣습니다} // 할당 된 후 버킷의 요소를 배열 int 카운터 = 0으로 다시 복사합니다. // (int j = 0; j <10; j ++)에 대한 요소 카운터 {arraylist <integer> bucket.get (j); // 키워드가있는 버킷 j while (buct.size ()> 0) {배열 [counter ++] = bucket.remove (0); // 버킷의 첫 번째 요소를 배열로 복사하고 제거}}} system.out.print ( "스레드"+(i+1)+"휠 정렬 :"); 표시하다(); }}인쇄 결과는 다음과 같습니다.
알고리즘 분석
언뜻보기에 카디널리티 정렬의 실행 효율성은 좋아 보이며 원본 데이터 항목을 배열에서 링크 된 목록으로 복사 한 다음 다시 복사하기 만하면 믿을 수 없습니다. 데이터 항목이 10 개있는 경우 20 개의 복제가 있으며 각 비트의 프로세스를 반복합니다. 5 자리 숫자가 정렬되었다고 가정하면 20*5 = 100 부가 필요합니다. 데이터 항목이 100 개 있으면 200*5 = 1000 사본이 있습니다. 사본 수는 데이터 항목의 수, 즉 O (n)에 비례합니다. 이것은 우리가 본 가장 효율적인 정렬 알고리즘입니다.
불행히도 데이터 항목이 많을수록 키워드가 더 길어집니다. 데이터 항목이 10 배 증가하면 키워드를 하나씩 추가해야합니다 (한 번 더 정렬). 사본 수와 데이터 항목의 수는 키워드의 길이에 비례하며 키워드 길이는 N의 로그 인 것으로 간주 될 수 있습니다. 따라서 대부분의 경우 카디널 분류의 실행 효율은 O (n*logn)으로 역전됩니다. 이는 빠른 정렬과 거의 동일합니다.
요약
위의 내용은 카디널리티 분류 및 Java 언어 구현에 대한 소개에 대한이 기사의 전체 내용입니다. 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨 두십시오.