我的快速排序有什么问题-只有两位数字的位置是错误的？

Question

我的快速排序代码在这里：

template<typename T>
void quick_sort_recursive(T arr[], int start, int end) {
   if (start >= end) return;
   T pivot = arr[start];
   int left = start + 1, right = end;

   while (left < right) {        
        while (arr[right] >= pivot && left < right) right--;
        while (arr[left] < pivot && left < right) left++;
        std::swap(arr[left], arr[right]);
    }

    if (arr[right] <  arr[start])
        std::swap(arr[left], arr[start]);
    else
        right--;

    quick_sort_recursive(arr, start + 1, right - 1);
    quick_sort_recursive(arr, right + 1, end);
}

template<typename T>
void quick_sort(T arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

---

测试数组是：

int a[17] = {3,5,1,5,1,6,7,32,43,2,54,632,24,353,5,5435,35};

但是，奇怪的事情发生了。我得到了一个输出：

1
1
2
3
5
5
5
6
24
7
32
35
43
54
353
632
5435

那么，为什么 7 和 24 总是错误的，而其他的是正确的？

Answer 1

你的递归调用

quick_sort_recursive(arr, start + 1, right - 1);
quick_sort_recursive(arr, right + 1, end);

从数组中省略两个元素。位置开始的元素和位置右边的元素。似乎您想将枢轴元素交换到两个段之间的中间，因此您应该从 start 而不是 start + 1.

开始第一次递归