C 中的快速排序为什么要进行额外的交换？

Question

我正在尝试理解快速排序算法并用C语言实现它。我在programiz中找到了这段代码；

// Quick sort in C

#include <stdio.h>

void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}
int partition(int array[], int low, int high) {
  
  
  int pivot = array[high];
  int i = (low - 1);

  for (int j = low; j < high; j++) {
    if (array[j] <= pivot) {
      i++;
      swap(&array[i], &array[j]);
    }
  }

// please note Here!!!!!

  swap(&array[i + 1], &array[high]);
  return (i + 1);
}

void quickSort(int array[], int low, int high) {
  if (low < high) {
    
    
    int pi = partition(array, low, high);
    
    quickSort(array, low, pi - 1);
    
    quickSort(array, pi + 1, high);
  }
}
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}
int main() {
  int data[] = {8, 7, 2, 1, 0, 9, 6};
  int n = sizeof(data) / sizeof(data[0]);
  quickSort(data, 0, n - 1);
  printf("Sorted array in ascending order: \n");
  printArray(data, n);
}

此代码正在运行。但我不明白为什么他们在

<high

函数中迭代到

partition

并在另一步骤中进行最终交换。相反，他们为什么不这样做；

int partition(int array[], int low, int high) {
  int pivot = array[high];
  int i = (low - 1);

  for (int j = low; j <=  high; j++) {
    if (array[j] <= pivot) {
      i++;
      swap(&array[i], &array[j]);
    }
  }
 return (i);
}

我也检查了geeksforgeeks。他们也有相同的代码。这就是我问这个的原因。请帮助我

https://www.programiz.com/dsa/quick-sort

https://www.geeksforgeeks.org/quick-sort/amp/

Answer 1

为什么不一步迭代到高点？ 现在，让我们讨论您的替代代码，您建议迭代到 j <= high and performing the swap directly without the final swap step. Here’s the key issue with that approach:

枢轴的最终位置：快速排序的关键步骤是确保分区后枢轴最终位于正确的位置。当循环结束时， i 将指向小于或等于枢轴的最后一个元素。然而，枢轴本身仍然位于最后一个位置（array[high]）。

如果当 j == high 时将 array[i] 与 array[j] 交换，则将与小于或等于主元的最后一个元素交换主元。这将导致枢轴落在一个相对于其他元素可能无法正确排序的位置。这会破坏分区逻辑。 最终交换更正位置：通过执行最终交换 (swap(&array[i + 1], &array[high]))，您可以确保枢轴准确放置在所有较小元素位于左侧且所有较小元素都位于左侧的位置。较大的元素位于右侧。这保证了枢轴处于正确的排序位置，这对于递归调用继续工作至关重要。

总结一下： 为什么迭代到 j < high in the loop?

我们在 j 处停止循环 < high because the pivot is located at array[high], and we don’t want to compare the pivot to itself during the partitioning step. Why the final swap?

循环结束后，array[i]处的元素是最后一个小于或等于主元的元素。枢轴本身位于 array[high] 处。最后的交换确保枢轴被放置在正确的排序位置，即紧接在小于或等于它的最后一个元素之后。 如果您不进行最后的交换会发生什么？

主元最终不会到达正确的排序位置，这会导致递归排序步骤中出现不正确的行为，可能导致算法无法正确对数组进行排序。 使用您建议的方法编写代码（用于比较）： 如果您要遵循建议的方法，即迭代到 j <= high, the final swap becomes unnecessary, but the pivot wouldn't end up in its correct position, and you would likely end up with an unsorted array.