快捷導(dǎo)航

C++STL函數(shù)和排序算法的快排以及歸并排序詳解

更新時(shí)間：2022年03月02日 15:25:56 作者：披星戴月的賈維斯

這篇文章主要為大家詳細(xì)介紹了C++STL函數(shù)和排序算法的快排以及歸并排序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助

一、隊(duì)列是什么？

頭文件queue主要包括循環(huán)隊(duì)列queue和優(yōu)先隊(duì)列priority_queue兩個(gè)容器。

像棧一樣，隊(duì)列（queue）也是一種線性表，它的特性是先進(jìn)先出，插入在一端，刪除在另一端。就像排隊(duì)一樣，剛來(lái)的人入隊(duì)（push）要排在隊(duì)尾(rear)，每次出隊(duì)(pop)的都是隊(duì)首(front)的人。

就像管道一樣先進(jìn)先出。

隊(duì)列的相關(guān)概念：

1.隊(duì)頭與隊(duì)尾：允許元素插入的一端稱為隊(duì)尾，允許元素刪除的一端稱為隊(duì)頭。

2.入隊(duì)：隊(duì)列的插入操作。

3.出隊(duì)：隊(duì)列的刪除操作。

隊(duì)列的聲明：

#include<iostream>
#include<queue>//隊(duì)列的頭文件
using namespace std;
int main ()
{
    queue<int> a;//隊(duì)列的聲明
    priority_queue<int> q;  //大根堆
    priority_queue<int, vector<int>, greater<int>> q;   // 小根堆
    struct Rec//結(jié)構(gòu)體rec中大根堆要定義小于號(hào)，小根堆要定義大于號(hào)
    {
        int x,y;
        bool operator >(const Rec &t) const
        {
            return x > t.x;
        }
    };
    queue<Rec> q;
    return 0;
}

（1）循環(huán)隊(duì)列 queue

push // 從隊(duì)尾插入
pop // 從隊(duì)頭彈出
front // 返回隊(duì)頭元素
back // 返回隊(duì)尾元素

（2）優(yōu)先隊(duì)列 priority_queue

push // 把元素插入堆
pop // 刪除堆頂元素
top // 查詢堆頂元素（最大值）

#include<iostream>
#include<queue>//隊(duì)列的頭文件
using namespace std;
int main ()
{
    queue<int> a;//隊(duì)列的聲明
    a.push(1);//在隊(duì)頭插入一個(gè)新元素；
    a.pop();//彈出隊(duì)尾元素
    a.front();//返回隊(duì)頭
    a.back();//返回隊(duì)尾
    //優(yōu)先隊(duì)列中
    a.top();//取最大值
    a.pop();//去最大值
    //注意：隊(duì)列沒(méi)有clear 函數(shù)
    q = queue<int>();//重新初始化一個(gè)隊(duì)列，起到清除隊(duì)列的效果。
    return 0;
}

二、排序算法

1.快速排序

主要思想：分治

解題步驟：

1、確定分界點(diǎn)，如果數(shù)據(jù)量比較大，到一百萬(wàn)之類的，建議分界點(diǎn)取中間。

2、調(diào)整區(qū)間，分為>=x,和<=x兩個(gè)部分。

3、遞歸處理左右兩段。

##include<iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N];
int n;
void quick_sort(int q[], int l, int r)
{
    if( l >= r) return;//判斷數(shù)組是否只有1位數(shù)或?yàn)榭?
    int x = q[l + r >> 1], i = l - 1, j = r + 1;//設(shè)置分界點(diǎn)以及i,j兩個(gè)“指針”；
    while( i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) //特判如果i,j兩指針都不滿足i<=x,j>=x這個(gè)條件時(shí)，交換兩個(gè)值
        {
            int t= q[i];
            q[i] = q[j];
            q[j] =t;
        }
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);//遞歸處理左右兩段
}
int main ()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for(int i = 0; i < n; i++) printf("%d ",q[i]);
    return 0;
}

快速排序例題：第k個(gè)數(shù)

#include<iostream>
using namespace std;
int n , k;
const int N = 100010;
int q[N];
int quick_sort(int l, int r,int k)
{
    if(l == r) return q[l];//特判如果只有一個(gè)數(shù)，返回這個(gè)數(shù)
    int x = q[l + r >> 1], i = l - 1, j = r + 1;// 
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    int sl = j - l + 1;
    if(k <= sl) return quick_sort(l, j , k);//遞歸左邊
    return quick_sort(j + 1, r, k - sl);//遞歸右邊
}
int main ()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    cout << quick_sort(0, n - 1, k) << endl;
    return 0;
}

2、歸并排序

主要思想：分治

1、確定分界點(diǎn)mid = （l+r）/2。

2、遞歸排序左右兩邊left，right。

3、歸并、合二為一（難點(diǎn)）。

??#include<iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r)
{
    if(l >= r) return;// 特判區(qū)間內(nèi)如果只有一個(gè)數(shù)或者為空時(shí)，直接return;
    int mid = l + r >> 1;//確定分界點(diǎn)mid
    merge_sort(q, l, mid), merge_sort(q, mid+1, r);//遞歸排序兩邊
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)//歸并，合并兩邊
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
        while(i <= mid) tmp[k++] = q[i++];//再次查看左邊區(qū)間是否還有剩余
        while(j <= r) tmp[k++] = q[j++];//再次查看右邊區(qū)間是否還有剩余
        for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];//把tmp[i] 存到q[j]里
}
int main ()
{
    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;
}