기본적인 정렬 방법은 무엇입니까?-일반적인 문제-php.cn

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

藏色散人

풀어 주다： 2020-07-02 09:41:45

원래의

3354명이 탐색했습니다.

기본 정렬 방법은 다음과 같습니다. 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)