是否有真正的C++快速排序算法？

Question

编辑:OP的混乱是由于假设枢轴有固定位置.它实际上取决于<=到它的元素数量.如果其中一个示例选择7作为枢轴元素,最终将其交换到更高的索引,并且使用7来自枢轴开始位置的不同元素的第一遍完成,则没有帮助.

自从我在CS中学习快速排序然后开始将其应用于代码之后,我就一直在努力解决代码执行真正快速排序算法的概念.快速排序的想法很简单:选择原始数组的一个数据透视表,并从数组中的所有其他数字排序到该数据透视图的左侧或右侧.然后,通过递归调用,通过相同的方法对每个子数组(枢轴和枢轴右侧的项)进行排序,直到对整个数组进行排序.

在实践中,我遇到的每种语言似乎都有相同的公认代码来实现这一目标.它看起来像这样(来自http://www.algolist.net/Algorithms/Sorting/Quicksort):

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

但是,正如您从网站自己的视觉中看到的那样,当第一个分区停止时,"3"仍位于所选"7"枢轴的右侧.在测试其他阵列时我也观察到了这一点.对于[6,5,1,3,8,4,7,2,2],第一个轴是8.在第一个分区之后,8一直到9的右边,直到最后一个递归调用.有没有人注意过这个？

Answer 1

但是,正如您从网站自己的视觉中看到的那样,当第一个分区停止时,"3"仍位于所选"7"枢轴的右侧

分区移动所有这些,left <= 7 <= right算法提供了这样做:

1 2 5 7 3 | 14 7 26 12

所选的pivot不是数组元素 7,而是值 7.

将pivot视为值,而不是数组的元素.这就是理论所说的,你所链接的网站也是这样说的:

选择一个透视值.我们将中间元素的值作为透视值,但它可以是任何值,即在数组中不存在的情况下,它在排序值的范围内.

选择元素的值只是一种方便.如果你替换"|" 以上7,算法符合理论.

快速排序可以还可以实现为left | pivot | right,例如见第一伪维基百科.它不具有是,虽然,left <= pivot | pivot | right >= pivot是的一个子集left <= pivot | right >= pivot.所以如果你先做第一个,你实际上也是第二个.