계산 정렬

다음은 정수 배열 또는 정수로 키가 지정된 구조체에 사용하는 정렬 알고리즘입니다. 정수 범위가 입력 크기 순서일 때 특히 유용합니다.

주요 아이디어는 정수의 발생 빈도를 결정하고 이를 사용하여 정렬 순서를 결정하는 것입니다.

예: {1,3,1,2} 배열을 얻었다고 가정해 보겠습니다.

먼저 이 입력에 대한 정수 범위, 최대값과 최소값, 1과 3을 결정합니다.

다음으로 배열을 만들고 이를 counts 배열이라고 부릅니다. 즉, 정수 범위+1의 크기이므로 이 경우에는 3(3-1+1)입니다.
입력 배열을 반복하여 적절한 항목의 개수를 늘립니다. 주어진 입력 값의 개수는 counts[value - min]에 배치됩니다. 주어진 입력에 대해 counts[0]은 값 1에 대한 카운트를 유지합니다.

이 결과는 개수 배열: {2,1,1}

이제 기본적으로 counts[i] = counts[i-1]+counts[i]인 누적 개수를 결정합니다.

이렇게 하면 누적 개수 배열이 생성됩니다: {2,3,4}

정렬된 입력에 대한 출력 배열을 만듭니다.

이제 입력을 역순으로 반복합니다.

각 단계에서 입력 배열의 값에 대한 누적 개수를 검색합니다. 값은 검색된 개수 - 1에 해당하는 출력 배열 인덱스에 배치됩니다. 그런 다음 누적 개수 값을 감소시킵니다.

첫 번째 단계에서는 값 2가 검색되고 누적 개수는 3입니다. 값은 출력에서 ​​인덱스 2(3-1)에 배치되어야 합니다.

다음 반복에서는 값이 1이고 누적 개수가 2입니다. 그래서 이 '1'은 출력의 인덱스 1(2-1)에 배치됩니다.

계속해서 값은 3이고 누적 개수는 4입니다. 출력의 인덱스 3에 배치합니다.

마지막으로 두 번째 값은 1이고 누적 개수는 1입니다(처음 볼 때 개수가 감소했기 때문에). 따라서 이 '1'은 출력의 인덱스 0에 배치됩니다.

, 역순으로 반복하여 동일한 요소의 순서를 유지하여 정렬을 '안정'하게 만드는 방법을 확인하세요

결과로 정렬된 배열은 {1,1,2,3}입니다.

func CountingSort(in []int) []int {
    // find the min/max values
    min := slices.Min(in)
    max := slices.Max(in)
    // create the count array
    counts := make([]int, max-min+1)
    for _, v := range in {
        counts[v-min]++
    }
    // determine cumulative counts
    for i := 1; i < len(counts); i++ {
        counts[i] = counts[i-1] + counts[i]
    }
    // create the output array
    out := make([]int, len(in))
    for i := range in {
        v := in[len(in)-1-i]
        out[counts[v-min]-1] = v
        counts[v-min]--
    }
    return out
}

좀 더 효율적으로 만들 수 있을까요? 아래에 의견과 제안을 남겨주세요.

감사합니다!

이 게시물의 코드와 이 시리즈의 모든 게시물은 여기에서 확인할 수 있습니다

위 내용은 계산 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!