정렬 알고리즘은 여러 곳에서 사용됩니다. 최근에 알고리즘을 다시 검토하고 여기에 기록하고 향후 검토를 위해 일부 자료를 저장해 두겠습니다.
더 이상 고민하지 않고 고전적인 정렬 알고리즘을 하나씩 살펴보겠습니다.
1. 정렬을 선택하세요
선택 정렬의 기본 아이디어는 배열을 순회하는 과정에서 i가 정렬이 필요한 현재 시퀀스 번호를 나타내는 경우 나머지 [i...n-1] 중에서 최소값을 찾아야 한다는 것입니다. , 그리고 찾은 최소값을 i 값으로 지정하여 교환합니다. 요소를 결정하는 각 프로세스에는 최대값을 선택하는 하위 프로세스가 있기 때문에 사람들은 이를 선택 정렬이라고 생생하게 부릅니다. 예를 들어보겠습니다:
초기: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
i = 0: [2, 17, 16, 16, 7, 31, 39, 32, 38, 11] (0번째 [38]<->8번째 [2])
i = 1: [2, 7, 16, 16, 17, 31, 39, 32, 38, 11] (첫 번째 [38]<->4 번째 [17])
i = 2: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (2번째 [11]<->9번째 [16])
i = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (스왑 필요 없음)
i = 4: [2, 7, 11, 16, 16, 31, 39, 32, 38, 17] (4번째 [17]<->9번째 [16])
i = 5: [2, 7, 11, 16, 16, 17, 39, 32, 38, 31] (5번째 [31]<->9번째 [17])
i = 6: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (6번째 [39]<->9번째 [31])
i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (스왑 필요 없음)
i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (스왑이 필요하지 않음)
i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (스왑 필요 없음)
예제에서 볼 수 있듯이 선택 정렬이 진행됨에 따라(i가 점차 증가함) 비교 횟수는 점점 줄어들지만, 선택 정렬은 배열의 초기 정렬 여부에 관계없이 선택 비교를 수행합니다. i부터 배열의 끝까지 따라서 주어진 길이의 배열에 대해 선택 정렬의 비교 횟수는 1 + 2 + 3 + .... + n = n * (n + 1) / 2입니다. , 교환 횟수는 초기 배열의 순서와 관련이 있습니다. 초기 배열 순서가 무작위인 경우 최악의 경우 배열 요소가 n번 교환되고 가장 좋은 경우는 0번이 될 수 있습니다( 배열 자체는 시퀀스입니다).
선택 정렬의 시간 복잡도와 공간 복잡도는 각각 O(n2)와 O(1)임을 추론할 수 있습니다(선택 정렬에는 배열 요소 교환을 위한 추가 공간만 필요함).
구현 코드:
다음과 같이 코드 코드를 복사합니다.
/**
*선택 정렬
*/
SELECTION(새 정렬 가능() {
공개 <T 확장 Comparable<T>> void sort(T[] 배열, 부울 승천) {
int len = array.length;
for (int i = 0; i < len; i++) {
선택한 정수 = i;
for (int j = i + 1; j < len; j++) {
int 비교 = array[j].compareTo(array[selected]);
if (비교 != 0 && 비교 < 0 == 상승) {
선택됨 = j;
}
}
exchange(배열, i, 선택됨);
}
}
})
2. 삽입 정렬
삽입 정렬의 기본 아이디어는 배열을 순회하는 과정에서 일련 번호 i 이전의 요소, 즉 [0..i-1]이 정렬되었다고 가정하고 이번 여행에서 올바른 위치를 찾아야 한다는 것입니다. i에 해당하는 요소 x의 k를 찾고, 이 위치 k를 찾는 과정에서 비교된 요소를 하나씩 뒤로 이동하여 요소 x에 대한 "공간을 만듭니다". 마지막으로 k에 해당하는 요소 값이 할당됩니다. x. 삽입 정렬은 정렬의 특성에 따라 이름이 붙여지기도 합니다.
다음은 빨간색으로 표시된 숫자가 삽입된 숫자이고, X로 표시된 숫자는 이 정렬에 참여하지 않는 요소입니다. 두 번째 정렬에 참여하는 요소는 [11, 31, 12]이고, 삽입해야 할 요소는 12인데, 12는 현재 올바른 위치에 있지 않기 때문에 다음과 같이 삽입해야 합니다. 이전 요소 31과 11을 순서대로. 비교하고, 비교하면서 비교된 요소를 이동하고, 12보다 작은 첫 번째 요소 11을 찾으면 비교를 중지합니다. 이때 31에 해당하는 인덱스 1이 12를 삽입해야 하는 위치입니다.
초기: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
첫 번째 패스: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18] (이동된 요소 없음)
두 번째 여행: [11, 12, 31, 5, 34, 30, 26, 38, 36, 18] (31은 뒤로 이동)
세 번째 여행 : [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (11, 12, 31은 모두 뒤로 이동)
네 번째 패스: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (이동 요소 없음)
다섯번째 여행 : [5, 11, 12, 30, 31, 34, 26, 38, 36, 18] (31, 34는 뒤로 이동)
여섯번째 여행 : [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (30, 31, 34는 뒤로 이동)
일곱 번째 패스: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (이동 요소 없음)
여덟 번째 여행: [5, 11, 12, 26, 30, 31, 34, 36, 38, 18] (38은 뒤로 이동)
아홉번째 여행 : [5, 11, 12, 18, 26, 30, 31, 34, 36, 38] (26, 30, 31, 34, 36, 38 뒤로 이동)
삽입 정렬은 정렬 과정에서 배열 요소의 첫 번째 부분이 정렬되어 비교 횟수를 효과적으로 줄일 수 있다는 점에서 선택 정렬보다 낫습니다. 물론 이 이점은 초기 순서에 따라 달라집니다. 결국 나쁜 경우(주어진 배열이 역순으로 되어 있는 경우) 삽입 정렬에 필요한 비교 및 이동 횟수는 1 + 2 + 3... + n = n * (n)이 됩니다. + 1) / 2. 이 극단적인 경우에는 삽입 정렬이 선택 정렬보다 정렬 효율성이 더 떨어집니다. 따라서 삽입 정렬은 불안정한 정렬 방법이며, 삽입 효율은 배열의 초기 순서와 밀접한 관련이 있습니다. 일반적으로 삽입정렬의 시간복잡도는 O(n2), 공간복잡도는 O(1)이다.
구현 코드:
다음과 같이 코드 코드를 복사합니다.
/**
*삽입정렬
*/
INSERTION(새 정렬 가능() {
공개 <T 확장 Comparable<T>> void sort(T[] 배열, 부울 승천) {
int len = array.length;
for (int i = 1; i < len; i++) {
T toInsert = 배열[i];
int j = i;
(; j > 0; j) {
int 비교 = array[j - 1].compareTo(toInsert);
if (비교 == 0 || 비교 < 0 == 상승) {
부서지다;
}
배열[j] = 배열[j - 1];
}
배열[j] = toInsert;
}
}
})
3. 버블 정렬
버블 정렬은 가장 고전적인 정렬 알고리즘으로 간주할 수 있습니다. 구현 방법이 가장 간단하기 때문에 이 알고리즘은 2단계 for 루프입니다. 내부 루프에서는 인접한 두 요소가 역순인지 판단합니다. 그렇다면 두 요소를 교환하고 하나의 외부 루프를 수행하여 배열의 나머지 요소 중 가장 작은 요소를 앞쪽으로 "떠있게" 하므로 이를 호출합니다. 버블 정렬.
평소처럼 간단한 예를 들어보겠습니다.
초기 상태: [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]
내부 레이어의 첫 번째 여행: [24, 19, 26, 39, 36, 7, 31, 29, 23, 38] (9일 [23]<->8일 [38)
내부 레이어의 두 번째 패스: [24, 19, 26, 39, 36, 7, 31, 23, 29, 38] (8번째 [23]<->7번째 [29])
내부 레이어의 세 번째 패스: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7번째 [23]<->6번째 [31])
내부 레이어의 네 번째 패스: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7과 23은 모두 올바른 순서이므로 교환이 필요하지 않습니다.)
내층의 다섯 번째 여행 : [24, 19, 26, 39, 7, 36, 23, 31, 29, 38] (5일 [7]<->4일 [36])
내부층의 여섯번째 여행 : [24, 19, 26, 7, 39, 36, 23, 31, 29, 38] (4차 [7]<->3차 [39])
내부 레이어의 일곱 번째 패스: [24, 19, 7, 26, 39, 36, 23, 31, 29, 38] (3번째 [7]<->2번째 [26])
내부 레이어의 8번째 패스: [24, 7, 19, 26, 39, 36, 23, 31, 29, 38] (2nd [7]<->1st [19])
내부 레이어의 아홉 번째 여행: [7, 24, 19, 26, 39, 36, 23, 31, 29, 38] (1st [7]<->0th [24])
......
실제로 버블 정렬은 선택 정렬과 유사하며 비교 횟수는 n * (n + 1) / 2로 동일합니다. 그러나 버블 정렬은 최소값을 선택하는 과정에서 추가 교환을 수행합니다(버블 정렬만 필요). 인접 요소의 순서가 올바르지 않은 것으로 확인되면 교환됩니다. 이에 따라 선택 정렬은 내부 루프 비교가 완료된 후 상황에 따라 교환 여부를 결정하므로 내 생각에는 선택 정렬이 속합니다. 버블 정렬이 개선되었습니다.
구현 코드:
다음과 같이 코드 코드를 복사합니다.
/**
* 버블 정렬(Bubble Sorting)은 삽입 정렬(Insertion Sorting)과 매우 유사합니다.
*/
BUBBLE(새 정렬 가능() {
공개 <T 확장 Comparable<T>> void sort(T[] 배열, 부울 승천) {
int 길이 = array.length;
int lastExchangedIdx = 0;
for (int i = 0; i < 길이; i++) {
// 교환이 거짓인지 여부를 식별하기 위한 플래그를 표시합니다.
부울 isExchanged = false;
// 인덱스 i에 도달하기 전에 마지막 비교 및 교환이 발생했습니다.
int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i;
for (int j = 길이 1; j > currOrderedIdx; j) {
int 비교 = array[j - 1].compareTo(array[j]);
if (비교 != 0 && 비교 > 0 == 상승) {
exchange(배열, j 1, j);
isExchanged = 사실;
lastExchangedIdx = j;
}
}
// 교환이 일어나지 않으면 배열이 이미 순서대로 되어 있음을 의미합니다.
if (isExchanged == false) {
부서지다;
}
}
}
})
4. 힐 정렬
Hill 정렬은 삽입 정렬이 큰 배열을 처리할 때 너무 많은 요소를 이동하는 문제에 직면했기 때문에 탄생했습니다. 힐 정렬(Hill Sorting)의 개념은 큰 배열을 여러 개의 작은 배열로 "분할하여 정복"하는 것인데, If gap 배열과 같이 간격으로 나누어집니다. = 2로 나누면 두 개의 배열 [1, 3, 5, 7]과 [2, 4, 6, 8]로 나눌 수 있습니다(대응하여 gap = 3 등). , 분할된 배열은 다음과 같습니다: [1, 4, 7], [2, 5, 8], [3, 6]) 그런 다음 분할된 배열에 대해 삽입 정렬을 수행하고 각 하위 배열이 정렬된 후 이를 줄입니다. 간격 = 1이 될 때까지 이전 단계를 반복합니다. 즉, 배열 전체에 대해 삽입 정렬을 수행하게 되는데, 이때 배열은 기본적으로 정렬되므로 이동해야 할 요소가 매우 작아지게 되는데, 이는 대용량 처리 시 삽입 정렬에서 더 많은 이동이 발생하는 문제를 해결한다. 스케일 배열.
구체적인 예는 삽입 정렬을 참조하세요.
힐 정렬(Hill Sort)은 삽입 정렬을 개선한 것으로, 데이터의 양이 많을 경우에는 직접 삽입 정렬을 사용하는 것이 좋습니다.
구현 코드:
다음과 같이 코드 코드를 복사합니다.
/**
* 쉘 정렬
*/
SHELL(새 정렬 가능() {
공개 <T 확장 Comparable<T>> void sort(T[] 배열, 부울 승천) {
int 길이 = array.length;
정수 간격 = 1;
// 길이 다음의 가장 큰 것을 사용 / 3을 첫 번째 간격으로 사용
while (간격 < 길이 / 3) {
간격 = 간격 * 3 + 1;
}
while (갭 >= 1) {
for (int i = 간격; i < 길이; i++) {
T next = 배열[i];
int j = i;
while (j >= 간격) {
int 비교 = array[j - gap].compareTo(next);
// 이미 위치를 찾았습니다.
if (비교 == 0 || 비교 < 0 == 상승) {
부서지다;
}
배열[j] = 배열[j - 간격];
j -= 간격;
}
if (j != i) {
배열[j] = 다음;
}
}
간격 /= 3;
}
}
})
5. 병합 정렬
병합 정렬은 "분할 정복" 방법인 재귀를 통해 구현됩니다. 대상 배열을 가운데에서 두 개로 나눈 다음 두 배열을 별도로 정렬한 후 정렬된 두 배열을 "병합"합니다. "를 Together에 추가할 때 병합 정렬에서 가장 중요한 것은 "병합" 과정입니다. 병합 과정에는 병합해야 하는 두 배열의 길이에 맞는 추가 공간이 필요합니다. 예를 들어 지정해야 하는 배열 다음과 같습니다: [3, 6, 8, 11]과 [1, 3, 12, 15] (논리적으로는 두 개의 배열로 나누어져 있지만, 이 요소들은 실제로는 여전히 원래 배열에 있지만 일부 인덱스를 통해 두 개의 배열로 나누어집니다. 원래 배열의 경우 [3, 6, 8, 11, 1, 3, 12, 15에서 세 개의 포인터 lo, mid, high를 각각 0, 3, 7로 설정했습니다. 논리적 하위 배열 분할이 가능합니다.) 그러면 필요한 추가 배열의 길이는 4 + 4 = 8입니다. 병합 프로세스는 다음과 같이 간략하게 요약될 수 있습니다.
1) 두 하위 배열의 요소를 새 배열 CopyArray에 복사합니다. 위에서 언급한 예를 예로 들면, CopyArray = [3, 6, 8, 11, 1, 3, 12, 15]입니다.
2) 두 포인터가 각각 원자 배열의 해당 첫 번째 요소를 가리키도록 설정합니다. 두 포인터의 이름이 leftIdx 및 rightIdx이고 leftIdx = 0(copyArray의 첫 번째 요소 [3]에 해당), rightIdx = 4( CopyArray의 다섯 번째 요소 [1]에 해당);
3) leftIdx와 rightIdx가 가리키는 배열 요소의 값을 비교하여 더 작은 것을 선택하고 그 값을 원래 배열의 해당 위치 i에 할당한 후 자동 증가 연산을 수행합니다. 할당에 참여하는 두 개의 인덱스. leftIdx 또는 rigthIdx 값이 해당 배열의 끝에 도달한 경우 남은 배열 요소를 나머지 위치에 순서대로 복사하면 됩니다.
다음은 병합의 구체적인 예입니다.
첫 번째 여행:
보조 배열 [21, 28, 39 | 35, 38] (배열은 |로 구분된 두 개의 왼쪽 및 오른쪽 하위 배열로 분할됩니다.)
[21, , , , ] (처음 21을 35와 비교하면 왼쪽 하위 배열이 승리합니다. leftIdx = 0, i = 0)
두 번째 여행:
보조 어레이 [21, 28, 39 |
[21, 28, , , ] (두 번째로 28을 35와 비교하면 왼쪽 하위 배열이 승리합니다. leftIdx = 1, i = 1)
세 번째 여행: [21, 28, 39 |
[21, 28, 35, , ] (세 번째로 39를 35와 비교하면 오른쪽 하위 배열이 승리합니다. rightIdx = 0, i = 2)
네 번째 여행 : [21, 28, 39 |
[21, 28, 35, 38,] (네 번째로 39와 38을 비교하면 오른쪽 하위 배열이 승리합니다. rightIdx = 1, i = 3)
다섯 번째 여행: [21, 28, 39 |
[21, 28, 35, 38, 39] (오른쪽 하위 배열은 다섯 번째로 복사되었으므로 leftIdx = 2, i = 4를 비교할 필요가 없습니다.)
위는 병합 과정입니다. 제한된 횟수만큼 정렬해야 하는 전체 배열을 길이가 1인 작은 배열로 나눌 때까지 분할할 수 있습니다. 배열을 더 이상 정렬할 필요가 없습니다. 그 후 길이 n/2의 마지막 하위 배열이 병합될 때까지 이러한 배열은 (재귀로 인해) 역순으로 병합됩니다. 병합이 완료된 후 배열 정렬도 완료됩니다.
병합 정렬에는 모든 정렬 중 가장 많은 추가 공간이 필요하며, 각 병합에는 (보조 배열을 제공하기 위해) 병합에 참여하는 두 배열의 길이의 합과 동일한 수의 요소가 필요합니다. 그러면 병합 정렬의 공간 복잡도는 1 + 2 + 4 + ... + n = n * ( n + 2) / 4 (n의 패리티 판단 무시)임을 추론할 수 있습니다. 시간 복잡도는 추정하기 어렵습니다. . 여기에서도 ()가 몇 개인지 잊어버렸습니다.
구현 코드:
다음과 같이 코드 코드를 복사합니다.
/**
* 병합 정렬
*/
MERGE(새 정렬 가능() {
공개 <T 확장 Comparable<T>> void sort(T[] 배열, 부울 승천) {
this.sort(배열, 0, array.length 1, 상승);
}
private <T는 Comparable<T>를 확장합니다. void sort(T[] array, int lo, int hi, boolean climb) {
// 하나를 최적화
// 부분 문자열의 길이가 20보다 작은 경우
// 재귀 호출을 줄이기 위해 삽입 정렬을 사용합니다.
if (안녕하세요 < 20) {
for (int i = lo + 1; i <= hi; i++) {
T toInsert = 배열[i];
int j = i;
for (; j > lo; j) {
int 비교 = array[j - 1].compareTo(toInsert);
if (비교 == 0 || 비교 < 0 == 상승) {
부서지다;
}
배열[j] = 배열[j - 1];
}
배열[j] = toInsert;
}
반품;
}
int mid = lo + (hi lo) / 2;
sort(배열, lo, mid, 상승);
sort(배열, 중간 + 1, 안녕, 오름차순);
merge(배열, lo, mid, hi, 상승);
}
개인 <T 확장 Comparable<T>> void merge(T[] 배열, int lo, int mid, int hi, 부울 승천) {
// 두 개를 최적화합니다.
// 이미 올바른 순서로 되어 있다면 이 병합을 건너뜁니다.
// 그럴 필요가 없기 때문에
int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);
if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == 상승) {
반품;
}
@SuppressWarnings("선택 해제됨")
T[] arrayCopy = (T[]) new Comparable[hi - lo + 1];
System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
int lowIdx = 0;
int highIdx = mid lo + 1;
for (int i = lo; i <= hi; i++) {
if (lowIdx > mid lo) {
// 왼쪽 하위 배열이 소진되었습니다.
배열[i] = arrayCopy[highIdx++];
} else if (highIdx > hi lo) {
// 오른쪽 하위 배열이 소진되었습니다.
배열[i] = arrayCopy[lowIdx++];
} else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == 상승) {
배열[i] = arrayCopy[lowIdx++];
} 또 다른 {
배열[i] = arrayCopy[highIdx++];
}
}
}
})
6. 퀵 정렬
퀵 정렬은 병합 방법을 사용하여 구현된 "분할 정복" 정렬 알고리즘이기도 하며 각 파티션(정렬 알고리즘의 핵심)의 배열 요소에 대한 정렬의 최종 정확한 위치를 한 번 결정할 수 있다는 점이 매력입니다. 위치 지정이 정확하면 이 요소는 다음 주기에서 고려되지 않습니다.