[algorithm] 연결 목록을 정렬하는 가장 빠른 알고리즘은 무엇입니까?

병합 정렬에는 O (1) 액세스가 필요하지 않으며 O (n ln n)입니다. 일반 데이터를 정렬하는 알려진 알고리즘이 O (n ln n)보다 낫습니다.

기수 정렬 (데이터 크기 제한) 또는 히스토그램 정렬 (개별 데이터 계산)과 같은 특수 데이터 알고리즘은 O (1) 액세스가있는 다른 구조를 임시 저장소로 사용하는 한 낮은 성장 함수로 연결된 목록을 정렬 할 수 있습니다. .

특수 데이터의 또 다른 클래스는 k 요소가 순서가 맞지 않는 거의 정렬 된 목록의 비교입니다. 이것은 O (kn) 연산으로 정렬 할 수 있습니다.

목록을 배열에 복사하고 다시 복사하는 것은 O (N)이므로 공간이 문제가되지 않는 경우 모든 정렬 알고리즘을 사용할 수 있습니다.

예를 들어를 포함하는 연결 목록이 주어지면 uint_8이 코드는 히스토그램 정렬을 사용하여 O (N) 시간으로 정렬합니다.

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>

typedef struct _list list_t;
struct _list {
    uint8_t value;
    list_t  *next;
};


list_t* sort_list ( list_t* list )
{
    list_t* heads[257] = {0};
    list_t* tails[257] = {0};

    // O(N) loop
    for ( list_t* it = list; it != 0; it = it -> next ) {
        list_t* next = it -> next;

        if ( heads[ it -> value ] == 0 ) {
            heads[ it -> value ] = it;
        } else {
            tails[ it -> value ] -> next = it;
        }

        tails[ it -> value ] = it;
    }

    list_t* result = 0;

    // constant time loop
    for ( size_t i = 255; i-- > 0; ) {
        if ( tails[i] ) {
            tails[i] -> next = result;
            result = heads[i];
        }
    }

    return result;
}

list_t* make_list ( char* string )
{
    list_t head;

    for ( list_t* it = &head; *string; it = it -> next, ++string ) {
        it -> next = malloc ( sizeof ( list_t ) );
        it -> next -> value = ( uint8_t ) * string;
        it -> next -> next = 0;
    }

    return head.next;
}

void free_list ( list_t* list )
{
    for ( list_t* it = list; it != 0; ) {
        list_t* next = it -> next;
        free ( it );
        it = next;
    }
}

void print_list ( list_t* list )
{
    printf ( "[ " );

    if ( list ) {
        printf ( "%c", list -> value );

        for ( list_t* it = list -> next; it != 0; it = it -> next )
            printf ( ", %c", it -> value );
    }

    printf ( " ]\n" );
}


int main ( int nargs, char** args )
{
    list_t* list = make_list ( nargs > 1 ? args[1] : "wibble" );


    print_list ( list );

    list_t* sorted = sort_list ( list );


    print_list ( sorted );

    free_list ( list );
}