>  기사  >  백엔드 개발  >  일반적으로 사용되는 정렬 알고리즘에 대한 동적 다이어그램 설명

일반적으로 사용되는 정렬 알고리즘에 대한 동적 다이어그램 설명

Y2J
Y2J원래의
2017-04-25 10:55:523969검색

이 글은 시각적으로 직관적이고 참고할만한 가치가 있는 일반적으로 사용되는 여러 가지 정렬 알고리즘을 주로 사용합니다. 관심 있는 친구들은

을 참조하여 일반적으로 사용되는 여러 가지 정렬 알고리즘을 직관적으로 경험해 볼 수 있습니다

1 퀵 정렬

소개:

퀵 정렬은 Tony Hall 알고리즘에서 개발한 정렬입니다. 평균적으로 n개 항목을 정렬하려면 O(n log n) 비교가 필요합니다. 최악의 경우에는 O(n2) 비교가 필요하지만 이런 상황은 흔하지 않습니다. 실제로 퀵 정렬은 내부 루프가 대부분의 아키텍처에서 효율적으로 구현될 수 있고 대부분의 실제 응용 프로그램에서 잘 작동하기 때문에 다른 Ο(n log n) 알고리즘보다 훨씬 빠른 경우가 많습니다. 데이터가 설계 선택을 결정하여 2차 항의 가능성을 줄입니다. 필요한 시간에.

단계:

시퀀스에서 "pivot"이라는 요소를 선택하고

시퀀스를 재정렬하고 피벗 값보다 작은 모든 요소를 ​​피벗 앞에 배치합니다. 기본 값보다 큰 숫자는 기본 뒤에 배치됩니다(같은 숫자가 양쪽에 올 수 있음). 이 파티션이 종료된 후 베이스는 시퀀스의 중간에 있습니다. 이를 파티션 작업이라고 합니다.
기준 값보다 작은 요소의 하위 배열과 기준 값보다 큰 요소의 하위 배열을 재귀적으로 정렬합니다.

정렬 효과:

2 병합 정렬

소개:

병합 정렬(Merge Sort, 대만어 번역: 병합 정렬)은 병합 연산을 기반으로 하는 효과적인 정렬 알고리즘입니다. 이 알고리즘은 분할 정복 방법(pide 및 Conquer)을 사용하는 매우 일반적인 응용 프로그램입니다

단계:

크기가 정렬된 두 시퀀스의 합이 되도록 공간을 적용하고 공간 병합된 시퀀스를 저장하려면

포인터 두 개를 설정하고, 초기 위치는 정렬된 두 시퀀스의 시작 위치입니다.
두 포인터가 가리키는 요소를 비교하여 상대적으로 작은 요소를 선택하여 병합 공간에 넣습니다. , 포인터를 다음 위치로 이동
특정 포인터가 시퀀스의 끝에 도달할 때까지 3단계를 반복합니다
다른 시퀀스의 나머지 요소를 모두 병합된 시퀀스의 끝에 직접 복사합니다

정렬 효과 :

3 힙 정렬

소개:

힙 정렬을 참조 힙의 데이터 구조를 위해 설계된 정렬 알고리즘을 사용합니다. 힙은 완전한 이진 트리에 근접하고 힙 속성을 만족하는 구조입니다. 즉, 하위 노드의 키 값 또는 인덱스는 항상 상위 노드보다 작거나 큽니다.

단계:

(더 복잡합니다. 온라인에서 확인하세요.)

정렬 효과:

4 선택 정렬

소개:

선택 정렬은 간단하고 직관적인 정렬 알고리즘입니다. 작동 방식은 다음과 같습니다. 먼저 정렬되지 않은 시퀀스에서 가장 작은 요소를 찾아 정렬된 시퀀스의 시작 부분에 저장한 다음, 정렬되지 않은 나머지 요소에서 계속해서 가장 작은 요소를 찾아 정렬된 시퀀스의 끝에 넣습니다. 모든 요소가 정렬될 때까지 계속됩니다.

정렬 효과:

5 버블 정렬

소개:

버블 정렬(Bubble Sort, 대만에서 번역: Bubble Sort 또는 Bubble Sort)은 간단한 정렬 알고리즘입니다. 정렬할 시퀀스를 반복적으로 살펴보며 한 번에 두 요소를 비교하고 순서가 잘못된 경우 교체합니다. 더 이상 교환이 필요하지 않을 때까지 어레이 방문 작업이 반복됩니다. 이는 어레이가 정렬되었음을 의미합니다. 이 알고리즘의 이름은 작은 요소가 스와핑을 통해 배열의 맨 위로 천천히 "부동"된다는 사실에서 유래되었습니다.

단계:

인접한 요소를 비교합니다. 첫 번째 것이 두 번째 것보다 크면 둘 다 교환하세요.

첫 번째 쌍에서 시작하여 마지막 쌍으로 끝나는 각 인접 요소 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소가 가장 큰 숫자가 되어야 합니다.
마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다.
비교할 숫자 쌍이 더 이상 없을 때까지 매번 요소 수를 줄여 위 단계를 계속 반복합니다.

정렬 효과:

6 삽입 정렬

소개:

삽입 정렬의 알고리즘 설명은 간단하고 직관적인 정렬 알고리즘입니다. 정렬되지 않은 데이터의 경우 정렬된 시퀀스의 뒤에서 앞으로 스캔하여 해당 위치를 찾아 삽입합니다. 삽입 정렬의 구현에서는 일반적으로 내부 정렬(즉, O(1) 추가 공간만 사용하는 정렬)이 사용됩니다. 따라서 뒤에서 앞으로 스캔하는 동안 정렬된 요소를 반복적이고 점진적으로 수행해야 합니다. 뒤로 이동하여 최신 요소에 대한 삽입 공간을 제공합니다.

단계:

정렬된 것으로 간주할 수 있는 첫 번째 요소부터 시작
다음 요소를 꺼내고 정렬된 요소 순서에서 뒤에서 앞으로 스캔
(정렬된) 요소가 새 요소보다 큰 경우 해당 요소를 다음 위치로 이동합니다.
정렬된 요소가 새 요소보다 작거나 같은 위치를 찾을 때까지 3단계를 반복합니다.
새 요소 삽입 해당 위치에 요소를

7 Hill 정렬

에서 2단계를 반복합니다. 소개:

Hill 정렬(내림차순이라고도 함) 증분 정렬 알고리즘은 삽입 정렬의 빠르고 안정적인 개선 버전입니다.

힐 정렬은 삽입 정렬의 다음 두 가지 속성을 기반으로 개선된 방법을 제안합니다.

삽입 정렬은 거의 정렬된 데이터를 연산할 때 매우 효율적입니다. 선형 정렬의 효율성
그러나 삽입 정렬은 한 번에 한 비트씩만 데이터를 이동할 수 있기 때문에 일반적으로 비효율적입니다.

정렬 효과:

위 내용은 일반적으로 사용되는 정렬 알고리즘에 대한 동적 다이어그램 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.