雅乐网

冒泡排序是一种很常见的简单排序。它依次扫描要排序的序列，比较两个相邻的元素，如果逆序就交换位置。

每次经过扫描一趟后，未排序部分最大的元素就“冒泡”到了最上面。

函数接口

void bubble_sort1(int *a, int low, int high)

接受的参数 数组的第一个元素地址  排序的区间 [low, high) 注意：前闭后开

思路

整个序列可以分成两个部分 左边的无序部分和右边的有序部分。

用last将两个部分隔开，无序部分为[low, last)  有序部分为[last, high)

最开始的情况下 另last=high-1 。将最后一个元素看作排好序的。只有一个元素的数组肯定是有序的。

接下来，在有序区间小于总区间的情况下（last > low）不断循环（外层循环）

（内层循环）从i = low开始 依次比较相邻的两个元素

a[i]和a[i+1] 然后i++ 。比较到什么时候结束呢？到了i=last的时候就可以结束了，这时候无序部分已经比较完了。

在这个过程中，设置了一个中间变量sorted 记录比较的时候最后一次交换时元素的下标 内层循环完成时，sorted以后的元素全部有序。

然后将last = sorted 进行下一次外循环。

代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 1000

void bubble_sort1(int *a, int low, int high);

int main(void)
{
	int i;
	int a[N];

	srand((int)time(NULL));

	for (i = 0; i < N; ++i)
	{
		a[i] = rand() % 10000;
	}

	bubble_sort1(a, 0, N);

	for (i = 0; i < N; ++i)
		printf("%d ", a[i]);
	printf("\n");

	return 0;
}

void bubble_sort1(int *a, int low, int high)
{
	int last = high - 1;
	int tmp;
	int sorted;
	int i;
	while (last > low)
	{
		i = low;
		sorted = low;
		while (i < last)
		{
			if (a[i] > a[i+1])
			{
				tmp = a[i+1];
				a[i+1] = a[i];
				a[i] = tmp;
				sorted = i+1;
			}
			++i;
		}
		last = sorted;
	}
}