我无法理解如何快速排序单链循环列表,我写了这段代码:
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”工作不正确,因为我在插入排序中使用它们并且它工作得很好