经典排序算法小记（一）―― 冒泡排序两种实现 - JAVA

我想学习过排序的人，第一个学习的就是冒泡排序吧。反正我是，也是最清楚的一个，汗颜。。。这里以从小到大举例。排序思路：设数组长度为N。 1.比较相邻两个数据的大小，如果前面数据大于后面数据，则交换两个数据。 2.这样从0到N-1进行遍历了一遍后，最大的数就“冒泡”到了数据的结尾。 3.N=N-1，重复上述操作指导N=0为止。
时间复杂度：O(n^2) ；空间复杂度：O(1) ；稳定性：稳定。
由思路很容易写出代码：

void BubbleSort1(int a[],int n) 
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		for(j = 1; j < n-i; j++) {
			if(a[j-1] > a[j]) {
				Swap(a[j-1],a[j]);
			}
		}
	}
}

不过仔细的人应该会注意到，如果数据本来就有序，那么排序还是会一趟一趟的进行，这样就浪费时间了下面是对代码的改进：

//设置一个标志，当无数据交换时，则说明排序完成，则直接结束循环。
void BubbleSort2(int arr[],int n) 
{
	int i, j;
	bool flag;

	j = n;
	flag = true;
	while (flag)
	{
		flag = false;
		for(i = 1; i < j; i++) 
		{
			if(arr[i-1] > arr[i]) 
			{
				Swap(arr[i-1], arr[i]);
				flag = true;
			}
		}

		j--;
	}
}

对遍历加一个标志，如果在一趟遍历中任何两数都没有发生交换，那么排序已完成。就算没有遍历N-1趟，循环依然完成。
冒泡排序是一种效率非常低下的排序方法，在数据量比较小时还排的上用场。