单向循环列表的快速排序[关闭]

问题描述 投票:0回答:0

我无法理解如何快速排序单链循环列表,我写了这段代码:

void quickSort(Node*& head, Node* start, Node* end) {
    Node* mid = start;
    for (int i = 0; i < getIndex(start,end)/2; i++)
    {
        mid = mid -> next;
    }
    Node* curLeft = start;
    Node* curRight = end;
    if ( start == end) return;
    if (getIndex(head, start) >= getIndex(head, end)) return;
    while (getIndex(head, curLeft) <= getIndex(head, curRight)) {
        
        while (curLeft->data < mid->data) {
            curLeft = curLeft->next;
        }
        while (curRight->data > mid->data) {
            Node* temp = curRight;
            do {
                temp = temp->next;
            } while (temp->next != curRight);
            curRight = temp;
        }
        if (getIndex(head, curLeft) <= getIndex(head, curRight)) {

            swapNodes(head, curLeft, curRight);
            curLeft = curLeft->next;
            Node* temp = curRight;
            do {
                temp = temp->next;
            } while (temp->next != curRight);
            curRight = temp;
        }
    }
    quickSort(head, start, curRight);
    quickSort(head, curLeft, end);
}

在该代码的情况下,我不能只交换值,我需要交换整个节点。

我不认为我的函数“getIndex”或“swapNodes”工作不正确,因为我在插入排序中使用它们并且它工作得很好

c++ linked-list quicksort
© www.soinside.com 2019 - 2024. All rights reserved.