十大经典排序算法之一--冒泡排序

1、冒泡排序概念

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

2、算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

3、动画演示

4、过程示例

给出数列

• 先排数字9，以此比较与交换

  

• 然后是数字6

  

• 数字1比3小，3比5小 ，所以5不动

  

• 以此类推1，3不动

  

5、算法实例

#include "stdio.h"

void bubble_sort(int* arr, int e)
{
	int temp = 0;
	for (int i = 0; i < e - 1; i++)
	{
		for (int j = 0; j < e - i - 1; j++)
		{
			if (arr[j + 1] < arr[j])
			{
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
	}
}

void print(int* arr, int e)
{
	for (int i = 0; i < e; i++)
	{
		printf("%d ", arr[i]);
	}
}

int main()
{
	int arr[5] = { 2,8,9,5,4 };

	bubble_sort(arr, 5);
	print(arr, 5);

	return 0;
}

优化：

假设我们现在排序ar[]={1,2,3,4,5,6,7,8,10,9}这组数据，按照上面的排序方式，第一趟排序后将10和9交换已经有序，接下来的8趟排序就是多余的，什么也没做。所以我们可以在交换的地方加一个标记，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去

#include "stdio.h"

void bubble_sort(int* arr, int e)
{
	int temp = 0;
	int flag = 0;
	for (int i = 0; i < e - 1; i++)
	{
		flag = 0;
		for (int j = 0; j < e - i - 1; j++)
		{
			if (arr[j + 1] < arr[j])
			{
				temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
				flag = 1;
			}
		}
		if (flag == 0)  //如果没有交换过元素，则已经有序
		{
			return;
		}
	}
}

void print(int* arr, int e)
{
	for (int i = 0; i < e; i++)
	{
		printf("%d ", arr[i]);
	}
}

int main()
{
	int arr[5] = { 2,8,9,5,4 };

	bubble_sort(arr, 5);
	print(arr, 5);

	return 0;
}