javascript_javascript 기술의 8가지 주요 정렬 구현에 대한 간략한 토론

학년이 시작된 지 한 달 만에 저는 필기 시험에 데이터 구조 알고리즘 문제가 나타나는 꿈을 여러 번 꿨습니다. 그 어떤 '유령'보다 데이터 구조가 더 두렵습니다. 하하, 그 '악몽'이 현실이 되는 것을 막기 위해서는 일반적으로 사용되는 데이터 구조를 검토하는 것이 정말 필요한 것 같습니다.

데이터 구조 등 프로그래밍 기본의 중요성은 말할 필요도 없이 바로 본론으로 들어가겠습니다.

정렬 알고리즘은 내부 정렬과 외부 정렬로 구분됩니다. 내부 정렬은 메모리를 사용하므로 여기서는 내부 정렬만 설명합니다.

1. 삽입 정렬: 직접 삽입 정렬과 Hill 정렬

2. 선택 정렬: 단순 선택 정렬과 힙 정렬

3. 교환 정렬: 버블 정렬과 퀵 정렬

4, 병합 정렬

5, 기수 정렬

직접 삽입 정렬

기본 아이디어: 정렬할 숫자 집합에서 이전 (n-1) [n>=2] 숫자가 이미 순서대로 되어 있다고 가정하고 먼저 이전 순서 숫자에 n번째 숫자를 삽입합니다. 이 n개 숫자도 정렬되어 있습니다. 모든 것이 정상화될 때까지 이 주기를 반복합니다.

힐 정렬

기본 아이디어: 알고리즘은 먼저 정렬할 숫자 집합을 특정 증분 d(n/2, n은 정렬할 숫자)에 따라 여러 그룹으로 나누고, 각 그룹에 기록된 첨자는 d에 따라 다릅니다. . 각 그룹의 모든 요소에 대해 직접 삽입 정렬을 수행한 다음 더 작은 증분(d/2)으로 그룹화하고 각 그룹에 대해 직접 삽입 정렬을 수행합니다. 증분이 1로 줄어들면 직접 삽입 정렬 후 정렬이 완료됩니다.

간단한 선택 정렬

기본 아이디어: 정렬할 숫자 집합에서 가장 작은 숫자를 선택하여 첫 번째 위치의 숫자와 교환하고, 나머지 숫자 중에서 가장 작은 숫자를 찾아 두 번째 위치의 숫자와 교환합니다. , 그러니까 ㅋㅋㅋ 끝에서 두 번째부터 마지막 ​​숫자까지 찾아보세요.

힙 정렬

기본 아이디어: 힙 정렬은 직접 선택 정렬을 효과적으로 개선한 트리 선택 정렬입니다.

n개 요소가 있는 시퀀스(h1, h2,...,hn), (hi>=h2i,hi>=2i 1) 또는 (hi<=h2i,hi<2i 1 ) ( i=1,2,...,n/2)을 힙이라고 합니다. 여기서는 이전 조건을 충족하는 힙만 논의합니다. 힙의 정의를 보면 힙의 최상위 요소(즉, 첫 번째 요소)가 가장 큰 항목(빅탑 힙)이어야 함을 알 수 있습니다. 완전한 이진 트리는 힙의 구조를 매우 직관적으로 나타낼 수 있습니다. 힙의 맨 위는 루트이고 나머지는 왼쪽 하위 트리와 오른쪽 하위 트리입니다. 처음에는 정렬할 숫자의 순서를 순차적으로 저장된 이진 트리로 간주하고 저장 순서를 조정하여 힙이 되도록 합니다. 이때 힙의 루트 노드 수가 가장 많습니다. 그런 다음 루트 노드를 힙의 마지막 노드로 바꿉니다. 그런 다음 이전 (n-1) 숫자를 다시 조정하여 힙을 형성합니다. 그런 식으로 두 개의 노드만 있는 힙이 있을 때까지 계속해서 교환되고, 마지막으로 n개의 노드로 구성된 순서화된 시퀀스가 ​​얻어집니다. 알고리즘 설명에 따르면 힙 정렬에는 두 가지 프로세스가 필요합니다. 하나는 힙을 설정하는 것이고, 다른 하나는 힙의 상단과 힙의 마지막 요소 사이의 위치를 ​​교환하는 것입니다. 따라서 힙 정렬은 두 가지 기능으로 구성됩니다. 하나는 힙을 구축하기 위한 침투 함수이고, 다른 하나는 정렬을 구현하기 위해 침투 함수를 반복적으로 호출하는 함수입니다.

버블정렬

기본 아이디어: 정렬할 숫자 집합에서 아직 정렬되지 않은 범위의 모든 숫자에 대해 인접한 두 숫자를 위에서 아래로 순서대로 비교하고 조정하여 더 큰 숫자가 가라앉도록 합니다. 그리고 작은 것들이 올라갑니다. 즉, 인접한 두 숫자를 비교할 때 순서가 순서 요구 사항과 반대라는 것이 발견될 때마다 서로 교체됩니다.

빠른 정렬

기본 아이디어: 벤치마크 요소(보통 첫 번째 요소 또는 마지막 요소)를 선택하고 정렬할 시퀀스를 한 번의 스캔을 통해 두 부분으로 나누고, 한 부분은 벤치마크 요소보다 작고, 다른 부분은 벤치마크 요소보다 큽니다. 또는 벤치마크 요소와 동일합니다. 이때 벤치마크 요소는 올바른 정렬 위치에 있으며 두 개의 분할된 부분은 동일한 방식으로 재귀적으로 정렬됩니다.

병합 정렬

기본 정렬: 병합 정렬 방법은 두 개(또는 그 이상)의 순서 목록을 새로운 순서 목록으로 병합하는 것입니다. 즉, 정렬할 시퀀스를 여러 하위 시퀀스로 나누고 각 하위 시퀀스는 순차적입니다. 그런 다음 정렬된 하위 시퀀스를 전체 정렬된 시퀀스에 병합합니다.

기수 정렬

기본 아이디어: 비교할 모든 값(양의 정수)을 동일한 자릿수로 통일하고, 자릿수가 짧은 숫자 앞에는 0을 추가합니다. 그런 다음 가장 낮은 비트부터 시작하여 하나씩 정렬합니다. 이런 방식으로 가장 낮은 비트부터 가장 높은 비트까지 정렬한 후 순서가 지정된 시퀀스가 ​​됩니다.

코드 데모 주소: http://lovermap.sinaapp.com/test/sort.html

이제 8가지 정렬 알고리즘의 안정성을 분석해 보겠습니다.

(네티즌들은 이전에 정렬의 기본 아이디어를 결합하여 정렬의 안정성을 이해하도록 요청받습니다(8가지 정렬의 기본 아이디어는 이전에 언급되었으며 여기서 반복하지 않습니다). 그렇지 않으면 다소 모호할 수 있습니다)

(1) 직접 삽입 정렬 : 일반적인 삽입 정렬에서는 순서가 지정된 시퀀스의 마지막 요소부터 비교가 시작되며, 그보다 크면 바로 뒤에 삽입되고, 그렇지 않으면 유지됩니다. 앞으로 비교. 삽입된 요소와 동일한 요소가 발견되면 동일한 요소 뒤에 삽입됩니다. 삽입 정렬이 안정적입니다.

(2) 힐 정렬 : 힐 정렬은 서로 다른 동기화 길이에 따라 요소를 삽입 정렬하는 것입니다. 삽입 정렬은 안정적이며 동일한 요소의 상대적 순서를 변경하지 않지만 다른 동안에는 삽입 정렬 과정에서 동일한 요소가 각각의 삽입 정렬에서 이동할 수 있으며 안정성이 파괴되므로 Hill 정렬이 불안정합니다.

(3) 단순 선택 정렬 : 한 선택에서 현재 요소가 요소보다 작고 작은 요소가 현재 요소와 동일한 요소 뒤에 나타나면 이후에는 안정적입니다. 교환 섹스는 파괴됩니다. 말하기가 다소 모호할 수 있습니다. 작은 예를 살펴보겠습니다. 858410, 첫 번째 스캔에서 첫 번째 요소 8은 4로 교환되고 원래 시퀀스에서 두 8의 상대적 순서는 일치하지 않습니다. 원본 순서이므로 선택 정렬이 불가능합니다.

(4) 힙 정렬 : 힙 정렬 프로세스는 n/2번째와 해당 하위 노드부터 시작하여 가장 큰(큰 상단 힙) 또는 가장 작은(작은 상단 힙)을 선택하는 것입니다. 총 3가지 값이 있습니다. 이는 3가지 요소 중 하나를 선택한다고 해서 안정성이 파괴되는 것은 아닙니다. 그러나 상위 노드 n/2-1, n/2-2, ...에 대한 요소를 선택할 때 n/2번째 상위 노드가 다음 요소를 교환하고 n/2-1번째 상위 노드는 그렇지 않은 경우가 가능합니다. 마지막에 동일한 요소를 교환하므로 힙 정렬이 안정적이지 않습니다.

(5) 버블 정렬 : 이전 내용에서 볼 수 있듯이 버블 정렬은 인접한 두 요소를 비교하며, 두 요소가 같을 경우 교환도 발생합니다. 교환할 필요가 없습니다. 따라서 버블 정렬은 안정적입니다.

(6) 퀵 정렬: 중심 요소가 순서의 요소로 바뀌면 이전 요소의 안정성이 깨질 가능성이 매우 높습니다. 작은 예를 살펴보겠습니다: 6 4 4 5 4 7 8 9. 첫 번째 정렬 단계에서 중앙 요소 6과 세 번째 4를 교환하면 요소 4의 원래 순서가 파괴되므로 퀵 정렬이 불안정합니다.

(7) 병합 정렬 : 분해된 하위 열에 요소가 1개 또는 2개 있을 때 1개 요소는 교환되지 않고, 크기가 같은 2개 요소는 교환되지 않습니다. . 시퀀스 병합 프로세스 중에 두 개의 현재 요소가 동일하면 결과 시퀀스 앞에 이전 시퀀스의 요소를 저장하므로 병합 정렬도 안정적입니다.

(8) 기수 정렬 : 먼저 낮은 순서로 정렬한 다음 높은 순서로 정렬한 다음 가장 높은 순서까지 수집합니다. 일부 속성에는 우선순위가 낮은 순서로 정렬된 다음 높은 우선순위로 정렬되는 경우가 있습니다. 최종 순서는 높은 우선순위와 낮은 우선순위가 동일한 순서로 정렬되는 것입니다. 기수 정렬은 분리 정렬과 분리 수집을 기반으로 하므로 안정적입니다.

8가지 정렬 방법의 분류, 안정성, 시간 복잡도, 공간 복잡도 요약:

위 내용은 이 글의 전체 내용입니다. 모두 마음에 드셨으면 좋겠습니다.