(C/C++)STL函数和排序算法:快排以及归并排序

简介: (C/C++)STL函数和排序算法:快排以及归并排序

一、队列是什么?


头文件queue主要包括循环队列queue和优先队列priority_queue两个容器。


像栈一样,队列(queue)也是一种线性表,它的特性是先进先出,插入在一端,删除在另一端。就像排队一样,刚来的人入队(push)要排在队尾(rear),每次出队(pop)的都是队首(front)的人。


就像管道一样先进先出。


队列的相关概念:


队头与队尾: 允许元素插入的一端称为队尾,允许元素删除的一端称为队头。

入队:队列的插入操作。

出队:队列的删除操作。

队列的声明:                                                                                                                        

#include<iostream>
#include<queue>//队列的头文件
using namespace std;
int main ()
{
    queue<int> a;//队列的声明
    priority_queue<int> q;  //大根堆
    priority_queue<int, vector<int>, greater<int>> q;   // 小根堆
    struct Rec//结构体rec中大根堆要定义小于号,小根堆要定义大于号
    {
        int x,y;
        bool operator >(const Rec &t) const
        {
            return x > t.x;
        }
    };
    queue<Rec> q;
    return 0;
}

1669436816749.jpg

(1)循环队列 queue

push    // 从队尾插入
pop     // 从队头弹出
front   // 返回队头元素
back    // 返回队尾元素


(2)优先队列 priority_queue

push    // 把元素插入堆
pop     // 删除堆顶元素
top     // 查询堆顶元素(最大值)
#include<iostream>
#include<queue>//队列的头文件
using namespace std;
int main ()
{
    queue<int> a;//队列的声明
    a.push(1);//在队头插入一个新元素;
    a.pop();//弹出队尾元素
    a.front();//返回队头
    a.back();//返回队尾
    //优先队列中
    a.top();//取最大值
    a.pop();//去最大值
    //注意:队列没有clear 函数
    q = queue<int>();//重新初始化一个队列,起到清除队列的效果。
    return 0;
}


二、排序算法


1.快速排序


主要思想:分治


解题步骤:


1、确定分界点,如果数据量比较大,到一百万之类的,建议分界点取中间。


2、调整区间,分为>=x,和<=x两个部分。


3、递归处理左右两段。


1669436893779.jpg


##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;//判断数组是否只有1位数或为空
    int x = q[l + r >> 1], i = l - 1, j = r + 1;//设置分界点以及i,j两个“指针”;
    while( i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) //特判如果i,j两指针都不满足i<=x,j>=x这个条件时,交换两个值
        {
            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个数

1669436917370.jpg

#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];//特判如果只有一个数,返回这个数
    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、确定分界点mid = (l+r)/2。


2、递归排序左右两边left,right。


3、归并、合二为一(难点)。

1669436957484.jpg

#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;// 特判区间内如果只有一个数或者为空时,直接return;
    int mid = l + r >> 1;//确定分界点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++];//再次查看左边区间是否还有剩余
        while(j <= r) tmp[k++] = q[j++];//再次查看右边区间是否还有剩余
        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;
}
相关文章
|
29天前
|
程序员 C++ 容器
在 C++中,realloc 函数返回 NULL 时,需要手动释放原来的内存吗?
在 C++ 中,当 realloc 函数返回 NULL 时,表示内存重新分配失败,但原内存块仍然有效,因此需要手动释放原来的内存,以避免内存泄漏。
|
1月前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
69 5
|
1月前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
52 1
|
1月前
|
存储 前端开发 C++
C++ 多线程之带返回值的线程处理函数
这篇文章介绍了在C++中使用`async`函数、`packaged_task`和`promise`三种方法来创建带返回值的线程处理函数。
45 6
|
1月前
|
C++
C++ 多线程之线程管理函数
这篇文章介绍了C++中多线程编程的几个关键函数,包括获取线程ID的`get_id()`,延时函数`sleep_for()`,线程让步函数`yield()`,以及阻塞线程直到指定时间的`sleep_until()`。
23 0
C++ 多线程之线程管理函数
|
1月前
|
算法 安全 Linux
【C++STL简介】——我与C++的不解之缘(八)
【C++STL简介】——我与C++的不解之缘(八)
|
1月前
|
编译器 C语言 C++
C++入门6——模板(泛型编程、函数模板、类模板)
C++入门6——模板(泛型编程、函数模板、类模板)
41 0
C++入门6——模板(泛型编程、函数模板、类模板)
|
1月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
22 0
|
27天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
11天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。