Сортировка односвязного списка с++

256

03 июня 2018, 14:10

Вот мой код:

struct branch{
    long order=0;
    branch * next = NULL;
};
branch * head = NULL;
void SuperSort(){
if(head){
    branch * miss = new branch;
    miss->next = head;
    while(miss->next->next){
        branch * worry = new branch;
        worry->next = miss->next;
        branch * pass = new branch;
        pass = miss->next->next;
        while(pass){
            if(worry->next->order<pass->order)
                worry->next = pass;
            branch * buf = new branch;
            buf->next = miss->next;
            if(miss->next==head){
                head->next = worry->next->next;
                worry->next = head;
                head = worry->next;
                worry->next->next = buf->next;
            } else {
                miss->next->next = worry->next->next;
                miss->next = worry->next;
                worry->next->next = buf->next->next;
                worry->next = buf->next;
            }
            pass = pass->next;
        }
        miss->next = miss->next->next;
    }
}
}

А так лучше?

Answer 1

Не знаю как но получилось. Главное что работает)))

branch* sort_list(branch* hea){
    branch *top = nullptr;
    branch *current = nullptr;
    bool sorted = false;
    while (sorted == false) {
        branch *parent = hea;
        branch *lowparent = hea;
        branch *low = hea;
        sorted = true;
        do {
            branch* next = parent->next;
            if (parent->order < next->order) {
                lowparent = parent;
                low = next;
                sorted = false;
                }
            parent = parent->next;
            } while (parent->next != nullptr);
        if (current != nullptr){
            current->next = low;
            }
        current = low;
        if(current == hea){hea = current->next;}
        lowparent->next = low->next;
        current->next = nullptr;
        if(top == nullptr){
            top = current;
            }
        };
    current->next = hea;
    return top;
}
void Sort(){
    for(int i=0;i<Length;i++)
        head = sort_list(head);
}