每日编程一刷（木桶快速排序）

本文主要是介绍每日编程一刷（木桶快速排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 前言
- 正文
- - 错误代码
- 木桶排序法
- - 投机取巧法

。# 每日编程一刷（木桶快速排序）

前言

在这里插入图片描述

欢迎来到每日编程题目一刷环节这次给大家带来的这道题目可以涉及木桶排序一个比较的简单快速排序的算法

思路很简单但是很巧妙这里结合一道例题进行解释

详情知识点请看这

正文

在这里插入图片描述

桶排序的核心思路就是将我们的数据进行穷举处理然后一一进行判断我们的数据是不是符合

比如说有下面 7 8 2 1 19 这些数据

这些数据我们首先将这个数组的所有值都赋值成为0 0代表的就是说我们的所有数据都是从0开始进行递增的就是一开始还是没有数据的

一直慢慢的往后增加只要是对应下标我们就进行++处理操作

下面代码进行演示

#include <stdio.h>int main(){int book[1001],i,j,t,n;for(i=0;i<=1000;i++)book[i]=0;scanf("%d",&n);//输入一个数n，表示接下来有n个数for(i=1;i<=n;i++)//循环读入n个数，并进行桶排序{scanf("%d",&t);  //把每一个数读到变量t中book[t]++;  //进行计数，对编号为t的桶放一个小旗子 方便我们最后输出一共有几个棋子在里面 其实排序是在打印顺序上面体现出来的}return 0;}

在这里插入图片描述

错误代码

//运行超时代码算法复杂度高(对于数组很大的时候就不适合使用)

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;int m=0;int j;cin>>n;vector<int>arr1(n);vector<int>arr2(n);for(int i=0;i<n;i++){cin>>arr1[i];//}for(int i=0;i<n;i++)//两层for循环进行判断 复杂度高{for(j=0;j<m;j++){if(arr1[i]==arr2[j]){break;}}if(j==m){arr2[m]=arr1[i];m++;}}sort(arr2.begin(),arr2.begin()+m);for(int i=0;i<m;i++){cout<<arr2[i]<<" ";}
}

木桶排序法

#include<stdio.h>
//桶排序，给出足够多的桶，每个桶里统计输入数字的次数(用于大量数据排序)
int main(){int n=0;int temp=0;scanf("%d",&n);//int maxn=0;int arr[1000005]={0};while(scanf("%d",&temp)!=EOF){getchar();arr[temp]++;//temp对应的数装进编号为temp的桶里，出现就++}for(int i=1;i<1000005;i++){//从小到大输出每个桶的编号,未出现的不打印
//         while(arr[i]--){//有重数方式打印
//             printf("%d ",i);
//         }if(arr[i]){//无重数打印printf("%d ",i);}}return 0;
}

投机取巧法

//投机取巧的方法在打印和排序上边下功夫

但是这个方法可以解决我们如果输入的数据是负数的话那么这个方法就可以排上用场了

#include<iostream>
#include<algorithm>//sort需要包含的头文件using namespace std;
int main()
{int n,t;cin>>n;int k[n+1];//数组，把n个数都放进去for(int i=0;i<n;++i){cin>>k[i];//逐个输入}sort(k,k+n);//sort可以排序//这个方法for(int j=0;j<n;++j){if(k[j]==k[j+1])continue;//重复的不输出 *** 这一点很重要cout<<k[j]<<" ";}return 0;
}

#include<iostream>
#include<algorithm>//sort需要包含的头文件
//木桶排序对于正整数才是真的有用 且效率高 木桶速排
using namespace std;
int main()
{int arr[1000005]={0};//对木桶进行初始化 局限性是这个数组是整数才行 因为我们里面的下表是整数 这个限制还是比较大的int n;int tmp;cin>>n;while(cin>>tmp){getchar();arr[tmp]++;//这个代码的意思就是说 如果这个数据有了的话就在我们的木桶里面进行++处理的操作}for(int i=1;i<1000005;i++)//这个是数据 我们输入的木桶{if(arr[i])//这个代码是判断只要不是空 我们就可以进行打印{cout<<i<<" ";//这个是处理不重复的数据}
//         while(arr[i]--)//这个是进行重复排序 其实是相当于是
//         {
//             cout<<i<<" ";
//         }}
}

本次刷题感到了算法的重要性因为自己本身对于算法的接触的较少本次的算法知识还是多亏了牛客网上的解析才察觉自己的代码的优化行还需要进行提升今天打卡完成明天再接再厉！！！！

在这里插入图片描述