[c语言]总结冒泡排序的一些细节
[c语言]总结冒泡排序的一些细节
1.求解前须知
对于一组乱序的数字，c语言的通常解决方法有两种，冒泡排序和选择排序。本文先介绍冒泡排序。
2.冒泡排序
①名词解释：
土豆哥自己的理解该过程就像水煮沸的逆过程一样，先是大的气泡生成(代表大数)，与下面小的气泡(代表较小数)进行比较，比小的气泡数值大，就往下掉落(即交换两个数的值)，直到大的气泡沉入杯底，这个过程就是执行了一轮冒泡排序，但是要让每一个较大的数字都沉入相应的位置，就要进行多次上述的过程。这样就是完整的冒泡排序。
②代码部分与理解
for(i=0；i<n-1;i++)
for(j=0;j<n-1-i;j++)
if(a[j]>a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
对于关键代码部分，我们知道一共有n个数进行排序，就要进行n-1轮比较。所以外循环控制总比较轮数。
同理，假设第一轮有j个数，这一轮就要与n-1个数比较，那么第二轮就要与n减1再减1个数比较(n-2),因为第一轮已经沉入底的大数不需要比较，第三轮就是n-3，第四轮就是n-4，所以可得：
在每一轮比较完成后，下一轮比较都会比上一轮减少一个，那么第i轮比较就会比上一轮减少i个，i就是外循环的轮次。
内循环控制控制每一次比较个数，然后if判断语句负责将大数往后放，即交换两个数的值。
③冒泡排序的优化。
在一个无序的数组中，冒泡排序最理想的状况是比较一轮，就是把最大的数字放入最后面就实现了有序排放，，此时要比较6回。时间复杂度为O(n)。
比较最多的情况就是每一轮都要把最大数放入到后面，也就类似于一个倒序数组，7，6，5，4，3，2，1。此时要比较
n(n-1)/2,即21回。时间复杂度为O(n²)。
那么如果比较数中有相同或者实行一次冒泡排序后，数值没有变化，那么不就浪费了一轮比较了吗？为了防止出现此类情况，我们可以有加入一个标记flag，来完成上述浪费，即现在循环前加入flag=0，如果这一轮排序了就令flag为1，否则flag为0，即这一回合没排序，跳出循环。
for (i = 0; i < n - 1; i++)//确定排序总共的轮数
{
int flag = 0;
for (j = 0; j < n - 1 - i; j++)//确定每轮比较的此数
{
if (a[j]>a[j + 1])
{
//交换数值
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = 1;//加入标记
}
}
printf("排序了第%d轮",i+1);
if (!flag)
break;//如果没有交换过元素，则已经有序
}
3.完整代码
①未优化的正常冒泡排序
#include<stdio.h>
int main()
{
int i,j,temp,a[666],n;
printf("输入需要排序的个数:\n");
scanf("%d",&n);
printf("输入需排序的%d个数字\n",n);
for(i=0;i<n;i++)
scanf("%d/t",&a[i]);
printf("`````````````````````````\n");
printf("显示未排序数字:\n");
for(i=0;i<n;i++)
printf("%4d",a[i]);
printf("\n");
for (i = 0; i < n - 1; i++)//确定排序趟数
{
for (j = 0; j < n - 1 - i; j++)//确定每轮比较次数
{
if (a[j]>a[j + 1])
{
//交换
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
printf("显示排序完成后的数字:\n");
for(i=0;i<n;i++)
printf("%4d",a[i]);
printf("\n");
return 0;
}
优化后的排序
#include<stdio.h>
int main()
{
int i,j,temp,a[666],n;
printf("输入需要排序的个数:\n");
scanf("%d",&n);
printf("输入需排序的%d个数字\n",n);
for(i=0;i<n;i++)
scanf("%d/t",&a[i]);
printf("`````````````````````````\n");
printf("显示未排序数字:\n");
for(i=0;i<n;i++)
printf("%4d",a[i]);
printf("\n");
for (i = 0; i < n - 1; i++)//确定排序趟数
{
int flag = 0;
for (j = 0; j < n - 1 - i; j++)//确定每轮比较次数
{
if (a[j]>a[j + 1])
{
//交换
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag=1;
}
}
printf("显示%d轮排序后的结果:\n",i+1);
for(j=0;j<n;j++)
printf("%4d",a[j]);
printf("\n");
if(flag==0)
break;
}
printf("显示排序完成后的数字:\n");
for(i=0;i<n;i++)
printf("%4d",a[i]);
printf("\n");
return 0;
}