如何避免快速排序堆栈流

Question

当我在C++中使用快速排序时，visual studio 2013警告堆栈溢出错误。

我该如何解决这个问题？在这个问题中，我不能使用这种快速排序吗？

我认为，因为我在快速排序中使用递归，所以这个问题使许多深层存储器堆栈。

这里是代码。

int partition(int **array, int p, int r){ 

    int x = array[r][1]; 
    int i = p - 1; 
    int j; 
    int temp0, temp1; 

    for (j = p; j < r; j++){ 
     if (array[j][1] <= x){ 
      i++; 

      temp0 = array[i][0]; 
      temp1 = array[i][1]; 

      array[i][0] = array[j][0]; 
      array[i][1] = array[j][1]; 

      array[j][0] = temp0; 
      array[j][1] = temp1; 
     } 
    } 

    temp0 = array[i + 1][0]; 
    temp1 = array[i + 1][1]; 

    array[i + 1][0] = array[r][0]; 
    array[i + 1][1] = array[r][1]; 

    array[r][0] = temp0; 
    array[r][1] = temp1; 

    return i + 1; 
} 

void quickSort(int **array, int p, int r){ 
    int q; 
    if (p < r){ 
     q = Partition(array, p, r); 
     quickSort(array, p, q - 1); 
     quickSort(array, q + 1, r); 
    } 
} 

Answer 1

在你的代码中，你总是先做前半部分（array，p，q - 1）。这可能会导致堆栈溢出。相反，总是先做两个子阵列中最小的一个，然后强制尾递归。

void quickSort(int **array, int p, int r){ 
    while (r - p >= 1){ 
     int q = Partition(array, p, r); 

     if ((q - 1) - p <= r - (q + 1)){ 
      quicksort(array, p, q - 1); 

      // Prepare for tail recursion 
      p = q + 1; 
     } 
     else { 
      quicksort(array, q + 1, r); 

      // Prepare for tail recursion 
      r = q - 1; 
     } 
    } 
} 

这样做，可以证明堆栈上的递归调用的最大数目是log_ {2}（n）。