如何在快速排序（quicksort）中实现medianOf3？求解决方案

我正尝试在快速排序算法中实现medianOf3方法，但所有尝试均未成功。已确认quicksort方法本身可正常运行，但partition方法无法完成正确分区。希望得到将medianOf3与quicksort结合实现的建议。已引入<bits/stdc++.h>头文件，并添加了using std::swap;和using namespace std;。

我的代码如下：

template<typename T> inline
int medianOf3(T A[], int l, int r){
        //this is overcommented... also, try and avoid using pointers
        T* a = A + l;//array name is just pointer to 1st (0 index) elem., + l shifts l*(T size)
        T* b = A + l + (r-l)/2;//middle item... int division rounds down
        T* c = A + r;

        //when a is a pointer, *a is the dereference operator (gives value a points to)
        T* m;
        if(*a < *b){
                if(*b < *c) m=b;
                else if(*c < *a) m=a;
                else m=c;
        } else{ //b <=a
                if(*a < *c) m=a;
                else if(*c < *b) m=b;
                else m=c;
        }
        return m-A; //m-A is the number of elements from A[0]

}
int partition(int a[], int l, int r){
    int s = medianOf3(a, l, r);
    swap(a[l], s);
    int p = a[l];
    int i = l; 
    int j = r;
    while(i<j){
        do{
            i=i+1;
        }while(a[i]<=p);
        do{
            j=j-1;
        }while(a[j]>p);
        if (i<j)
            swap(a[i], a[j]);
    }
    swap(a[l], a[j]);
    return j;
}
void quickSort(int arr[], int l, int r){
    if (l < r){
        int p = partition(arr, l, r);
        quickSort(arr, l, p - 1);
        quickSort(arr, p + 1, r);
    }
}

问题排查与修复方案 #

• 核心错误：partition函数的swap参数错误
  原代码中swap(a[l], s);是错误的，s是medianOf3返回的中位数索引，应该交换的是a[l]和a[s]，正确写法为：

  swap(a[l], a[s]);
  

  这个错误会导致基准值设置错误，直接引发分区失败。

• medianOf3函数的逻辑优化
  原函数的判断逻辑存在冗余，且注释有笔误（//b <=a8应为//b <=a）。可以改用更直观的写法，避免指针操作，直接通过索引访问元素：

  template<typename T> inline
  int medianOf3(T A[], int l, int r){
      int mid = l + (r - l) / 2;
      T val_l = A[l], val_mid = A[mid], val_r = A[r];
      
      // 找出三个值中的中位数对应的索引
      if ((val_l >= val_mid && val_l <= val_r) || (val_l <= val_mid && val_l >= val_r))
          return l;
      else if ((val_mid >= val_l && val_mid <= val_r) || (val_mid <= val_l && val_mid >= val_r))
          return mid;
      else
          return r;
  }
  

  这种写法更易读，也减少了指针操作带来的出错概率。

• partition函数的边界处理优化
  原循环中i初始为l，do-while直接i++，当数组长度较小时可能出现越界风险。可以调整初始值和循环条件，确保不会访问数组外的元素：

  int partition(int a[], int l, int r){
      int s = medianOf3(a, l, r);
      swap(a[l], a[s]);
      int p = a[l];
      int i = l + 1; 
      int j = r;
      while(true){
          while(i <= r && a[i] <= p) i++;
          while(j >= l && a[j] > p) j--;
          if(i >= j) break;
          swap(a[i], a[j]);
      }
      swap(a[l], a[j]);
      return j;
  }
  

  调整后避免了do-while可能带来的无条件递增/递减，同时增加了数组边界的判断，提升了稳定性。

内容的提问来源于stack exchange，提问作者o.ayden76