Radixsort로 배열 정렬

Question

현재 Radixsort를 이해하려고하고 있으며 이에 대한 간단한 질문이 있습니다. 내가 기수 정렬로 정렬 할 아주 나쁜 생각은 무엇

이며, 아래의 배열 :

"9999 ... 9, 9999 ... 9, 9999 ... 9"

때문에 Radixsort는 배열에서 첫 번째, 두 번째 및 세 번째 숫자의 모든 단일 숫자를 비교합니다. 따라서이 배열에 다른 정렬 알고리즘을 사용하는 것이 좋습니다. Radixsort와 정렬하기에 매우 불리한 다른 배열이 있습니까? 기수의

안부

Answer 1

시간 비용은 일종의 O (㎚) 여기서 N은 소자들의 수이고, m은 요소의 복잡성이다. 당신 말이 맞습니다. 더 빠르지 않은 경우가 있습니다. 긴 정수 문자열의 경우 m은 logn을 초과 할 수 있습니다. nlogn은 예를 들어 병합 정렬의 시간 비용입니다.