0

考虑到中间元素的枢轴，我如何生成和打印快速排序的最坏情况集？这是我对快速排序算法的实现：

  void quickSort(int arr[], int left, int right) {

     int index = partition(arr, left, right);

        if (left < index - 1)

           quickSort(arr, left, index - 1);

        if (index < right)

           quickSort(arr, index, right);
 }


 int partition(int arr[], int left, int right){

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

   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--;

        }

  };
  return i;

 }

关于如何为该算法生成最坏情况的任何想法？

4

4 回答 4

5

将枢轴元素设置为等于最低或最高数字，应该得到最坏的情况。这种情况下的复杂度是O(n^2)。

于 2013-10-16T04:42:54.610 回答
2

快速排序算法的最坏情况发生在数组已经排序时。枢轴应该尽可能平均地拆分数组，其中枢轴左侧的元素小于枢轴，而其右侧的元素更大，即枢轴固定在排序数组中的最终位置，不再进一步交换发生在枢轴上。这使我们能够独立地处理枢轴左侧的数组和右侧的数组，并在其上递归地应用相同的算法。

最坏的情况发生在我们的主元元素尽可能不均等地拆分数组时，即在较小的一半中，我们得到的不是理想的 n/2 个元素，而是为零——这意味着主元是数组中最大或最小的。

因此，最坏的情况发生在输入数组已经排序时 - 如果选择枢轴作为第一个或最后一个元素。

当枢轴选择算法要选择中间元素时，基本上最坏的情况发生在选择枢轴以使一个分区为空时，即每次选择的枢轴都是最小/最大的。

于 2013-10-16T04:46:49.367 回答
1

quickshort 最坏的情况是每次你划分数组时它应该是一侧的。所以输入数组可以是一个排序数组。

于 2013-10-16T04:44:24.513 回答
0

快速排序的最坏情况是当您选择枢轴作为数组中的最低或最高元素，然后尝试围绕它进行分区时。如果您每次都选择数组中的最低或最高元素作为分区，您将进行接近 n 2 次比较/交换。为了避免这种最坏情况的行为，您可以使用中位数算法的中位数，即线性时间 (O(n)) 来为您选择合适的枢轴，这将使您的最坏情况为 O(n log n)。

于 2013-10-16T06:46:58.197 回答