首页 > 代码库 > 交换排序:冒泡排序

交换排序:冒泡排序

交换排序:两两比較待排序记录的关键码,若是逆序,则交换,直到无逆序。

当中最简单的交换排序是:冒泡排序。

冒泡排序(Bubble Sort,也叫起泡排序):不断地比較相邻的记录,若是不满足排序要求,则交换。

交换时,可从前向后。也可从后向前。看一个从前向后的排序过程:

原序列 12  3   45  33  6

下标   0   1   2   3   4

第一趟:

       3   12  45  33  6  (3,12交换)

       3   12  45  33  6  (12,45不用交换)

       3   12  33  45  6  (45,33交换)

       3   12  33  6   45 (45,6交换)

第二趟:

       3   12  33  6  45  (3,12不用交换)

       3   12  33  6  45  (12,33不用交换)

       3   12  6   33 45  (33,6交换)

第三趟:

       3   12  6   33 45  (3,12不用交换)

       3   6   12  33 45  (12,6交换)

第四趟:

       3   6   12  33 45  (3,6不用交换)

结束。以上过程很之详尽,相信你一定懂了。

代码一:

void BubbleSort10(int a[], int n)  //从左向右 
{
	if (a && n > 1)
	{
		int i,j;
		for (i = 1; i < n; i++)     //最多仅仅需进行n-1趟排序  
		for (j = 0; j < n - i ; j++)
		{
			if (a[j] > a[j+1])
			Swap(a[j], a[j+1]);
		} 
	}
}
void BubbleSort11(int a[], int n)  //从右向左 
{
	if (a && n > 1)
	{
		int i,j;
		for (i = 1; i < n; i++) 
		for (j = n - 1; j>=i; j--)
		{
			if (a[j - 1] > a[j])
			Swap(a[j - 1], a[j]);
		} 		
	}
}


继续思考:若是在某一趟排序中,无元素交换,是不是表明已所有有序了呢?

是的!既然如此,下一趟排序就不用进行了。

针对代码一。给出优化的代码二:

void BubbleSort20(int a[], int n)  //从左向右 
{
	if (a && n > 1)
	{
		int i,j = n-1;
		bool flag = true;
		while(flag)
		{
			flag = false;
			for (i = 0; i < j; i++)
			if (a[i] > a[i+1])
			{
				Swap(a[i], a[i+1]);
				flag = true;
			}
			j--; 
		}
	}
}
void BubbleSort21(int a[], int n)  //从右向左 
{
	if (a && n > 1)
	{
		int i,j = 1;
		bool flag = true;
		while(flag)
		{
			flag = false;
			for (i = n - 1; i >= j; i--)
			if (a[i - 1] > a[i])
			{
				Swap(a[i - 1], a[i]);
				flag = true;
			}
			j++; 
		}
	}
}

再思考:下一趟排序向右(或向左)的最远位置,仅仅是简单的减一吗?可否更高效?

有的。记录上一趟排序时交换元素的最远距离,下一趟排序最远仅仅到这个位置。

针对代码二。给出优化的代码三:

void BubbleSort30(int a[], int n)  //从左向右 
{
	if (a && n > 1)
	{
		int i,k,j = n-1;
		bool flag = true;
		while(flag)
		{
			flag = false;
			k = 0;
			for (i = 0; i < j; i++)
			{
				if (a[i] > a[i+1])
				{
					Swap(a[i], a[i+1]);
					flag = true;
					k = i;
				}
			}
			if (k == 0)
				break;
			j = k; 
		}
	} 
}
void BubbleSort31(int a[], int n)   //从右向左 
{
	if (a && n > 1)
	{
		int i,k,j = 1;
		bool flag = true;
		while(flag)
		{
			flag = false;
			k = n - 1;
			for (i = n - 1; i >= j; i--)
			{
				if (a[i - 1] > a[i])
				{
					Swap(a[i - 1], a[i]);
					flag = true;
					k = i;
				}
			}
			if (k == n - 1)
				break;
			j = k; 
		}
	} 
}

交换方法的代码是这样:

void Swap(int &a, int &b)
{
	if(a!=b)
	{
		a^=b;
		b^=a;
		a^=b;
	}
}

測试走起……


小结:

冒泡排序是稳定的。但不高效。时间复杂度是O(n^2)。

转载请注明出处。本文地址:http://blog.csdn.net/zhangxiangdavaid/article/details/30271613


若是有所帮助,顶一个哦!


专栏文件夹看这里:

  • 数据结构与算法文件夹
  • c指针


交换排序:冒泡排序