나는 자바에서 독자적으로 링크 된 목록을 만들고 정렬을 수행하는 데 사용하려고합니다. 나는 의 첫 번째 노드 인과 의 다음 노드에만 접근 할 수 있습니다.은 다음 노드를 가리키는 포인터입니다. 모든 노드에는 정수인 두 필드 x와 y가 있습니다. 내장 메서드를 사용하지 않고 연결된 요소에 요소를 추가하고 quicksort 또는 병합 정렬을 사용하여 요소를 정렬하려면 어떻게해야합니까?정렬 할 독자적으로 링크 된 목록 만들기
내장 된 방법을 사용하지 않고 연결된 목록에 요소를 추가하고 quicksort 또는 병합 정렬을 사용하여 정렬하려면 어떻게해야합니까? 퀵와 머지 소트 등
빠른 알고리즘은 요소들의 어레이가 정렬되는 수에 >> 지수 < < 존재에 의존한다; 즉, a[i] = a[j]과 같은 동작 시퀀스에있다. 연결된 목록을 사용하면 무작위 인덱싱이 O(N) 작업이됩니다. 이것은 O(N log N) 알고리즘을 O(N^2 log N) 알고리즘으로 바꿀 것입니다. 당신이 (자바의 다양한 버전에서) 자바의 기본 정렬 방법을 보면
, 당신은 LinkedList을 정렬하는 것은 수행되는 것을 볼 수 있습니다 :
큰 링크 된 목록을 정렬하는 데 가장 효율적인 방법입니다.
연결된 목록에 적용되는 mergesort 및 quicksort에 대한 요점은 부분적으로 만 적절합니다. 이중 연결리스트에서 병합과 퀵 소트는 효율적인 방법으로 구현 될 수 있습니다. 즉, 퀵 소트의 경우 피벗이 선택되는 방법에 따라 달라 지지만 'O (n log n)'의 정상 런타임을 달성하는 것은 불가능하지 않습니다. , resp. 'O (n^2)'최악의 경우. – Paul
어쩌면, 만약 당신이 정말로 그것에 영리했다면. 그러나 대규모 링크드 목록에 대한 빠른 정렬을 구현하는 것은 여전히 시도하기에는 미친 일입니다. 그는 배열 기반 목록을 사용하거나 분류 목록을 사용하여 정렬해야합니다 ... 단일 연결 목록에 대해 구현하기가 비교적 쉽습니다. –
지금까지 시도한 코드를 추가하십시오 – royB
그래서 ... 클래스 메소드를 사용하지 않고 노드를 목록에 삽입하려고합니까? 이것은 극단적으로 나쁜 코드 스타일이거나 단순히 달성 할 수없는 것입니다. – Paul
@ Paul, 'built-in methods'는 아마도 클래스 메소드와 같지 않을 것입니다. 나는 임무가 스스로 그것을하는 것이고, 내장 된 자바 구조를 사용하지 않을 것이라고 생각한다. –