在 split 函数中使用 while 循环运行 QuickSort 时出现运行时错误

Question

我实现了我的快速排序算法，如下所示。 sortArray 函数是对数组进行排序的入口点。它初始化数组的下限和上限，然后调用快速排序函数。快速排序通过将数组分成更小的子数组并对每个子数组进行排序来递归地对数组进行排序。它调用 split 函数对数组进行分区。 split 函数返回必须进行分割的位置的索引。代码如下-

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        
        cout << "Running Code" << endl;
        int lower = 0;
        int upper = nums.size() - 1;
        

        quicksort(lower, upper, nums);
        return nums;
    }

    void quicksort(int lower, int upper, vector <int> &nums )
    {
        if(lower<upper)
        {
            int index = split(lower, upper, nums);
            cout << index << endl;
            quicksort(lower,index-1,nums);
            quicksort(index+1,upper,nums);
        }
        
    }

    int split(int lower, int upper, vector<int> &nums)
    {
        int base = nums[lower];
        int start = lower;
        int end = upper;

        printf("start: %d end: %d\n", start, end);
        
        while(start < end)
        {
                      
            while(nums[start] < base);
            start++;
          
            while(nums[end] > base);
            end--;

            if(start<end)
            swap(nums[start], nums[end]);

        }

        swap(nums[lower],nums[end]);

        return end;

       


    }
};

我想对数组进行递归排序，但出现运行时错误，如下所示 -

=================================================================
==22==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x5020000000a0 at pc 0x558a0c57ac59 bp 0x7ffcb3489590 sp 0x7ffcb3489588
READ of size 4 at 0x5020000000a0 thread T0
    #4 0x7fa09395ed8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: c289da5071a3399de893d2af81d6a30c62646e1e)
    #5 0x7fa09395ee3f  (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f) (BuildId: c289da5071a3399de893d2af81d6a30c62646e1e)
0x5020000000a0 is located 0 bytes after 16-byte region [0x502000000090,0x5020000000a0)
allocated by thread T0 here:
    #6 0x7fa09395ed8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: c289da5071a3399de893d2af81d6a30c62646e1e)
Shadow bytes around the buggy address:
  0x501ffffffe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501ffffffe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x502000000000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
=>0x502000000080: fa fa 00 00[fa]fa fa fa fa fa fa fa fa fa fa fa
  0x502000000100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000200: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000280: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000300: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==22==ABORTING

我花了很多时间尝试调试代码，但没有成功。任何帮助都感激不尽。谢谢。

Answer 1

有几个问题：

• while(nums[start] < base);

  是一个空循环体（注意分号），所以如果条件为真，循环将永远不会退出。您在下一个

  while

  循环中遇到同样的错误。

• 在分区实现中，您混合了 Lomuto 方案和 Hoare 方案 的概念。以下是两个方案之间的一些关键区别（

  split

  ）：

  财产	洛穆托	霍尔	您的代码的意图
  返回的索引总是枢轴的索引吗？	是的	不	是的
  原始枢轴索引是否被排除在循环之外？	是的	不	不
  循环是否有两个索引相互走向？	不	是的	是的

  如您所见，代码的意图（忽略错误）与这两种方案都不匹配。

由于 Hoare 的方案平均执行的交换次数要少得多，我建议您修复代码以与该方案保持一致：

• 由于 Hoare 的方案不一定返回主元的索引，并且主元值可以位于任一侧的任何位置，因此

  quicksort

  的第一次递归调用不应排除该索引。所以改成：

  quicksort(lower,index,nums);
  

• split

  中的最终交换不是霍尔计划的步骤，它也不会起作用：

  lower

  处的枢轴值可能已交换到不同的位置，因此在这种情况下会带来严重破坏。你应该忽略这个

  swap

  。

• 为了避免更复杂的代码，霍尔算法的实现实际上总是在每次循环迭代时至少递增

  start

  和递减

  end

  一次。因此，将内部

  while

  循环更改为

  do...while

  循环。

这是使用霍尔方案对快速排序代码的更正：

    void quicksort(int lower, int upper, vector <int> &nums )
    {
        if(lower<upper)
        {
            int index = split(lower, upper, nums);
            quicksort(lower,index,nums); // Hoare's scheme cannot exclude index
            quicksort(index+1,upper,nums); 
        }
    }

    int split(int lower, int upper, vector<int> &nums)
    {
        int base = nums[lower];
        int start = lower - 1;  // Start one off
        int end = upper + 1;    // (idem)

        while(start < end)
        {
            do { // Always increment at least once
                start++;
            }
            while(nums[start] < base); 
          
            do { // Always decrement at least once
                end--;
            }
            while(nums[end] > base);

            if(start<end)
                swap(nums[start], nums[end]);
        }
        // Hoare's scheme does not attempt to swap the pivot value to nums[end] 
        return end;
    }