冒泡排序

冒泡排序的思想

?冒泡排序的代码实现

活动地址：CSDN21天学习挑战赛

冒泡排序的思想

冒泡排序一般是编程初学者接触的第一个排序算法，因为其思想简单明了，很容易被接受，实现的代码也比较容易编写。冒泡排序的思想本质上就是两两交换，通过多次交换之后，最终形成有序数字。

例如将4 1 5 3 这四个数字排成升序，从下标 0 也就是4开始，4大于1，交换4和1，4不大于5，不交换，接着5大于3，5与3交换，第一轮排序结果为 1 4?3?5?接着从下标 1 也就是4开始，4大于3，交换4与3，4不大于5，故不交换，第二轮排序结果仍为 1 3 4?5?再接着从下标 2 也就对应着4，4不大于5，不交换，排序后的结果为 1 3 4 5，最后一个数字是不用排的

?冒泡排序的代码实现

伪代码

for i = 1 to n-1
? ? change = 0
? ? for j = n downto i + 1
? ? ? ? if A[j] < A[j - 1]
? ? ? ? ? ? exchange A[j] with A[j-1]
? ? ? ? ? ? change = 1
? ? if change == 0
? ? ? ? return

原本的冒泡排序的代码是

for i = 1 to n-1
? ? for j = n downto i + 1
? ? ? ? if A[j] < A[j - 1]
? ? ? ? ? ? exchange A[j] with A[j-1]
? ? ? ? return

加上change能起到优化的作用，如果传入一个有序的数组给未经优化的冒泡排序，那么这个程序可不会管你有序无序，先从头到尾给你排一遍，每排一个位置就要进行从头到尾的判断，白白消耗时间。而加上change情况就不一样了，先给 change 赋值 0 ，假设它是有序的，然后从第一个数开始逐个判断，如果出现了交换就说明是无序的，change被修改为1，未出现交换就说明整个数组是有序的，change值未被修改，直接退出程序，避免无意义的对比

c/c++代码实现

void bubble(int * arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		int change = 0;
		for (int j = 0; j < size - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
				change = 1;
			}
		}
		if (change == 0)
			return;
	}
}

int main()
{
	int arr[] = { 34, 3, 56, 24, 67, 89 , 44, 15, 90, 5, 19, 107, 47, 10 };
	int size = sizeof(arr) / sizeof(int);

	bubble(arr, size);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
}