快速排序帮助，不知道为什么分区返回索引而不是数组

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

返回的索引仅用于标识快速排序算法中递归的结束。它主要是主元元素的索引，用于识别较小和较大的数字。

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

Answer 2

您的分区函数正在就地修改数组。它返回的整数是值小于主元之前的索引，以及从值大于主元的位置开始的索引。这两个递归调用分别对较小的元素和较大的元素进行排序；递归调用之前测试的条件作为基本情况。