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

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

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

#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)。