partitioning - 快速排序帮助，不确定为什么分区返回索引而不是数组

Question

我想知道是否有人可以帮助我进行快速排序。我理解分区的一般思想，但不确定为什么它返回索引

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

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

我理解整个重新排列的部分。这对我来说很有意义，但我不确定为什么分区只返回一个索引。我以为它应该返回一个数组？就像问题是......排序{1, 12, 5, 26, 7, 14, 3, 7, 2}。我以为它会回来...

1, 2, 5, 7, 3, 14, 7, 26, 12

我想这就是为什么我不了解实际的快速排序功能。但如果有人可以帮助以易于理解的方式清楚地解释它，我们将不胜感激。多谢!

Answer 1

返回的索引仅用于标识 QuickSort 算法中的递归结束。它主要是用于标识更小和更大数字的枢轴元素的索引。

AND:您指的是增强型快速搜索算法。在 QuickSearch 算法的基本版本中，不需要返回的索引。

它也适用于:(但要慢得多)

void quickSort(int arr[], int left, int right) 
{
      if (left < right)
      {
         int index = partition(arr, left, right);
         quickSort(arr, left, index - 1);
         quickSort(arr, index+1, right);
      } 
}