本帖最后由 行我福 于 2015-1-20 22:14 编辑
说到排序,估计新手首先就会反应出来的是冒泡排序,本贴就以冒泡排序开始说起,在此以升序为例来说明~
传统的冒泡有一点暇丝,可能在某一轮冒泡的时候就得到结果,但是计算机不知道,它依旧会进行比较操作,为了改进这一缺点,我定义一个标识符flag,在每轮比较结束之前将flag赋值为1,如果该轮比较操作中发现排序没有完成,那么就在该轮结束时赋值为0,否则不改变其flag值,在下一轮开始冒泡前对flag进行判断,如果其值为1,表示在上一轮排序中已经完成了排序功能,那么就结束排序比较,接下来请看代码:- #include <stdio.h>
- void bubble_sort(int arr[],int n)
- {
- int i,j,flag,temp;
- for(i=0;i<n-1;i++)
- {
- flag=1;
- for(j=0;j<n-i-1;j++)
- {
- if(arr[j]>arr[j+1])
- {
- temp=arr[j];
- arr[j]=arr[j+1];
- arr[j+1]=temp;
- flag=0;
- }
- }
- if(1==flag) break;
- }
- printf("\n比较操作进行了%d轮",i+1);
- return;
- }
- int main()
- {
- int a[]={12,54,67,89,96};
- int i;
- printf("排序前\n");
- for(i=0;i<5;i++)
- {
- printf("%d\t",a[i]);
- }
- bubble_sort(a,5);
- printf("\n排序后\n");
- for(i=0;i<5;i++)
- {
- printf("%d\t",a[i]);
- }
- return 0;
- }
复制代码 在上述代码,排序中加了一个打印输出语句,用于输出比较进行多少轮。由于最初给定的数组是一个有序的数组,因此比较操作只进行了一轮,但是如果没有若没有代码中使用flag,那么,即使是对有序的数组进行排序,同样进行5轮操作,使用标志符之后,算法的效率得到了提高。 根据上述,冒泡排序的时间复杂度是O(n^2);
|
-
图片1.png
(4.4 KB, 下载次数: 11)
冒泡排序改进版截图
|