前言：
👏作者简介：我是笑霸final，一名热爱技术的在校学生。
📝个人主页：个人主页1 || 笑霸final的主页2
📕系列专栏：《数据结构与算法》
📧如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀
🔥如果感觉博主的文章还不错的话，👍点赞👍 + 👀关注👀 + 🤏收藏🤏
一、前言
-
欢迎报名
字节跳动青训营 线上免费参加 详情请看链接点此查看详情 -
上一章回顾：第一周练习——认识复杂度和简单排序算法
二、归并排序
给你一个n代表有n个数字，给出这n个数字，然后你需要使用归并排序将这些数字从小到大排好。
输入描述:
第一行输入一个n，代表有n个数字
第二行输入n个数
输出描述:
输出排序好后的n个数
示例1
输入:
4
4 3 2 1
输出:
1 2 3 4
代码
#include<bits/stdc++.h>
using namespace std;
void sort(vector<int> &nums,int l,int r){
if(l>=r) return;
long mid=l+((r-l)>>1);
//递归左右
sort(nums,l,mid);
sort(nums,mid+1,r);
//合并
//创建辅助数组
vector<int> help(r-l+1);
int i=0;//辅助数组的下标
int p1=l;//左边的下标
int p2=mid+1;//右边的下标
while(p1<=mid && p2<=r){
help[i++]= nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
}
while(p1<=mid){
help[i++]=nums[p1++];
}
while(p2<=r){
help[i++]=nums[p2++];
}
//合并到原来的数组
for(int i=0;i<r-l+1;i++){//这里注意别越界
nums[l+i]=help[i];
}
}
int main(){
int n=0;
cin>>n;
if(n<=0)return 0;
vector<int>nums(n);
for(int i=0;i<n;i++){
cin>>nums[i];
}
sort(nums,0,n-1);
for(int i=0;i<n;i++){
cout<<nums[i]<<" ";
}
return 0;
}
三、堆排序
什么是堆？
堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的 数组 对象。
问题？
给你一个n代表有n个数字，给出这n个数字，然后你需要使用归并排序将这些数字从小到大排好。
输入描述:
第一行输入一个n，代表有n个数字
第二行输入n个数
输出描述:
输出排序好后的n个数
示例1
输入:
4
4 3 2 1
输出:
1 2 3 4
代码
#include <bits/stdc++.h>
using namespace std;
void heapSort(vector<int> &v){
//大根堆，小根堆，大根堆排升序，小根堆排降序
int size = v.size();
while(size > 0){
int i = size / 2 -1; //从二叉树的最后非叶子结点开始
//遍历非叶子节点
for(;i>=0;i--){
int mx = v[i]; //取当前根节点为默认的最大值
if(i*2+2<size){//存在右节点
if(v[i*2+1] < v[i*2+2])
swap(v[i*2+1] , v[i*2+2]);//把较大值换到左节点
}
if(mx < v[i*2+1]) swap(v[i*2+1] , v[i]);
}
size--;
swap(v[0],v[size]);
}
}
int main(){
int n;
cin>>n;
vector<int> v(n,0);
for(int i = 0;i<n;i++) cin>>v[i];
heapSort(v);
for(auto i:v) cout<<i<<" ";
return 0;
}
随堂习题-给气球分类题目【荷兰国旗问题】
牛牛今天带来了一排气球，气球有n个，然后每一个气球里面都包含一个数字，牛牛是一个善于思考的人,于是他就想到了一个问题，
牛牛随便给你一个值K，这个值在这些气球中不一定存在，聪明的你需要把气球中包含的数字是小于K的放到这排气球的左边，大于K的放到气球的右边，
等于K的放到这排气球的中间，最终返回一个整数数组，其中只有两个值，分别是气球中包含的数字等于K的部分的左右两个下标值,如果气球中没有K这个数字就输出-1，-1。
输入描述:
第一行的输入为n和K，n代表有多少个气球，K代表牛牛选的数
第二行需要输入n个大小的数组a，a[i]代表每个气球中放的数字，
其中1 <=N,K<=1000,1<=a[i]<=1000。
输出描述:
一行，输出返回数组中的那两个值。
示例1
输入:
10 3
1 4 0 0 3 1 5 3 1 1
输出:
6 7
说明:
气球按照题意处理后变成下面的样子
1 1 0 0 1 1 3 3 5 4
你会看出3 3的位置一个在6 一个在7
#include <iostream>
using namespace std;
int partation(int L,int R,int n,int a[n],int k)
{
int less = L - 1;//左边界
int more = R + 1;//右边界
int index = L;//下标
while(index < more){
if(a[index] < k){//小于目标值
swap(a[index++],a[++less]);//交换左边界的下一个值和当前下标的值 然后下标+1
}
else if(a[index] > k){//大于目标值
swap(a[index],a[--more]);//交换右边界的下一个值和当前下标的值
//注意这里下标值不需要+1
}
else{
index++;
}
}//while循环结束
if(less + 1 > more -1){
cout << -1 <<" "<< -1;
}
else{
cout << less+1 <<" "<< more-1;
}
return 0;
}
int main(){
int n,k;
cin>>n>>k;
int *a = new int[n];
for(int i = 0;i<n;i++){
cin >> a[i];
}
int L = 0;
int R = n - 1;
partation(L,R,n,a,k);
return 0;
}
四、快速排序
快速排序原版
改进 在数组中随机取一个数 和数最后的那个数交换 然后以这个数为划分值 其他过程一样
给你一个n代表有n个数字，然后你需要使用快速排序将这些数字从小到大排好
输入描述:
第一行输入一个n，代表有n个数字
第二行输入n个数中1 <=N,K<=1000,1<=a[i]<=1000。
输出描述:
输出排序好后的n个数
示例1
输入:
4
4 3 2 1
输出:
1 2 3 4
#include <iostream>
using namespace std;
int help[2];
int *partition(int *arr,int L,int R,int* help){
int less=L-1;
int more=R;
while(L<more){
if(arr[L]<arr[R]){
swap(arr[++less], arr[L++]);
}
else if(arr[L]>arr[R]){
swap(arr[L], arr[--more]);
}
else{
L++;
}
}
swap(arr[more],arr[R]);
help[0]=less+1;
help[1]=more;
return help;
}
void quicksort(int *arr,int L,int R){
if(L<R){
int p=rand()%(R-L+1)+L;
swap(arr[R],arr[p]);
int *help2=partition(arr,L,R,help);//荷兰国旗问题 划分区间
quicksort(arr,L,help2[0]-1);
quicksort(arr,help2[1]+1,R);
}
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
quicksort(arr,0,n-1);//快排
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}