【模板】快速排序与归并排序——Template，QuickSort&MergeSort

秒速五厘米 2022-11-12 02:51 149阅读 0赞

快速排序

#include<iostream>
    using namespace std;
    int n,a[1000001];
    void qsort(int l,int r)//应用二分思想
    { 
        int mid=a[(l+r)/2];//中间数
        int i=l,j=r;
        do{ 
            while(a[i]<mid) i++;//查找左半部分比中间数大的数
            while(a[j]>mid) j--;//查找右半部分比中间数小的数
            if(i<=j)//如果有一组不满足排序条件（左小右大）的数
            { 
                swap(a[i],a[j]);//交换
                i++;
                j--;
            }
        }while(i<=j);//这里注意要有=
        if(l<j) qsort(l,j);//递归搜索左半部分
        if(i<r) qsort(i,r);//递归搜索右半部分
    }
    int main()
    { 
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        qsort(1,n);
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    }

归并排序

#include<iostream>
    using namespace std;
    const int N = 1e6 + 10;
    int q[N], tmp[N];
    
    void merge_sort(int q[], int l, int r) { 
        if(l >= r) {                               //如果数组中没有数，或者只有一个数，直接return
            return ;
        }
        int mid = (l + r) / 2;
        merge_sort(q, l, mid);                     //递归归并左右两部分
        merge_sort(q, mid + 1, r);
        int k = 0, i = l, j = mid + 1;             //k记录当前tmp数组中已经放好位置的是第几个数
        while(i <= mid && j <= r) { 
            if(q[i] <= q[j]) {                      //把较小的那个数放入tmp数组中
                tmp[k++] = q[i++];
            } else { 
                tmp[k++] = q[j++];
            }
        }
        while(i <= mid) {                          //如果某个指针走到了尽头，则把另一个数组剩下的部分全部加入到tmp数组中
            tmp[k++] = q[i++];
        }
        while(j <= r) { 
            tmp[k++] = q[j++];
        }
        for(int i = l, j = 0; i <= r; ++i, ++j) {             //再把tmp数组的数写回到q[l~r]
            q[i] = tmp[j];
        }
    }
    
    int main() { 
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) { 
            scanf("%d", &q[i]);
        }
        merge_sort(q, 0, n - 1);
        for(int i = 0; i < n; ++i) { 
            printf("%d ", q[i]);
        }
        return 0;
    }

测试板子题目：洛谷[P1177 【模板】快速排序][P1177]

归并排序是稳定的算法，快速排序是不稳定的算法。

归并排序的时间复杂度永远都是O(NlogN)，  
但快速排序的时间复杂度在最坏的情况下为O(n2)

综合考虑，使用归并排序更好，更实用！

[P1177]: https://www.luogu.com.cn/problem/P1177