안정성 (안정성)
정렬 알고리즘은 안정적입니다. 즉, R과 S 키에 대한 두 개의 동일한 레코드가 있고 R이 원래 목록에서 S 앞에 나타나면 R도 정렬된 목록에서 S 앞에 나타납니다.
정렬 알고리즘 분류
일반적인 것으로는 삽입(삽입 정렬/힐 정렬), 교환(버블 정렬/퀵 정렬), 선택(선택 정렬), 병합(병합 정렬) 등이 있습니다.
1. 삽입정렬
삽입 정렬(Insertion Sort)은 정렬되지 않은 데이터에 대해 정렬된 순서를 뒤에서 앞으로 스캔하여 해당 위치를 찾아 삽입하는 방식으로 작동합니다. 삽입 정렬의 구현에서는 일반적으로 내부 정렬(즉, O(1) 여분의 공간만 사용하는 정렬)이 사용됩니다. 따라서 스캔 과정에서 뒤에서 앞으로 반복적이고 점진적으로 이동해야 합니다. 요소를 뒤로 정렬하여 최신 요소에 대한 삽입 공간을 제공합니다.
일반적으로 삽입 정렬은 내부 위치를 사용하여 배열에서 구현됩니다. 특정 알고리즘은 다음과 같이 설명됩니다.
첫 번째 요소부터 시작하여 요소가 정렬된 것으로 간주할 수 있습니다.
다음 요소를 가져와서 정렬된 요소 순서대로 뒤에서 앞으로 스캔합니다.
(정렬된) 요소가 새 요소보다 큰 경우 해당 요소를 다음 위치로 이동합니다.
정렬된 요소가 새 요소보다 작거나 같은 위치를 찾을 때까지 3단계를 반복합니다.
해당 위치에 새 요소를 삽입한 후.
2~5단계를 반복하세요.
다음과 같이 코드 코드를 복사합니다 .
공개 정적 무효 삽입 정렬(int[] 데이터) {
for (int index = 1; index < data.length; index++) {
int 키 = 데이터[인덱스];
int 위치 = 인덱스;
// 더 큰 값을 오른쪽으로 이동
while (위치 > 0 && data[위치 - 1] > 키) {
데이터[위치] = 데이터[위치 - 1];
위치--;
}
데이터[위치] = 키;
}
}
2. 힐 정렬
쉘 정렬(Shell Sort)은 삽입 정렬의 한 종류입니다. 직접 삽입 정렬 알고리즘이 개선되었습니다. 이 방법은 DL이기 때문에 증분 정렬 감소라고도 합니다. Shell은 1959년에 제안된 이름을 따서 명명되었습니다.
Hill 정렬은 삽입 정렬의 다음 두 가지 속성을 기반으로 향상된 방법을 제안합니다.
삽입 정렬은 거의 정렬된 데이터를 처리할 때 매우 효율적입니다. 즉, 선형 정렬의 효율성을 얻을 수 있습니다.
그러나 삽입 정렬은 한 번에 한 비트씩만 데이터를 이동할 수 있기 때문에 일반적으로 비효율적입니다.
다음과 같이 코드 코드를 복사합니다 .
static <E는 Comparable<? super E>>를 확장합니다. void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, . ..
(; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
3. 버블 정렬
버블 정렬(Bubble Sort, 대만에서 번역: Bubble Sort 또는 Bubble Sort)은 간단한 정렬 알고리즘입니다. 정렬할 시퀀스를 반복적으로 살펴보며 한 번에 두 요소를 비교하고 순서가 잘못된 경우 교체합니다. 더 이상 교환이 필요하지 않을 때까지 어레이 방문 작업이 반복됩니다. 이는 어레이가 정렬되었음을 의미합니다. 이 알고리즘의 이름은 작은 요소가 스와핑을 통해 배열의 맨 위로 천천히 "부동"된다는 사실에서 유래되었습니다.
버블 정렬 알고리즘은 다음과 같이 작동합니다.
인접한 요소를 비교하고 첫 번째 요소가 두 번째 요소보다 크면 두 요소를 모두 바꿉니다.
첫 번째 쌍에서 시작하여 마지막 쌍으로 끝나는 각 인접 요소 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소는 가장 큰 숫자가 되어야 합니다.
마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.
비교할 숫자 쌍이 더 이상 남지 않을 때까지 매번 점점 더 적은 수의 요소에 대해 위 단계를 반복합니다.
다음과 같이 코드 코드를 복사합니다 .
공개 정적 무효 bubbleSort(int[] 데이터) {
정수 온도 = 0;
for (int i = data.length - 1; i > 0; --i) {
부울 isSort = false;
for (int j = 0; j < i; ++j) {
if (데이터[j + 1] < 데이터[j]) {
온도 = 데이터[j];
데이터[j] = 데이터[j + 1];
데이터[j + 1] = 온도;
isSort = 참;
}
}
// 내부 루프에서 교환이 발생하면 비교를 계속하고, 내부 루프에서 교환이 발생하지 않으면 정렬된 것으로 간주됩니다.
if (!isSort)
부서지다;
}
}
4. 퀵 정렬
퀵소트는 버블정렬을 개선한 것입니다. 1962년 CAR Hoare가 제안했습니다. 기본 아이디어는 한 번의 정렬을 통해 정렬할 데이터를 두 개의 독립적인 부분으로 나눈 다음, 이 방법을 사용하여 데이터의 두 부분을 빠르게 분리하는 것입니다. . 정렬(Sorting)은 전체 정렬 과정을 재귀적으로 수행하여 전체 데이터가 정렬된 시퀀스가 되도록 할 수 있습니다.
퀵 정렬은 분할 정복 전략을 사용하여 목록을 두 개의 하위 목록으로 나눕니다.
단계는 다음과 같습니다.
시퀀스에서 요소를 선택하는 것을 "피벗"이라고 합니다.
기본 값보다 작은 모든 요소는 기본 앞에 배치되고 기본 값보다 큰 모든 요소는 기본 뒤에 배치되도록 배열을 재정렬합니다(동일한 숫자가 양쪽에 올 수 있음). 이 파티션이 종료된 후 베이스는 시퀀스의 중간에 있습니다. 이를 파티션 작업이라고 합니다.
기준 값보다 작은 요소의 하위 배열과 기준 값보다 큰 요소의 하위 배열을 재귀적으로 정렬합니다.
다음과 같이 코드 코드를 복사합니다 .
/*
* 퀵소트를 위한 보다 효율적인 구현 <br />
* 피벗에 대해 왼쪽, 중앙 및 오른쪽 중앙값(@see #median())을 사용하고
* 알고리즘의 핵심을 위한 더 효율적인 내부 루프.
*/
공개 클래스 Quicksort {
공개 정적 최종 int CUTOFF = 11;
/**
* 빠른 정렬 알고리즘 <br />
*
* @param arr은 비교 가능한 항목의 배열입니다. <br />
*/
public static <T는 Comparable을 확장합니다<? super T>> void Quicksort(T[] arr) {
QuickSort(arr, 0, arr.length - 1);
}
/**
* 왼쪽, 중앙, 오른쪽의 중앙값을 구합니다. <br />
* 이것을 주문하고 배열의 끝에 피벗을 숨겨 숨깁니다. <br />
*
* @param arr은 비교 가능한 항목의 배열입니다. <br />
* @param은 하위 배열의 가장 왼쪽 인덱스를 떠났습니다. <br />
* @param right 하위 배열의 가장 오른쪽 인덱스.<br />
* @return T
*/
public static <T는 비교 가능<? super T>> T median(T[] arr, int left, int right) {
int center = (왼쪽 + 오른쪽) / 2;
if (arr[left].compareTo(arr[center]) > 0)
swapRef(arr, 왼쪽, 가운데);
if (arr[left].compareTo(arr[right]) > 0)
swapRef(arr, 왼쪽, 오른쪽);
if (arr[center].compareTo(arr[right]) > 0)
swapRef(arr, center, right);
swapRef(arr, center, right - 1);
return arr[오른쪽 - 1];
}
/**
* 빠른 정렬 알고리즘으로 배열을 정렬하는 내부 방법 <br />
*
* @param arr은 비교 가능한 항목의 배열입니다. <br />
* @param은 하위 배열의 가장 왼쪽 인덱스를 떠났습니다. <br />
* @param right 하위 배열의 가장 오른쪽 인덱스 <br />
*/
private static <T는 Comparable을 확장합니다<? super T>> void QuickSort(T[] arr, int left, int right) {
if (왼쪽 + CUTOFF <= 오른쪽) {
// 피벗을 찾는다
T 피벗 = 중앙값(arr, 왼쪽, 오른쪽);
//파티션 시작
int i = 왼쪽, j = 오른쪽 - 1;
을 위한 (;;) {
while (arr[++i].compareTo(pivot) < 0);
while (arr[--j].compareTo(pivot) > 0);
만약 (i < j)
swapRef(arr, i, j);
또 다른
부서지다;
}
// 피벗 참조를 다시 작은 컬렉션으로 바꿉니다.
swapRef(arr, i, right - 1);
QuickSort(arr, left, i - 1); // 작은 컬렉션을 정렬합니다.
QuickSort(arr, i + 1, right); // 큰 컬렉션을 정렬합니다.
} 또 다른 {
// 총 개수가 CUTOFF보다 작으면 삽입 정렬을 사용합니다.
// 대신 (훨씬 더 효율적이기 때문입니다).
Sort(arr, 삽입 왼쪽, 오른쪽);
}
}
/**
* 배열의 참조를 교환하는 방법.<br />
*
* @param arr 객체 배열 <br />
* @param idx1 첫 번째 요소의 인덱스 <br />
* @param idx2 두 번째 요소의 인덱스 <br />
*/
공개 정적 <T> void swapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* 삽입 정렬을 사용하여 부분 배열을 처음부터 끝까지 정렬하는 방법
* 알고리즘 <br />
*
* @param arr은 비교 가능한 항목의 배열입니다. <br />
* @param 시작 위치를 시작합니다. <br />
* @param 끝 위치를 종료합니다. <br />
*/
public static <T는 Comparable을 확장합니다<? super T>> void insertSort(T[] arr, int start, int end)
나는 int;
for (int j = 시작 + 1; j <= 끝; j++) {
T tmp = arr[j];
for (i = j; i > start && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
개인 정적 무효 printArray(Integer[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
공개 정적 무효 메인(String[] args) {
정수[] 데이터 = {10, 4, 9, 23, 1, 45, 27, 5, 2};
System.out.println("bubbleSort...");
printArray(데이터);
퀵정렬(데이터);
printArray(데이터);
}
}
5. 선택 정렬
선택 정렬은 간단하고 직관적인 정렬 알고리즘입니다. 작동 방식은 다음과 같습니다. 먼저 정렬되지 않은 시퀀스에서 가장 작은(큰) 요소를 찾아 정렬된 시퀀스의 시작 부분에 저장한 다음, 정렬되지 않은 나머지 요소에서 계속해서 가장 작은(큰) 요소를 찾아 마지막에 넣습니다. 정렬된 순서. 모든 요소가 정렬될 때까지 계속됩니다.
요소를 결정하는 각 프로세스에는 최소값을 선택하는 하위 프로세스가 있으므로 사람들은 이를 선택 정렬이라고 생생하게 부릅니다.
예를 들어, 시퀀스 5 8 5 2 9에서 우리는 첫 번째 요소 5가 첫 번째 패스에서 2로 교환될 것이라는 것을 알고 있습니다. 그런 다음 원래 시퀀스에서 두 5의 상대적 순서가 파괴되므로 선택 정렬은 다음과 같습니다. 정렬 알고리즘이 안정적이지 않습니다.
다음과 같이 코드 코드를 복사합니다 .
공개 정적 무효 selectSort(int[] 데이터) {
int minIndex = 0;
정수 온도 = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //정렬되지 않은 영역의 최소 데이터 배열 인덱스
for (int j = i + 1; j < data.length; j++) { // 정렬되지 않은 영역에서 가장 작은 데이터를 찾아 배열 첨자를 저장합니다.
if (데이터[j] < 데이터[최소 인덱스]) {
최소지수 = j;
}
}
if (minIndex != i) { // 순서가 지정되지 않은 영역의 최소 위치가 기본 첫 번째 데이터가 아닌 경우 교환합니다.
온도 = 데이터[i];
데이터[i] = 데이터[최소인덱스];
데이터[최소인덱스] = 온도;
}
}
}
6. 병합 정렬
병합 정렬은 병합 작업을 기반으로 하는 효과적인 정렬 알고리즘입니다. 이 알고리즘은 분할 정복(Divide and Conquer) 방식을 사용하는 매우 일반적인 응용 프로그램입니다.
병합 작업 과정은 다음과 같습니다.
크기가 정렬된 두 시퀀스의 합이 되도록 공간을 적용합니다. 이 공간은 병합된 시퀀스를 저장하는 데 사용됩니다.
두 개의 포인터를 설정합니다. 초기 위치는 두 개의 정렬된 시퀀스의 시작 위치입니다.
두 포인터가 가리키는 요소를 비교하여 상대적으로 작은 요소를 선택하여 병합 공간에 넣은 후 포인터를 다음 위치로 이동시킵니다.
포인터가 시퀀스 끝에 도달할 때까지 3단계를 반복합니다.
다른 시퀀스의 나머지 모든 요소를 병합된 시퀀스의 끝에 직접 복사합니다.
다음과 같이 코드 코드를 복사합니다 .
public static int[] mergeSort(int[] arr) {//병합 정렬--재귀
if (arr. 길이 == 1) {
반환 도착;
}
int half = arr.length / 2;
int[] arr1 = 새로운 int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//병합 정렬 서브루틴
int[] result = new int[arr1.length + arr2.length];
int i = 0;
정수 j = 0;
정수 k = 0;
동안 (참) {
if (arr1[i] < arr2[j]) {
결과[k] = arr1[i];
if (++i > arr1.length - 1) {
부서지다;
}
} 또 다른 {
결과[k] = arr2[j];
if (++j > arr2.length - 1) {
부서지다;
}
}
k++;
}
for (; i < arr1.length; i++) {
결과[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
결과[++k] = arr2[j];
}
결과 반환;
}
전체 코드(QuickSort 제외)
다음과 같이 코드 코드를 복사합니다 .
패키지 com.clzhang.sample.thinking;
import java.util.*;
/**
* 몇 가지 일반적인 정렬 알고리즘의 Java 구현
* @저자 에이서
*
*/
공개 클래스 CommonSort {
/**
* 삽입 정렬의 구체적인 알고리즘은 다음과 같습니다.
* 1. 첫 번째 요소부터 시작하여 요소가 정렬된 것으로 간주할 수 있습니다.
* 2. 다음 요소를 꺼내고 정렬된 요소 순서에서 뒤에서 앞으로 스캔합니다.
* 3. 정렬된 요소가 새 요소보다 큰 경우 해당 요소를 다음 위치로 이동합니다.
* 4. 정렬된 요소가 새 요소보다 작거나 같은 위치를 찾을 때까지 3단계를 반복합니다.
* 5. 이 위치에 새 요소를 삽입한 후
* 6. 2~5단계를 반복하세요.
*/
공개 정적 무효 삽입 정렬(int[] 데이터) {
for (int index = 1; index < data.length; index++) {
int 키 = 데이터[인덱스];
int 위치 = 인덱스;
// 더 큰 값을 오른쪽으로 이동
while (위치 > 0 && data[위치 - 1] > 키) {
데이터[위치] = 데이터[위치 - 1];
위치--;
}
데이터[위치] = 키;
}
}
/**
* 힐 정렬(Hill sorting), 많은 수의 정렬 작업에 적합한 알고리즘 구현 아이디어는 Wikipedia를 참조하세요.
*/
static <E는 Comparable<? super E>>를 확장합니다. void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, . ..
(; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
/**
* 버블정렬 알고리즘의 동작은 다음과 같습니다.
* 1. 인접 요소를 비교합니다. 첫 번째 것이 두 번째 것보다 크면 둘 다 교환하세요.
* 2. 처음의 첫 번째 쌍부터 끝의 마지막 쌍까지 인접한 요소의 각 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소가 가장 큰 숫자가 되어야 합니다.
* 3. 마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.
* 4. 비교할 숫자 쌍이 더 이상 없을 때까지 매번 더 적은 수의 요소에 대해 위 단계를 계속 반복합니다. [1]
*/
공개 정적 무효 bubbleSort(int[] 데이터) {
정수 온도 = 0;
for (int i = data.length - 1; i > 0; --i) {
부울 isSort = false;
for (int j = 0; j < i; ++j) {
if (데이터[j + 1] < 데이터[j]) {
온도 = 데이터[j];
데이터[j] = 데이터[j + 1];
데이터[j + 1] = 온도;
isSort = 참;
}
}
// 내부 루프에서 교환이 발생하면 비교를 계속하고, 내부 루프에서 교환이 발생하지 않으면 정렬된 것으로 간주됩니다.
if (!isSort)
부서지다;
}
}
/**
* 선택 정렬의 기본 아이디어는 다음과 같습니다.
* 1. 배열을 순회하는 과정에서 i가 현재 정렬이 필요한 시퀀스 번호를 나타낸다면 나머지 [i+1...n-1] 중에서 최소값을 찾아야 합니다.
* 2. 그런 다음 찾은 최소값을 i가 가리키는 값과 교환합니다.
* 요소를 결정하는 각 프로세스에는 최소값을 선택하는 하위 프로세스가 있으므로 사람들은 이를 선택 정렬이라고 생생하게 부릅니다.
* @param 데이터
*/
공개 정적 무효 selectSort(int[] 데이터) {
int minIndex = 0;
정수 온도 = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //정렬되지 않은 영역의 최소 데이터 배열 인덱스
for (int j = i + 1; j < data.length; j++) { // 정렬되지 않은 영역에서 가장 작은 데이터를 찾아 배열 첨자를 저장합니다.
if (데이터[j] < 데이터[최소 인덱스]) {
최소지수 = j;
}
}
if (minIndex != i) { // 순서가 지정되지 않은 영역의 최소 위치가 기본 첫 번째 데이터가 아닌 경우 교환합니다.
온도 = 데이터[i];
데이터[i] = 데이터[최소인덱스];
데이터[최소인덱스] = 온도;
}
}
}
/**
* 병합 작업 과정은 다음과 같습니다.
* 1. 정렬된 두 시퀀스의 합이 되도록 공간을 적용합니다. 이 공간은 병합된 시퀀스를 저장하는 데 사용됩니다.
* 2. 두 개의 포인터를 설정합니다. 초기 위치는 두 개의 정렬된 시퀀스의 시작 위치입니다.
* 3. 두 포인터가 가리키는 요소를 비교하여 상대적으로 작은 요소를 선택하여 병합 공간에 넣은 후 포인터를 다음 위치로 이동합니다.
* 4. 포인터가 시퀀스의 끝에 도달할 때까지 3단계를 반복합니다.
* 5. 다른 시퀀스의 나머지 요소를 모두 병합된 시퀀스의 끝 부분에 직접 복사합니다.
*/
public static int[] mergeSort(int[] arr) {//병합 정렬--재귀
if (arr. 길이 == 1) {
반환 도착;
}
int half = arr.length / 2;
int[] arr1 = 새로운 int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//병합 정렬 서브루틴
int[] result = new int[arr1.length + arr2.length];
int i = 0;
정수 j = 0;
정수 k = 0;
동안 (참) {
if (arr1[i] < arr2[j]) {
결과[k] = arr1[i];
if (++i > arr1.length - 1) {
부서지다;
}
} 또 다른 {
결과[k] = arr2[j];
if (++j > arr2.length - 1) {
부서지다;
}
}
k++;
}
for (; i < arr1.length; i++) {
결과[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
결과[++k] = arr2[j];
}
결과 반환;
}
개인 정적 무효 printArray(int[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
공개 정적 무효 메인(문자열 []args){
int[] 데이터 = {10,4,9,23,1,45,27,5,2};
System.out.println("bubbleSort...");
int[] a = data.clone();
printArray(a);
버블정렬(a);
printArray(a);
System.out.println("selectSort...");
int[] b = data.clone();
printArray(b);
선택정렬(b);
printArray(b);
System.out.println("insertionSort...");
int[] c = data.clone();
printArray(c);
삽입정렬(c);
printArray(c);
System.out.println("shellSort...");
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<data.length;i++)
list.add(data[i]);
System.out.println(목록);
쉘정렬(목록);
System.out.println(목록);
System.out.println("mergeSort...");
int[] d = data.clone();
printArray(d);
printArray(mergeSort(d));
}
}