快速排序进阶版（加入插入排序提高其性能）

如图所示，对于足够大的n，快速排序算法要比其他算法效率更高。令精确值为nbreak。当n<nbreak时，插入排序的平均性能最佳，而当n>nbreak时，快速排序的性能能最佳。

因此当n>nbreak时，我们可以把插入排序和快速排序综合为一个排序函数，可以提高快速排序的性能。 

在萨尼的《数据结构、算法与应用 c++语言描述》中：

把

if(l>=r) return;

 替换为

if (r - l <= nbreak) {
        insertion_sort(a, l, r);
        return;
}

原本的快速排序：

#include<bits/stdc++.h>
using namespace std;
void print_a(vector<int>& a){
    for(int i:a){
        cout<<i<<"";
    }
    cout<<endl;
} 
void quick_sort(vector<int> &a,int l,int r){
    if(l>=r) return;
    int i=l-1,j=r+1,x=a[(l+r)/2];
    while(i<j){
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
        cout<<"i="<<i<<" "<<"j="<<j<<" ";
        print_a(a);
    }
    quick_sort(a,l,j);
    quick_sort(a,j+1,r);

}

int main(){
    int n;
    cout<<"请输入n:"<<" ";
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    quick_sort(a,0,a.size()-1);
    print_a(a);
    return 0;
}

更新后的快速排序：

#include<bits/stdc++.h>
using namespace std;
void insertion_sort(vector<int>& a, int l, int r) {
    for (int i = l + 1; i <= r; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= l && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}
void print_a(vector<int>& a){
    for(int i:a){
        cout<<i<<"";
    }
    cout<<endl;
}
void quick_sort(vector<int> &a,int l,int r){
    if (r - l <= a.size()) {
        insertion_sort(a, l, r);
        return;
    }
    int i=l-1,j=r+1,x=a[(l+r)/2];
    while(i<j){
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
        cout<<"i="<<i<<" "<<"j="<<j<<" ";
        print_a(a);
    }
    quick_sort(a,l,j);
    quick_sort(a,j+1,r);

}

int main(){
    int n;
    cout<<"请输入n:"<<" ";
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    quick_sort(a,0,a.size()-1);
    print_a(a);
    return 0;
}

一般来说，当子数组的大小小于 10（这个值是可以根据具体情况调整的），使用插入排序会更有效率，因为插入排序对于小数组来说非常高效。在快速排序中加入一个小优化，当待排序的子数组的大小小于某个阈值时，使用插入排序来加速排序，这种方式称为“混合排序”。我们通过将小数组的排序任务交给插入排序来优化快速排序，这种方法可以减少递归深度，提高排序效率。