arrays - 带有导致段错误的指针的快速排序

Question

我正在尝试采用标准的快速排序算法，并通过采用分区函数对其进行稍微修改，使其不再采用整个数组、低索引和高索引，而是采用指向低索引的指针'th 元素以及我想要分区的元素数量。但是，我遇到了段错误，但我无法弄清楚。感谢您的帮助。

#include <stdio.h>

void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

int partition(int *array, int high) {
  int pivot = array[high];
  int i = 0;

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

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

void quickSort(int *array, int low, int high) {
  if (low < high) {
    int pi = partition(array + low, high - low);
    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]);
  
  printf("Unsorted Array\n");
  printArray(data, n);
  
  // perform quicksort on data
  quickSort(data, 0, n - 1);
  
  printf("Sorted array in ascending order: \n");
  printArray(data, n);
}

Answer 1

在您的代码中给出以下内容:

int pi = partition(array + low, high - low);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);

您使用指针调整基数 (array+low) 进行分区，并分段纯长度 (high-low)。如果这就是您的分区实现的工作方式(大多数情况都是如此)，那很好。但您需要记住生成的枢轴位置 pi 将基于该段中的位置； 不在整个数组中。您需要在递归时通过放回配置分区的原始偏移量来对此进行调整:

int pi = partition(array + low, high - low);
quickSort(array, low, low + pi - 1);   // <== LOOK
quickSort(array, low + pi + 1, high);  // <== HERE

仅此更改就可以让您的实现运行起来。还有其他方法可以做到这一点，当/如果我有时间的话，我会用其中的一些方法更新这个答案。