>  기사  >  기본적인 정렬 방법은 무엇입니까?

기본적인 정렬 방법은 무엇입니까?

藏色散人
藏色散人원래의
2020-07-02 09:41:453325검색

기본 정렬 방법은 다음과 같습니다. 1. 선택 정렬은 "단순 선택 정렬"과 "힙 정렬"로 구분됩니다. 2. 삽입 정렬은 "단순 삽입 정렬"과 "힐 정렬"로 구분됩니다. 정렬은 "버블 정렬"과 "빠른 정렬"로 구분됩니다. 4. 병합 정렬 5. 기수 정렬.

기본적인 정렬 방법은 무엇입니까?

기본 정렬 방법

sorting

어떤 상황에서도 최적의 정렬 알고리즘은 없습니다. 실제 상황에 따라 문제를 해결하려면 최적의 알고리즘을 선택해야 합니다

알고리즘은 안정적입니다. : 정렬할 레코드 집합에서 두 개의 동일한 레코드 R과 S가 있고, 정렬할 레코드에서 R이 S 앞에 있고, 정렬 후에도 R이 여전히 S 앞에 있다면, 즉 해당 레코드는 앞뒤 위치가 정렬 중입니다. 정렬 알고리즘은

  • Selection Sort

Simple Selection Sort

Simple Selection Sort(간단 선택 정렬)은 unsorted에 작동하는 직관적인 정렬 알고리즘은 시퀀스에서 가장 작은 요소를 선택하여 시퀀스의 첫 번째 요소와 교환한 다음, 정렬되지 않은 나머지 시퀀스에서 가장 작은 요소를 선택하여 시퀀스의 두 번째 요소와 교환하며, Sequence

시간 복잡도: O(N2)

Heap sort

정렬되지 않은 시퀀스를 최대 힙으로 생성하고 힙의 최상위 요소를 마지막 요소로 교체합니다. 나머지 요소를 최대 힙으로 생성하고 요소를 순차적으로 진행합니다. 교환 및 최대 힙 생성

시간 복잡도: O(NlogN) 공간 복잡도: O(1)

  • 삽입 정렬

단순 삽입 정렬

정렬할 시퀀스 집합 나누기 정렬된 부분과 정렬되지 않은 부분의 두 부분이 있습니다. 초기 상태에서 정렬된 시퀀스에는 첫 번째 요소만 포함되고 정렬되지 않은 시퀀스의 요소는 다음을 제외한 N-1개의 요소입니다. 그 이후에는 정렬되지 않은 시퀀스의 요소가 정렬된 시퀀스에 하나씩 삽입됩니다. 이런 식으로 N-1 삽입 후 정렬되지 않은 시퀀스의 요소 수가 0이 되면 정렬이 완료됩니다.

시간 복잡도: O(N2) 안정 정렬

힐 정렬

정렬할 요소 집합 일정한 간격으로 여러 개의 시퀀스로 나누어 각각 삽입 정렬을 수행합니다. 처음에 설정된 "간격"은 상대적으로 크며 "간격"이 1이 될 때까지 정렬의 각 라운드에서 간격이 점차 감소합니다. 즉, 마지막 단계는 간단한 삽입 정렬을 수행하는 것입니다

시간 복잡도: 관련 증분 시퀀스 선택 Non-stable sorting

  • Exchange sorting

Bubble sorting

N개 요소로 정렬할 시퀀스를 정렬할 때 총 N-1 루프가 수행됩니다. k번째 루프에서는 1번째부터 N-k번째까지의 요소를 앞에서 뒤로 비교하고, 인접한 두 요소를 비교할 때마다 전자의 요소가 후자의 요소보다 크면 두 위치를 교환합니다. 그렇지 않으면 위치가 변경되지 않습니다.

시간 복잡도: O(N2)

빠른 정렬

정렬되지 않은 요소를 벤치마크로 "피벗"을 기반으로 두 개의 하위 시퀀스로 나눕니다. 여기서 한 하위 시퀀스의 레코드는 피벗보다 큽니다. 다른 하위 시퀀스는 모두 피벗보다 작으며 두 하위 시퀀스는 비슷한 방법을 사용하여 재귀적으로 정렬됩니다. 길이가 1인 N개의 하위 시퀀스로 간주되고, 인접한 하위 시퀀스가 ​​쌍으로 병합되어 길이가 2(또는 1)인 N/2(+1)개의 하위 시퀀스를 형성한 다음 계속해서 인접한 하위 시퀀스를 쌍으로 병합합니다. 길이 N의 시퀀스가 ​​남아 있으면 이 시퀀스는 정렬 후 원래 시퀀스의 결과입니다. 시간 복잡도: O(Nlog2N) 공간 복잡도: O(N)

  • Radix sort

  • 버킷 정렬

N개 키워드의 값 범위가 0에서 M-1 사이이고 M이 N보다 훨씬 작은 것으로 알려진 경우 버킷 정렬 알고리즘은 키워드의 각 값, 즉 M에 대해 "버킷"을 생성합니다. N개의 키워드를 스캔하면 각 키워드가 해당 버킷에 담겨 자연스럽게 정렬됩니다

Radix sort

    Radix sort는 Bucket Sort를 일반화한 것입니다. 정렬하려면 두 개 이상의 키워드를 포함하세요

위 내용은 기본적인 정렬 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

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