c++ - 如何使快速排序算法中已排序数组的交换次数为零？

Question

有没有办法让已经排序的升序数组列表的交换次数为零。

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high- 1; j++)
    {
         // If current element is smaller than or
         // equal to pivot
         if (arr[j] <= pivot)
          {
           printf("inside if");
           i++;    // increment index of smaller element
           swap(&arr[i], &arr[j]);
           no_of_comparisons++;
          }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

Answer 1

如果您使用中间元素而不是列表中的最后一个元素(并稍微重新排列算法)，则可以避免交换。

为了获得最佳的 qsort，您最好使用第一个、最后一个和中间元素的中位数(称为“三的中位数”)。

如果您担心对攻击者生成的数据进行排序的性能(qsort 的平均性能为 O(n log n)，但最坏情况为 O(n²))，请使用随机枢轴。 p>

注意:我可以看到问题是关于 partition 而不是 qsort，但它很可能是在 qsort 的上下文中。