插入快速排序

问题描述 投票：0回答：1

我需要重复 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章 第741章 第254章 第651章 163 第441章 第231章 509 第302章 127 924 第887章 第822章 第471章 第856章 第873章 234 第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 11 8 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 818 785 795 830 763 7 42 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++ algorithm sorting quicksort
1个回答
0
投票

您的代码中存在一些问题：

  • 调用 

    sortS
    后不应返回，因为堆栈上可能有更多范围需要排序。

  • 当您通过从堆栈中弹出来开始每次迭代时，通过设置 

    left
    或 
    right
    来结束循环迭代是没有意义的（就像您在 
    if... else if
    块中所做的那样）。这些值会立即被从堆栈中弹出的内容覆盖。但是，看看您如何决定将最大的分区放在堆栈上，并希望继续使用剩余的分区（尽可能避免使用堆栈），我认为您希望避免堆叠两个分区只是为了弹出其中一个分区立即他们。这可以被视为堆栈空间的浪费。但如果是这种情况，您实际上应该不在循环开始时从堆栈中弹出分区，而只有在处理了无法再拆分的分区时才这样做。例如，当您调用 
    sortS
    时就是这种情况：此时当前分区已完全排序并且不需要更多细分。这是从堆栈中弹出下一个分区的时刻。

  • 我不明白为什么在循环结束时对两个分区大小相等的情况进行特殊处理。鉴于上述观点，您永远不必将 two 分区推送到堆栈上（尽管如果您以 pop 开始迭代，则可以这样做，但您必须决定采用哪种方式走）。

不是问题，但是：

  • 如果您确保插入排序

    if (right - left + 1 <= M && right - left + 1 > 1)
    能够很好地处理违反第二个条件的
    sortS
    /
    left
    参数，则可以删除条件
    right
    的第二部分。

  • 至于测试您的快速排序代码，我建议减少输入的大小，并将 

    M
    设置为 2：插入排序部分不应在此类测试中发挥重要作用。

这是您的代码的更正：

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;
        }
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.