数据结构笔记 - 排序算法 优化冒泡排序算法

一般的冒泡排序算法一般会进行L->length – 1次外部循环,但是有时候数组在循环到一半时就已经排序好了,但是这时循环还是不断的进行下去,一直做比较操作,尽管没有交换数据,但是做了很多不必要的比较操作。

我们可以在程序中设置一个flag标志位,当发现这一轮中没有交换动作时,就表明该数组是排序好的,这样就可以设置flag为false,退出循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>

#define MAXSIZE 100 /* 待排序数组的大小 */

typedef bool Flag; /* 是否在这一轮循环中有进行数据的交换 */

typedef struct
{
int r[MAXSIZE+1]; /* 待排序数组r,r[0]为哨兵或临时变量 */
int length; /* 待排序数组的长度,为了方便理解,不包含r[0]元素 */
}SortList;

/* 优化了的冒泡排序算法 */
void BubbleSort03(SortList *L)
{
int i,j;
Flag flag=true;
int temp;
/* 如果flag是true说明有数据交换过,否则表明数组已经是顺序的了,退出循环 */
for(i=1;i<L->length && flag;i++)
{
flag=false;
for(j=L->length;j>i;j--)
{
if(L->r[j-1]>L->r[j])
{
/* 交换r[j-1]和r[j]的值 */
temp=L->r[j-1];
L->r[j-1]=L->r[j];
L->r[j]=temp;
flag=true;
}
}
}
}

冒泡排序算法的时间复杂度分析:

最好的情况下,即数组本身是排序好的,这时进行n-1次比较,时间复杂度为O(n);最坏的情况下,即数组是逆序的,需要比较次数为:1+2+3+…+(n-1)=n(n-1)/2,推导出时间复杂度为O(n^2)。

arthinking wechat
欢迎关注itzhai公众号