26.冒泡排序

每当皇帝选妃时，首席太监小桂子总是忍不住在旁边偷窥这些候选的美女，有一次他发现做为伴读小书童的你居然犯了个常人都可以轻易看出的错误，有几位候选的美女站成如下一排：

当我们采用前面的选择排序时，我们仍然要将候选者遍历5遍，才能完成最终的排序，但其实，本身这些美女除了第一个外，已经很有序了，我们只需要把第一个和第二个交换，然后又和第三个交换，如此循环，直到和最后一个交换后，整个数组基本就有序了！

当然，并不是每次都这么幸运，像下面的情况就会更复杂一些，一趟并不能完全解决问题，我们需要多趟才能解决问题.

经过上述五步后，得到的结果:

此时，我们只保障了最后一个数是最大的，并不能保障前面的数一定会有序，所以，我们继续按照上面五步对剩下的5个数继续进行一次排序，数组就变得有序了。

以上过程就是冒泡排序: 通过重复地遍历未排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢得像泡泡一样“浮”到数列的顶端，故而得名!

代码实现:

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

void swap(int* num1, int* num2)//交换两个指针保存的值
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}

void BubbleSort(int arr[], int len)//冒泡排序
{
	for (int i = 0; i < len - 1; i++)
	{
		bool sorted = true;

		for (int j = 0; j < len - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
				swap(&arr[j], &arr[j + 1]);
			sorted = false;
		}

		if (sorted) break;//没有发生交换，顺序正确，退出
	}
}

int main()
{
	int beauties[] = { 163, 161, 158, 165, 171, 170, 163, 159, 162 };
	//第一趟161 158 163 165 170 163 159 162 -- 171
	//第二趟158 161 163 165 163 159 162 -- 170 171
	//第三趟158 161 163 163 159 162 -- 165 170 171
	//第四趟158 161 163 159 162 -- 163 165 170 171   稳定的排序算法
	//第五趟158 161 159 162 -- 163 163 165 170 171
	//第六趟158 159 161 -- 162 163 163 165 170 171
	//第七趟158 159 161 待排序的数据没有产生交换，排序结束
	int len = sizeof(beauties) / sizeof(beauties[0]);

	BubbleSort(beauties, len);

	printf("美女排序以后的结果是：\n");
	for (int i = 0; i < len; i++)
	{
		printf("%d ", beauties[i]);
	}


	system("pause");
	return 0;
}

参考资料来源：

奇牛学院