C++快速排序的几种实现方法+优化

左右挖坑互填左右交换三数取中优化完整代码 左右挖坑互填

//分割数组int partition(int a[], int l, int r){ int begin = l; int x = a[l]; while(l < r){ while(l < r && a[r] <= x) r--; a[l] = a[r]; while(l < r && a[l] >= x) l++; a[r] = a[l]; } a[l] = x; return l;}

//分割数组int partition(int a[], int l, int r){ int begin = l;//记录比较元素的下标 int x = a[l]; while(l < r){ while(l < r && a[r] <= x) r--;//从右至左找到第一个小于比较元素的数 while(l < r && a[l] >= x) l++;//从左至右找到第一个大于比较元素的数 if(l < r) swap(a[l], a[r]);//将大数与小数交换 } swap(a[begin], a[l]);//将比较元素交换到期望位置 return l;//返回比较元素的位置}

具体快排优化推荐这个博客：快速排序的4种优化

//三数取中（优化）int NumberOfThree(int a[], int l, int r){ int mid = (l + r) >> 1; if(a[mid] > a[r]) swap(a[mid], a[r]); if(a[l] > a[r]) swap(a[l], a[r]); if(a[mid] > a[l]) swap(a[l], a[mid]); return a[l];}

#include using namespace std;int NumberOfThree(int a[], int l, int r){ int mid = (l + r) >> 1; if(a[mid] > a[r]) swap(a[mid], a[r]); if(a[l] > a[r]) swap(a[l], a[r]); if(a[mid] > a[l]) swap(a[l], a[mid]); return a[l];}int partition(int a[], int l, int r){ int begin = l; int x = NumberOfThree(a, l, r); while(l < r){ while(l < r && a[r] <= x) r--; a[l] = a[r]; while(l < r && a[l] >= x) l++; a[r] = a[l]; } a[l] = x; return l;}void quickSort(int a[], int l, int r){if(l >= r) return;int idx = partition(a, l, r);quickSort(a, l, idx - 1), quickSort(a, idx + 1, r);}int main(){int n;cin >> n;int a[n];for(int i = 0; i < n; i++) cin >> a[i];quickSort(a, 0, n - 1);for(int i = 0; i < n; i++) cout << a[i] << ' ';return 0;}