一.冒泡排序
1.概念
冒泡排序这种排序方法其实关键词就在于冒泡两个字,顾名思义就是数字不断比较然后最大的突出来,也就是说把相邻的两个数字两两比较,当一个数字大于右侧相邻的数字时,交换他们的位置,当一个数字和他右侧的数字小于或等于的时候,不交换。
2.图解
关于冒泡排序我自己画了一幅图来描述他的一轮过程
这里我举了五个无序的数{7,3,6,5,4}
由此可看出他不断与右侧相邻的数字进行比较,当他大于右边的数字就交换,否则不交换,就用这种方法不断进行排序进行很多轮,最后得出一个有序的序列{2,4,5,6,7}。
3.代码的思路
冒泡循环是一种有序的序列,有上图我们不难看出冒泡循环一轮需要进n-1次比较然后开启下一层,而且你一轮比较完了之后最后一个最大的数就不用再参与比较循环了,所以下一次的循环可以减少一次。
因此我的思路是利用两次for循环,一次循环来当取第二次循环的次数,然后依次减少第二次for循环的次数,简便了很多过程,然后数组两个相邻的数字进行依次比较,大于右边的也就是大于下一位的交换位置,否则不交换,所以我的两个for循环的代码如下(其实这也算是个万能代码,就冒泡循环这一块)当然i,k,b都需要来定义的,n为比较序列中元素个数。
这个代码也用了两次for循环所以我们不难推算出时间复杂度为o(n^2)
for(i=0;i<n-1;i++)
{
for(k=0;k<n-1-i;k++)
{ if(a[k]>a[k+1])
{ b=a[k];
a[k]=a[k+1];
a[k+1]=b;
}//交换a[k]与a[k+1]位置
}
}
4.代码例子
我自己也写了一个代码,输入a[10]序列的数字,然后冒泡循环进行排序来实现
#include<stdio.h>
int main()
{
int a[10], i, j, b, k;
for (i = 0; i < 10;i++)
{
printf("输入第%d个数为:", i+1);
scanf_s("%d", &a[i]);
}
for (k = 0; k < 9; k++)//外部循环
for (i = 0; i < 9 - k; i++)//内部循环
if(a[i] > a[i + 1])//
{
b = a[i];
a[i]= a[i + 1];
a[i + 1] = b;
}
printf("排出序列为:");
for(i = 0; i < 10; i++)
printf("%d ", a[i]);
return 0;
}
最后运行也是成功的
二.选择排序
1.概念
选择循环的主要是选择,选择一个元素去进行比较,假如这个数比他小,换成嘞个数继续比较,最后找出最小值与数组第一位的数进行交换。然后一直这样循环下去,直到代码排序完成。也就是通过一个中间量从带排序的的数中找出最大或最小的交换到对应位置。
2.图解
关于选择排序我自己花了一幅图来描述他的一轮比较
我用了五个无序数来做例子{2,1,4,-3,3}
由此可以看出选择比较的过程,这里我用指针代指了需要的中间量,刚开始指针指向2,然后2去比较,1<2,所以指针指向较小值,指针指向1,最后就这样找出-3为最小值和第一个交换,得到第一轮循环比较的数列{-3,1,4,2,3}。
3.代码的思路
其实观察上图一轮循环次数还有循环完一轮之后,不需要用最小值比较可以看出其实他和冒泡循环有点相似,都是循环一轮需要进n-1次比较然后开启下一层,而且下一次循环可以减少一次。
所以我的思路是,依然运用两次for循环,与冒泡循环不同的是我需要一个中间商,所以我可以引用一个局部变量来帮助我,这个局部变量就是图解的指针,局部变量就是数组对应元素的位置,不断进行比较,当他小于一个数时,他就等于嘞个数的位置数,继续比较,直到循环结束找出最小值,最小值跟第一位换位置,一次循环直到排出有序序列为止。所以代码如下
for(i=o;i<n-1:i++)//循环数列取得数开始依次比较
{
int x=i;//x为中间商
for(k=i+1;k<n;k++)//从循环数列取得数后一位开始循环数列取得数进行依次比较
{
if(a[x]>a[k])//得出最小值
k=x;
if(x!=i)//将得到的最小值跟最前面的数字进行交换
{ t=a[i];
a[i]=a[x];
a[x]=t;
}
}
}
这也是一个万能代码可以用在选择序列上。
总结
到此这篇关于C++冒泡排序与选择排序详解的文章就介绍到这了,更多相关C++冒泡排序 选择排序内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!