링크 된 목록의 quicksort 구현?

삽입 정렬뿐 아니라 O (n^2)보다 좋은 시간에 실행되는 두 배로 연결된 목록을 정렬해야합니다. 내가 quicksort를 사용하는 것에 대해 생각하고 있었지만 알고리즘을 이해하는데 문제가있었습니다. 시작하는 데 도움이 될 수있는 이해하기 쉬운 문서로 나를 안내해 주시겠습니까?링크 된 목록의 quicksort 구현?

출처

2012-03-26 Andrew Webb

[Hungerian 민속 춤을 사용 퀵 시각화 동영상]의 알고리즘의 우수한 높은 수준의 설명이있다. –

다른 데이터 구조로 추출하여 정렬하거나, 정렬해야합니까? 배열로 추출하고, 빠른 정렬을 수행하고, 연결된 목록에 다시 넣는 것은 2n + nlogn과 같아야합니다.이 값은 여전히 n 제곱보다 작습니다. – captncraig

아니요, 다른 데이터 구조를 사용하여 노드를 저장할 수 없습니다. –

실제로는 merge sort을 권하고 싶습니다. 이중 연결리스트를 사용하는 것이 더 합리적이며, O (n log n)의 런타임을가집니다. 기본적으로 중간을 찾고 목록을 절반으로 분할하고 각 절반을 그 자체로 정렬 한 다음 선형 시간으로 두 개를 결합합니다.

C++에서 꽤 좋은 작업 구현을 가지고있는 스레드가 here인데, 자바를 배우는 경우 읽을 수있는 가장 쉬운 방법은 아니지만 좋은 출발점이 될 수 있습니다.

도 (http://www.youtube.com/watch?v=ywWBy6J5gz8) this site.

출처

2012-03-27 16:08:51 captncraig

중요한 점은 quicksort와는 달리 * 최악의 경우 * 런타임 또한'O (n * log n)'입니다. 또한 구현하기 쉽습니다 :) –

링크 된 목록의 quicksort 구현?

답변

관련 문제