Golang의 빠른 분류

이 게시물Quick Sort in Golang은 처음Qvault에 실렸다.
빠른 정렬은 효율적인 정렬 알고리즘으로 생산 정렬 실현에 광범위하게 응용된다.merge sort와 유사하게 빠른 정렬은divide and conquer algorithm이다.이름이 말한 바와 같이 빠른 정렬은 가장 빠른 정렬 알고리즘 중의 하나이다. 즉, 세부 사항을 조심스럽게 실현해야 한다. 조심하지 않으면 속도가 곧 떨어질 수 있기 때문이다.

갈라놓다

피봇 컴포넌트를 선택하고 스플라인

의 중심에 가장 가깝게

모든 물체를 추축

의'크다'또는'작다'쪽으로 이동

피봇이 최종 위치에 있음

피벗

양쪽에서 반복

정복하다

모든 원소가 투시 조작

을 완료한 후 정렬 그룹을 되돌려줍니다

빠른 정렬 위조 코드

Golang() 배분 함수

빠른 정렬은 실제로 두 개의 함수, 주함수quicksort()와 함수partition()를 사용했다.알고리즘의 핵심은 partition() 함수에 반직각적으로 존재한다.그것은 추축을 찾아서 모든 물건을 추축의 정확한 쪽으로 이동하는 것을 책임진다.

Go에서 전체 코드는 다음과 같습니다.

func partition(arr []int, low, high int) ([]int, int) {
    pivot := arr[high]
    i := low
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            arr[i], arr[j] = arr[j], arr[i]
            i++
        }
    }
    arr[i], arr[high] = arr[high], arr[i]
    return arr, i
}

<small id="shcb-language-1"><span>Code language:</span> <span>Go</span> <span>(</span><span>go</span><span>)</span></small>

Golang의 QuickSort() 함수

quickSort() 함수는 사실상 구역 함수의 포장기일 뿐 처리 알고리즘의 귀속 성질이다.

func quickSort(arr []int, low, high int) []int {
    if low < high {
        var p int
        arr, p = partition(arr, low, high)
        arr = quickSort(arr, low, p-1)
        arr = quickSort(arr, p+1, high)
    }
    return arr
}`
<small id="shcb-language-2"><span>Code language:</span> <span>Go</span> <span>(</span><span>go</span><span>)</span></small>

실제 코드에서 빠른 정렬을 사용하는 예시

fmt.Println(quickSortStart([]int{5, 6, 7, 2, 1, 0))
// prints
// [0, 1, 2, 5, 6, 7]`
<small id="shcb-language-3"><span>Code language:</span> <span>Go</span> <span>(</span><span>go</span><span>)</span></small>

빠른 정렬을 사용하는 이유는 무엇입니까?

평균적으로 빠른 정렬의 최대치는 O(n*log(n))이다.최악의 경우, 우리가 어떠한 조치도 취하지 않고 자신을 보호한다고 가정하면, 그것은 O(n^2) 로 분해될 수 있다.partition() 함수는 for 순환이 있는데, 범위는 수조의 최저 인덱스에서 최고 인덱스까지입니다.partition() 함수 자체가 O(n)이다.빠른 정렬의 전체적인 복잡성은 호출 횟수partition()에 달려 있다.
최악의 경우 입력이 정렬되었습니다.모든 pivot 수조에서 가장 큰 원소나 정렬된 pivot 수조에서 가장 작은 원소입니다.이 경우 partition()는 모두 n회로 불린다.가장 좋은 상황에서 pivot는 모든 하위 목록의 중간 요소로 log(n) 호출partition()을 초래할 수 있다.
빠른 정렬에는 다음과 같은 속성이 있습니다.

일반적인 상황에서 매우 빠릅니다

.

현지: 메모리 절약, 대량 복제 및 할당 불필요

더 복잡한 실현

보통 불안정: 같은 키로 요소의 상대적인 순서를 변경

빠른 정렬에서 빠른 실행 보장

우리가 실현한quicksort버전은 거의 항상 O(n*log(n))의 속도로 실행될 수 있지만, 그것의 거대한 복잡성은 기술적으로 여전히 O(n^2)이다.우리는 알고리즘을 조금 바꾸어 이 문제를 해결할 수 있다.다음과 같은 두 가지 방법이 있습니다.

정렬 전 무작위 카드 세탁 입력.이것은 O(n) 시간 안에 완성할 수 있다.

주동적으로 구역에서 데이터 샘플의 중치를 찾으면 O(1) 시간 안에 완성할 수 있다.

무작위 카드 세탁 최적화

무작위 방법은 인코딩하기 쉬우며 거의 항상 유효하기 때문에 자주 사용한다.이렇게 하는 목적은 목록을 정렬하기 전에 카드를 빨리 씻는 것이다.천문학적 관점에서 보면 정렬 목록에 들어갈 가능성이 크지 않고 입력이 클수록 가능성도 작다.

중치 최적화 찾기

가장 유행하는 해결 방안 중 하나는'3분의 1'을 사용하는 방법이다.각 파티션의 세 요소(예: 첫 번째, 중간 및 마지막 요소)를 선택하고 그 사이에 중간 값을 찾습니다.그런 다음 항목을 피벗으로 사용합니다.이런 방법의 장점은 O(n^2)시간으로 분해할 수 없다는 것이다. 왜냐하면 우리는 구역 중 최악의 항목을 축으로 영원히 사용하지 않을 것을 보장하기 때문이다.진정한 중치를 사용하지 않았기 때문에, 그것은 여전히 느릴 수 있다는 것이다.
인코딩 시작할 준비 됐어요?
Try our coding courses free
Join our Discord community

질문이나 피드백이 있습니까?

질문이나 댓글이 있으면 팔로우하고 트위터에 연락 주세요.만약 내가 문장에서 잘못을 저질렀다면, 반드시 let me know해야 한다. 그러면 나는 그것을 바로잡을 수 있다.