순서가 지정된 배열의 배열을 효과적으로 정렬하는 방법

Question

정렬 된 숫자 시퀀스의 배열을 정렬하는 복잡한 알고리즘을 구현하고 있습니다. 전체 알고리즘은 nlog (n) 복잡이어야합니다. 따라서이 부분은 같거나 그 이상이어야하지만 어떻게해야할지 모르겠습니다.

예가 있습니다.

(0) 
(0,1) 
(0) 
(0,5) 
(2,4) 
() 
(0,5) 
() 
(2,4) 
(1,3,4) 

최종 종류가 있어야한다 : 순서의 배열이있다

몇 가지 중요한 사항이 있습니다

() 
() 
(0) 
(0) 
(0,1) 
(0,5) 
(0,5) 
(1,3,4) 
(2,4) 
(2,4) 

:

• 정렬이
• 서열 정렬 사전 편찬하지만, 연속성을 보장하지 않습니다.
• 비어있는 밀기울도 있습니다. NCES
이
• 시퀀스는 0에서 배열은 아마 더 이상
• 최종 구현은 C++로 수 없습니다 긴 100,000 될 수
• 더 이상, 수백 긴에있는 동일한 시퀀스를 많이하지만 지금은
• 아마도 중요하지 않습니다

제발 가장 좋은 방법을 제안 할 수 있습니까? 고마워요

Answer 1

quicksort를 사용하면 정렬 알고리즘은 O (n log n)가됩니다. 두 항목을 비교하는 방법은 정렬 자체의 복잡성과 관련이 없으며 고유 한 복잡성 (아마도 O (m))이 있습니다.

Answer 2

프로젝트에 GPLv3 코드를 통합 할 수 있다면 GNU Sort을 시작하는 것이 좋습니다. 최소한 샘플 입력에서 실행했을 때 샘플 출력을 얻었으므로 즉시 잘못되지는 않습니다.

Answer 3

문제는 radix sort과 비슷합니다.이 경우 가장 가까운 항목 (예 : 100 번째 항목)이없는 경우 해당 항목을 먼저 정렬하고 min possible value - 1 (예를 들어 -1이 표시 될 수 있음)으로 설정하고, 그런 다음이 정렬 된 시퀀스를 두 번째 맨 오른쪽 항목으로 정렬하고이 방법을 계속 수행하십시오.

또한 시퀀스의 항목이 모두 1..k (이 경우에는 1.9 사이에 있음을 알 수 있습니다.)를 사용하여 counting sort을 사용하여 O (n)에서 정렬하면 카운팅 정렬을 사용할 수 있습니다. 정렬 시간은 O (n)이지만 그렇지 않으면 정렬 시간은 O (n log n)입니다.