快速排序分段错误

Question

我用 C 实现了快速排序算法，并且在元素少于 30000 个的向量中正常工作。但是，它出现了分段错误 排队

if (vet[sup]>vet[sup/2+1]){swap(&vet[sup], &vet[sup/2+1]);}

具有更大的向量。 这是完整的算法：

void swap(int* a, int* b){
    *a=*a^*b;
    *b=*a^*b;
    *a=*a^*b;
}
int partition(int inf, int sup, int vet[]){
    while (inf<sup){
        while (vet[inf]<=vet[sup] && inf<sup){inf++;}
        while (vet[inf]<=vet[sup] && inf<sup){sup--;}
        if (inf<sup){swap(&vet[inf], &vet[sup]);}
    }
    return inf;
}
void median (int inf, int sup, int vet[]){ //select the median of the first, last and midle value of the vector
    if (vet[inf]>vet[sup/2+1]){swap(&vet[inf], &vet[sup/2+1]);}
    if (vet[sup]>vet[sup/2+1]){swap(&vet[sup], &vet[sup/2+1]);}  
    else if (vet[sup]<vet[inf]){swap(&vet[sup], &vet[inf]);}    
}
void quicksort(int inf, int sup, int vet[]){
    if (inf<sup){
        median(inf, sup, vet);    
        int piv=partition(inf, sup, vet);
        quicksort(inf, piv-1, vet);
        quicksort(piv+1, sup, vet);
    }
}

我尝试编写快速排序，其中尽可能少地声明变量，但它仍然出现分段错误。我不知道这是堆栈溢出还是指针问题，只有较大的向量才会发生。

抱歉我的英语不好，我还在学习

Answer 1

您的代码中存在多个问题：

• 您的编码风格很难阅读和调试：例如，将测试和交换代码塞在同一行上使得无法判断哪个部分导致崩溃。每行写入一条语句，并在多行上中断控制语句。

• 交换代码异或技巧已经过时：它是神秘的，可能未定义且效率低下，甚至更糟糕：如果

  a

  和

  b

  指向同一位置，它不起作用。使用更简单的代码：

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

• 这是可能的，尽管提供给代码的数据集不太可能被精心设计以导致堆栈溢出。 您可能想学习 Doug McIlroy 的经典文章：QuickSort 的杀手对手，它解释了如何构建这样的向量。 防止潜在堆栈溢出但不会降低二次时间复杂度的简单对策很容易实现：仅在较小的一半上递归并在较大的一半上循环。

• 更可能的崩溃原因是你没有用sup/2+1选择切片中的

  middle

  元素，你应该写

  (inf + (sup - inf + 1) / 2

  ，因此没有正确选择枢轴，因此算法可能会递归太多随机向量的时间事件。

这是修改后的版本：

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

int partition(int inf, int sup, int vet[]) {
    while (inf < sup) {
        while (vet[inf] <= vet[sup] && inf < sup) {
            inf++;
        }
        while (vet[inf] <= vet[sup] && inf < sup) {
            sup--;
        }
        if (inf < sup) {
            swap(&vet[inf], &vet[sup]);
        }
    }
    return inf;
}

// Select the median of the first, last and middle value of the vector
// and move it to vet[sup]
void median(int inf, int sup, int vet[]) {
    int m = inf + (sup - inf + 1) / 2;
    // set vet[m] = min(vet[inf], vet[m])
    if (vet[inf] > vet[m]) {
        swap(&vet[inf], &vet[m]);
    }
    if (vet[sup] > vet[m]) {
        // set vet[sup] = min(vet[sup], min(vet[inf], vet[m]))
        swap(&vet[sup], &vet[m]);
    } else
    if (vet[sup] < vet[inf]) {
        // set vet[sup] = min(vet[sup], max(vet[inf], vet[m]))
        swap(&vet[sup], &vet[inf]);
    }    
}

void quicksort(int inf, int sup, int vet[]) {
    while (inf < sup) {
        median(inf, sup, vet);    
        int piv = partition(inf, sup, vet);
        // recurse on the smaller half, loop on the other half
        if (piv - inf < sup - piv) {
            quicksort(inf, piv - 1, vet);
            inf = piv + 1;
        } else {
            quicksort(piv + 1, sup, vet);
            sup = piv;
        }
    }
}