Knuth快速插入排序仅支持16元素数组的修复需求（保留代码结构）
我尝试复现Knuth著作中的快速插入排序算法，但当前代码仅能正确排序包含16个元素的数组，推测问题出在栈的参数传递环节。需在保留现有代码结构的前提下，修改代码使其可正确处理元素数量为100、500、1000、5000的数组。
当前快速排序实现代码
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); } } } }
栈实现代码
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; }
测试用例
原数组
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
问题分析与修复
核心问题
- 错误的
return语句：当子数组长度≤M时，调用插入排序后直接return，导致栈中剩余的待排序区间被完全忽略——这就是16元素数组能正常排序的原因：刚好一次处理完所有元素，不会触发后续栈操作。 - 分区后循环逻辑冲突：原代码试图在当前循环中直接处理较小分区，会覆盖
left/right变量，与栈的调度逻辑矛盾。 - 分区内层循环条件错误：
i - 1 < --j的判断容易导致边界越界，逻辑不严谨。
修改后的快速排序代码
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); // 子数组长度≤M时用插入排序，继续处理栈中剩余区间 if (right - left + 1 <= M && right - left + 1 > 1) { sortS(arr, left, right); continue; } int K = arr[left]; int i = left; int j = right + 1; // 修正分区循环条件，避免边界错误 while (true) { while (++i < j && arr[i] < K) {} while (--j > i && K < arr[j]) {} if (i < j) { swap(arr[i], arr[j]); } else { if (left != j) { arr[left] = arr[j]; arr[j] = K; } break; } } // 优化入栈顺序：先推大分区，再推小分区，减少栈深度 int left_size = j - left; int right_size = right - j; if (left_size > right_size && right_size > 0) { sortQ_push(&stack, left, j - 1); sortQ_push(&stack, j + 1, right); } else if (right_size > left_size && left_size > 0) { sortQ_push(&stack, j + 1, right); sortQ_push(&stack, left, j - 1); } else { // 仅推入非空分区 if (left_size > 0) sortQ_push(&stack, left, j - 1); if (right_size > 0) sortQ_push(&stack, j + 1, right); } } }
关键修改点
- 将
return替换为continue：处理完当前小分区后，继续循环处理栈中剩余的待排序区间。 - 修正分区内层循环条件：把
i - 1 < --j改为--j > i，避免边界越界问题。 - 优化分区入栈逻辑：仅推入非空分区，同时优先处理较小分区（通过先推大分区，栈顶即为小分区），减少栈深度，避免栈溢出。
内容的提问来源于stack exchange，提问作者smallshorty
