>

중복 데이터로 배열을 배열 할 때 빠른 정렬 속도가 덜 효율적이라고 생각합니까? 데이터 유형이 char이면 배열이 100000 이상 일수록 n ^ 2 순서에 가까워집니다. 중복 데이터가 없다고 가정하면 첫 번째 요소가 피벗으로 배치되는 첫 번째 요소 인 빠른 정렬의 가장 좋은 경우를 얻습니다. 첫 번째 요소 권리? 가장 좋은 경우가 있습니까?

  • 답변 # 1

    파티션 중 한쪽 끝에서 다른 쪽 끝까지 스캔하는 Lomuto 파티션 구성표는 복제 속도가 느려집니다. 모든 값이 동일하면 각 파티션 단계는 최악의 시나리오 인 1과 n-1 크기로 분할합니다.

    인덱스 (또는 이터레이터 또는 포인터)가 교차 할 때까지 양쪽 끝에서 서로를 향해 스캔하는 Hore 파티션 구성표는 일반적으로 복제 속도가 빠릅니다. 중복으로 인해 더 많은 스왑이 발생하더라도 각 스왑은 두 값을 읽은 후 피벗과 비교 한 직후에 발생하며 여전히 스왑 캐시에 있습니다 (객체 크기가 크지 않다고 가정). 복제 수가 증가함에 따라 분할은 각 파티션 단계가 데이터를 두 개의 동일한 반으로 나누는 이상적인 경우를 향해 향상됩니다. 1 천 6 백만 64 비트 정수를 정렬하는 벤치 마크를 실행했습니다. 무작위 데이터의 경우 약 1.37 초가 걸렸으며 중복으로 개선되었으며 모든 값이 동일하면 약 0.288 초가 걸렸습니다.

    또 다른 대안은 파티션을 요소<피벗, 요소 == 피벗, 요소>피벗으로 분할하는 3 방향 파티션입니다. 모든 요소가 동일하면 O (n) 시간 안에 완료됩니다. k 개의 가능한 값만있는 n 개의 요소의 경우 시간 복잡도는 O (n ⌈log3 (k) ⌉)이고, k가 일정하기 때문에 시간 복잡도는 여전히 O (n)입니다.

    위키 링크 :

    https://en.wikipedia.org/wiki/Quicksort#Repeated_elements

    https://en.wikipedia.org/wiki/Dutch_national_flag_problem

  • 이전 c# - reddits 게시물 정렬과 유사한 기능을 구현하는 동안 전환 사례를 피하는 방법
  • 다음 IIS appsettingsjson을 사용하여 닷넷 코어에서 Angular 6 URL 다시 쓰기를 구성하는 방법