桶排序、冒泡排序、快速排序
排序
一、桶排序
1、算法思想与原理
- 设置两个数组，分别存放桶和输入的因素
- 桶数组通过循环排序后，输入数字出现几次，在对应桶处标记几次并打印
- 依次打印排序后的数据
2、算法思路
- for循环：初始化数组、输入一串数字并读入数组、依次判断标记桶、打印排序好后的数组
3、代码实现
3.1最简单粗暴滴方法
#include
#include
using namespace std;
int main()
{
int a[11],i,j,t;
//int n[5];
for(i=0;i<=10;i++) //将数组中的所有初始化为0
a[i]=0;
for(i=1;i<=5;i++) //循环输入5个数
{
cin>> a[i];
}
for(i=0;i<=10;i++) //依次判断a[0]~a[10]
for(j=1;j<=a[i];j++) //依次打印排序好的数列
cout< 说明：
（1）只能输入事先预定设置的数组个数
（2）数组中每个数的大小不能超过10
（3）没有人机交互
优化:
（1）从大到小排序
（2）先指定输入数组的大小再完成
3.2 进阶可指定数组大小
#include
#include
using namespace std;
int main()
{
int a[201],i,j,t,n;
for(i=0;i<=200;i++) //将数组中的所有初始化为0
{
a[i]=0;
}
cin>>n; //输入一个数n，表示接下来的数组中有n个数
for(i=1;i<=n;i++) //循环输入n个数
{
cin>>a[i]; //把变量读入桶中
a[i]++; //在对应桶中计数
}
for(i=0;i<=n;i++) //依次判断a[0]~a[n]
for(j=1;j<=a[i];j++) //依次打印排序好的数列
cout< 效果如下：
错误：2、9、1变成了指定1、2、3数字的个数
错误原因：存放输入数组数据时，没有用一个数组来存放，导致最终丢失输入数据
修改如下：
#include //调用万能头文件
using namespace std;
#define MAX 200 //定义数组长度
int n,a[MAX],t[MAX]; //分别定义两个数组、t[MAX]存放初始化桶、a[MAX]存放输入数组
int main(){
memset(t,0,sizeof t); //桶数组初始化为0
cin>>n; //输入数组元素数量，也可以用scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>a[i]; //读入数组每一个元素
t[a[i]]++; // 在初始化桶中计数
}
for(int i=0;i<=n;i++){ //!!!依次判断a[0]~a[n],所以i一定要从0开始，否则会漏掉数组里的数字
if(t[i]!=0){
for(int j=1;j<=t[i];j++) cout< 运行正确。
4、总结
（1）时间复杂度：O（M+N） m：桶的个数，n：待排序的个数
（2）缺点：不可对负数进行排序，因为数组的编号只能从a[0]开始
? 优点：是一个非常快速的排序方法
二、冒泡排序
1、算法思想与原理
思想：每次比较相邻的元素、若顺序错误则交换过来
原理：n个数进行排序，进行n-1次排序操作。“每一趟”需从第一位开始进行相邻两个数的比较，直至最后一个数比较完成。
2、算法逻辑
- 设置for循环进行整体n-1趟比较（n为输入数组个数）
- 循环将第i个数依次后后面每一个数字作比较
- if条件进行大小比较，并交换
- 循环输出结果
3、代码实现
蓝桥杯：基础练习——BASIC-13 数列排序
#include
#include
using namespace std;
int main()
{
int a[100];
int i,j,t,n;
cin>>n; //输入一个数，表示接下来有3个数
for(i=1;i<=n;i++) //循环读入n个数到数组a中
{
cin>>a[i];
}
//冒泡排序核心部分
for(i=1;i<=n-1;i++) //n个数排序，只需要进行n-1趟
{
for(j=1;j<=n-i;j++) //从第1位开始比较直到最后一个尚未归为的数 。
//第i个数比较时只需要比较后面的n-i位 ,所以循环中时n-i即可
{
if(a[j]>a[j+1]) //比较大小并交换
{
t=a[j]; a[j]=a[j+1]; a[j+1]=t;
}
}
}
//输出结果
for(i=1;i<=n;i++)
{
cout< 代码完善后可完成按照名字对应的分数排序，代码修改如下：
#include
#include
using namespace std;
struct student //此处创建一个结构体储存姓名和分数
{
char name [21];
char score;
};
int main()
{
struct student a[100],t;
int i,j,n;
cin>>n; //输入一个数，表示接下来有3个数
for(i=1;i<=n;i++) //循环读入n个名字到结构体中
{
cin>>a[i].name;
}
for(i=1;i<=n;i++) //循环读入n个分数到结构体中
{
cin>>a[i].score;
}
//冒泡排序核心部分
for(i=1;i<=n-1;i++) //n个数排序，只需要进行n-1趟
{
for(j=1;j<=n-i;j++) //从第1位开始比较直到最后一个尚未归为的数 。
//第i个数比较时只需要比较后面的n-i位 ,所以循环中时n-i即可
{
if(a[j].score>a[j+1].score) //比较大小并交换
{
t=a[j]; a[j]=a[j+1]; a[j+1]=t;
}
}
}
//输出结果
for(i=1;i<=n;i++)
{
cout< 4、小结
- 时间复杂度：O(N ^ 2 )
三、快速排序
1、算法思想：
? 基于“二分”的算法思想，选取一个基准数将和两个指针分别指向数列的两端，并与基准数进行大小比较。通过比较完成对基准数的归位，即基准数左边比其大右边比其小。依次选取基准数归位后，便可完成整个数列的排序。
- 1．先从数列中取出一个数作为基准数。
- 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 3．再对左右区间重复第二步，直到各区间只有一个数。
2、算法实现
① 从数列中挑出一个元素，称为 “基准”（pivot），
② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
③ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
3、代码实现
#include
#include
using namespace std;
#include
using namespace std;
void quickSort(int array[],int left,int right) //left,right分别是数组的起始下标
{
int i,j,k,temp;
if(left=k)) //顺序很重要，要先从右往左找
j--;
if(i>n;
for (i = 0; i>a[i];
}
quickSort(a, 0, 10);
cout<<"输出数组元素:"<