C++实现quick sort与merge sort无报错但排序结果不符合预期求助

错误点分析 #

快速排序错误 #

• pivot下标选择逻辑错误：你在main函数中计算的select是原始数组的全局固定下标，而快排递归处理的是动态变化的子数组区间，固定下标无法对应子数组的对应位置，甚至可能超出子数组边界，导致pivot取值完全错误。
• 分区逻辑错误：partition函数最后交换i+1和high位置的元素，但你并没有提前把pivot移动到high位置，最终放到分区点的不是pivot元素，分区功能完全失效。

归并排序错误 #

• merge函数的第一个while循环中，每次给arr[k]赋值后遗漏了k++操作，导致后续赋值会覆盖之前的元素，合并逻辑错误。

修正后的完整代码 #

#include <iostream>
using namespace std;

void swap(int *a, int *b);
void printarray(int array[], int size);
// select改为策略标记：0=取当前子区间首元素，1=中间，2=尾元素
int partition(int array[], int low, int high, int select);
void quicksort(int array[], int low, int high, int select);
void merge(int arr[], int p, int q, int r);
void mergesort(int arr[], int l, int r);

int main() {
    int n, arr[20], selection, num, select;
    cout << "Enter the total number of elements:" << endl;
    cin >> n;
    cout << "Enter the elements:" << endl;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    cout << "Which method would you like to choose?" << endl;
    cout << "1. Quick sort" << endl << "2. Merge Sort" << endl;
    cin >> num;
    switch (num) {
      case 1:
        cout << "Which element would you choose to be the pivot element?" << endl;
        cout << "1. First element" << endl << "2. Middle element" << endl << "3. Last element" << endl;
        cin >> selection;
        // 直接传策略标记，不再计算全局下标
        select = selection - 1;
        quicksort(arr, 0, n - 1, select);
        printarray(arr, n);
        break;
      case 2:
        mergesort(arr, 0, n - 1);
        printarray(arr, n);
        break;
      default:
        cout << "invalid input" << endl;
        break;
    }
}

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

void printarray(int array[], int size) {
    int i;
    for (i = 0; i < size; i++)
        cout << array[i] << " ";
    cout << endl;
}

int partition(int array[], int low, int high, int select) {
    int pivot_idx;
    // 根据当前子数组的边界和策略计算pivot下标
    if(select == 0) pivot_idx = low;
    else if(select == 1) pivot_idx = low + (high - low)/2;
    else pivot_idx = high;
    int pivot = array[pivot_idx];
    // 把pivot先交换到high位置，保证最后交换的是pivot
    swap(&array[pivot_idx], &array[high]);
    
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (array[j] <= pivot) {
            i++;
            swap(&array[i], &array[j]);
        }
    }
    swap(&array[i + 1], &array[high]);
    return (i + 1);
}

void quicksort(int array[], int low, int high, int select) {
    if (low < high) {
        int pi = partition(array, low, high, select);
        quicksort(array, low, pi - 1, select);
        quicksort(array, pi + 1, high, select);
    }
}

void merge(int arr[], int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    
    int L[n1], M[n2];
    
    for (int i = 0; i < n1; i++)
        L[i] = arr[p + i];
    for (int j = 0; j < n2; j++)
        M[j] = arr[q + 1 + j];
    
    int i = 0, j = 0, k = p;
    
    while (i < n1 && j < n2) {
        if (L[i] <= M[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = M[j];
            j++;
        }
        // 补全k自增操作
        k++;
    }
    
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2) {
        arr[k] = M[j];
        j++;
        k++;
    }
}

void mergesort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergesort(arr, l, m);
        mergesort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

测试验证 #

使用你给出的测试输入运行修正后代码，选择快速排序、首元素作为pivot，可得到正确输出：

10 11 12 13 14 15

内容的提问来源于stack exchange，提问作者Yash Malhotra