C++STL函数和排序算法的快排以及归并排序详解 C++STL函数和排序算法的快排以

一、队列是什么？
二、排序算法

1.快速排序
2、归并排序

总结

一、队列是什么？头文件queue主要包括循环队列queue和优先队列priority_queue两个容器。
像栈一样，队列（queue）也是一种线性表，它的特性是先进先出，插入在一端，删除在另一端。就像排队一样，刚来的人入队（push）要排在队尾(rear)，每次出队(pop)的都是队首(front)的人。
就像管道一样先进先出。
队列的相关概念：
1.队头与队尾：允许元素插入的一端称为队尾，允许元素删除的一端称为队头。
2.入队：队列的插入操作。
3.出队：队列的删除操作。
队列的声明：

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

（1）循环队列 queue

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

（2）优先队列 priority_queue

push// 把元素插入堆
pop// 删除堆顶元素
top// 查询堆顶元素（最大值）

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

二、排序算法
1.快速排序
主要思想：分治
解题步骤：
1、确定分界点，如果数据量比较大，到一百万之类的，建议分界点取中间。
2、调整区间，分为>=x,和<=x两个部分。
3、递归处理左右两段。

文章图片

##includeusing 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个数

文章图片

#includeusing 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、归并、合二为一（难点）。

??#includeusing 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; //确定分界点midmerge_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; }

总结 【C++STL函数和排序算法的快排以及归并排序详解】本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注脚本之家的更多内容!