c++ 快速排序与插入

ftf50wuq 于 8个月前发布在其他

关注(0)|答案(1)|浏览(44)

我需要重复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 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 818 785 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++

来源：https://stackoverflow.com/questions/77503309/quick-sort-with-insertion

1条答案

按热度按时间

tquggr8v1#

你的代码中有几个问题：

在调用sortS之后不应该返回，因为可能有更多的范围需要在堆栈上排序。
由于每次迭代都是从堆栈中弹出，因此通过设置left或right来结束循环的迭代没有意义（就像你在if... else if块中所做的那样）。这些值会立即被你从堆栈中弹出的内容覆盖。然而，看看你是如何决定把最大的分区放在堆栈上的，并希望继续使用剩余的分区（避免尽可能多地使用堆栈），我认为你想避免堆叠两个分区只立即弹出其中一个。这可能被视为浪费堆栈空间。但如果是这样的话，实际上，你不应该在循环开始时从堆栈中弹出一个分区，而只是在处理一个不能再分割的分区时才这样做。例如，当你调用sortS时：此时，当前分区已完全排序，不再需要再细分。此时，从堆栈中弹出下一个分区。
我不明白为什么在循环结束时，你会对两个分区大小相等的情况进行特殊处理。根据上面的观点，你永远不应该在堆栈上压入 * 两个 * 分区（尽管如果你以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;
        }
    }
}

字符串

赞(0）回复(0）举报 8个月前

我来回答

c++ 快速排序与插入

1条答案

相关问题

热门标签

最新问答