先随机生成一组数组
#include<stdio.h>
#include<time.h>
int main()
{
time_t ts;
unsigned int date=time(&ts);//获取时间种子
srand(date);//产生种子
int a[100];
int max,min;
//生成随机数组
for(int i=0;i<100;i++)
{
a[i]=rand()%300;
}
//打印数组
for(i=0;i<100;i++)
{
printf("%d\t",a[i]);
}
return 0;
}
选择排序法是选择最大值或最小值
最大值最小值代码如下
int max=a[0],min=a[0];//初始化,如果不进行此操作,垃圾数据会影响结果
for(i=0;i<100;i++)
{
if(a[i]>max)
{
max=a[i];
}
}
printf("max=%d\n",max);
//找到最小值
for(i=0;i<100;i++)
{
if(a[i]<min)
{
min=a[i];
}
}
printf("min=%d\n",min);
选择排序法分析
顺序排列,从小到大
1.找到最小的数min
2.最小值放在开头 比如a[0].
3.继续循环,最小值放在a[1]
这样要解决的问题就是
1.找到min的下标kmin
2.然后交换a[i]与kmin
#define N 100
int kmin=0;//记录者min的下标
for(i=0;i<N-1;i++)//a[0]与剩下N-1个数做比较
{
kmin=i;//记录下标
for(int j=i+1;j<N;j++)//遍历剩下的数,直到最后一个数
{
if(a[j]<a[kmin])
{
kmin=j;
}
}
if(kmin!=i)//如果a[i]就已经是最小值,就不交换
//如果找到a[i],与a[kmin]交换位置
{
int temp=a[kmin];
a[kmin]=a[i];
a[i]=temp;
}
}
选择排序法做的次数,N=100为例,选择100+99+98+……次,N*(N-1)/2,时间复杂度N^2,理解较为容易,但是是最慢的排序方法
冒泡排序法
设计思想,每一次循环,都让最大的数沉底,或者最小的数浮头
两两交换,我们来演示一趟冒泡
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
int main()
{
int a[10]={3,1,4,3,26,7,4,2,5,7};
#define N=10
for(int i=0;i<N-1;i++)//N个数,从第一个数开始要做N-1次两两比较
{
if(a[i]>a[i+1])//对比
{
int temp=a[i];//保留临时交换变量
a[i]=a[i+1];
a[i+1]=temp;
}
for(int k=0;k<10;k++)//新建一个下标来控制输出
{
printf("%d ",a[k]);
}
printf("\n");
}
return 0;
}
这里我们可以看到,26这个最大的数逐渐沉底了
弄清这个原理后,我们完成完整的冒泡排序
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
int main()
{
int a[10]={32,15,44,31,26,72,43,24,57,17};
#define N 10
for(int i=0;i<N-1;i++)//从0开始,N个数比较N-1趟
{
for(int j=0;j<N-1-i;j++)//如果比较了i趟,剩下要排序的数就变成了N-i个,这N-i个数要进行N-i-1次两两比较
{
if(a[j]>a[j+1])//对比
{
int temp=a[j];//保留临时交换变量
a[j]=a[j+1];
a[j+1]=temp;
}
}
for(int f=0;f<10;f++)
{
printf("%d ",a[f]);
}
printf("\n");
}
return 0;
}