通过插入快速排序-解网

问：

我需要重复 Knuth 书中的快速插入排序，但它只对一个包含 16 个元素的数组进行排序。我猜问题是由于堆栈上的参数传递造成的。我需要代码结构保持这样

void quickSort(vector<int>& arr) {
    int left, right;
    int M = 16;

    SortQ_stack* stack = nullptr;
    sortQ_push(&stack, 0, arr.size() - 1);

    while (stack != nullptr) {

        sortQ_pop(&stack, left, right);

        if (right - left + 1 <= M && right - left + 1 > 1) {
            //Q9 сортировка простыми вставками
            sortS(arr, left, right);
            return;
        }

        int K = arr[left];
        int i = left;
        int j = right + 1;



        while (true) {
            while (++i < j && arr[i] < K) {}
            while (i - 1 < --j && K < arr[j]) {}
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            else
            {
                if (left != j)
                {
                    arr[left] = arr[j];
                    arr[j] = K;
                }
                break;
            }
        }

        if (right - j > j - left) {
            sortQ_push(&stack, j + 1, right);
            right = j - 1;
        }
        else if (j - left > right - j) {
            sortQ_push(&stack, left, j - 1);
            left = j + 1;
        }
        else {
            if (left < right) {
                sortQ_push(&stack, j + 1, right);
                sortQ_push(&stack, left, j - 1);
            }
        }
    }
}

例如原始数组： 384 356 316 535 438 148 613 973 563 486 467 235 627 668 652 470 196 884 337 659 703 422 287 580 446 860 895 515 685 795 546 969 151 763 505 489 811 118 462 375 505 830 510 132 498 163 503 595 947 54秒 254 651 163 441 231 509 302 127 924 887 822 471 856 873 13瓦 362 363 946 380 726 321 785 556 732 818 955 795 321 550 742 962 704 394 126 146 526 535 348 553 460 236 375 831 993 249 966 355 513 912 635

数组排序不正确：

151 356 316 355 249 148 375 236 348 146 126 235 321 321 380 363 196 362 337 234 127 302 287 231 163 254 163 132 375 118 384 446 438 460 505 489 486 467 462 394 505 470 510 471 498 422 503 509 441 513 515 526 535 535 553 550 546 556 563 580 595 613 627 635 651 652 659 668 685 703 704 726 732 741 818785 795 830 763 742 856 822 831 795 811 860 962 955 946 884 873 887 924 912 895 966 947 969 993 973

我需要它在 100、500、1000、5000 个阵列上正常工作

我的堆栈实现

struct SortQ_stack {
    int left;
    int right;
    SortQ_stack* next;
};

void sortQ_push(SortQ_stack** top, int l, int r) {
    SortQ_stack* new_node = new SortQ_stack();
    new_node->left = l;
    new_node->right = r;
    new_node->next = *top;
    *top = new_node;
}

void sortQ_pop(SortQ_stack** top, int& l, int& r) {
    if (*top == nullptr) {
        l = -1;
        r = -1;
        return;
    }
    l = (*top)->left;
    r = (*top)->right;
    SortQ_stack* temp = *top;
    *top = (*top)->next;
    delete temp;
}

C++ 算法快速排序

@smallshorty我需要它来相应地处理 100、500、1000、5000 个数组——您也需要它来处理 20 和 30 的数组。我建议你从较小的数量开始，比如 20 个项目。它的排序不能处理 20 个元素，它不适用于 100 个或更高的元素。此外，较少的元素数量将使代码更易于调试。

答：

0赞 trincot 11/18/2023 #1

代码中存在一些问题：

调用后不应返回，因为堆栈上可能有更多范围需要排序。sortS
当您以堆栈中的弹出声开始每次迭代时，通过设置 or 来结束循环的迭代是没有意义的（就像您在块中所做的那样）。这些值会立即被您从堆栈中弹出的内容覆盖。但是，看看您如何决定将最大的分区放在堆栈上，并希望继续使用剩余的分区（尽可能避免使用堆栈），我认为您希望避免堆叠两个分区只是为了立即弹出其中一个。这可能被视为对堆栈空间的浪费。但是，如果是这种情况，您实际上不应该在循环开始时从堆栈中弹出分区，而只有在处理了无法再拆分的分区时才这样做。例如，当您调用：时，当前分区已完全排序，不需要更多的细分。这是从堆栈中弹出下一个分区的时刻。leftrightif... else ifsortS
我不明白为什么在循环结束时，您对两个分区大小相等的情况进行了特殊处理。鉴于上述观点，您永远不必在堆栈上推送两个分区（尽管如果您以 pop 开始迭代，这将是这样做的方法，但您必须决定走哪条路）。

没问题，但是：

如果您确保插入排序能够很好地处理违反第二个条件的 / 参数，则可以删除条件的第二部分。if (right - left + 1 <= M && right - left + 1 > 1)sortSleftright
至于测试您的快速排序代码，我建议减小输入的大小，并设置为 2：插入排序部分不应在此类测试中扮演重要角色。M

以下是代码的更正：

void quickSort(vector<int>& arr) {
    int left = 0, right = arr.size() - 1; // Don't use stack yet
    // Set M to a low value until you are certain quickSort works perfectly
    int M = 2;  
    
    // Start with an empty stack to save stack space
    SortQ_stack* stack = nullptr; 
    // As a consequence the loop condition involves left/right
    while (right > left || stack) { 
        if (right <= left) { // Only pop when nothing to sort in current range
            sortQ_pop(&stack, left, right);
        }
 
        if (right - left + 1 <= M) {  // Simplified condition
            //Q9 Sorting with simple inserts
            sortS(arr, left, right);
            left = right; // Trigger a pop in next iteration
            continue; // Don't return!!
        }

        int K = arr[left];
        int i = left;
        int j = right + 1;
        while (true) {
            while (++i < j && arr[i] < K) {}
            while (i - 1 < --j && K < arr[j]) {}
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            else
            {
                if (left != j)
                {
                    arr[left] = arr[j];
                    arr[j] = K;
                }
                break;
            }
        }
       if (right - j > j - left) {
            if (right > j + 1) { // Only push windows larger than 1
                sortQ_push(&stack, j + 1, right);
            }
            right = j - 1;
        }
        else { // There should be no other cases besides this one
            if (j - 1 > left) { // Only push windows larger than 1
                sortQ_push(&stack, left, j - 1);
            }
            left = j + 1;
        }
    }
}

上一个：如何遍历 std：：vector 的范围

下一个：T 不是非类型模板参数的有效类型

通过插入快速排序

Quick sort with Insertion

评论