冒泡排序-排序算法

前言

如果有6个人站成一排，要将他们按从矮到高的顺序排列。你可能有多种方式来完成。但是如果其中有一个人特别高，比他身边的人高，在队伍中特别明显，你可以轻易看出那个最高的需要和身边的人交换位置，这是冒泡排序的核心原理。

案例

假如上面6个人的身高分别为176，167，172，178，172，182（单位cm）。

那么交换过程如下：

第 0 次交换：

第 1 次交换：

第 2 次交换：

第 3 次交换：

第 4 次交换：

这样这 6 个人就有序了。

定义

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

一趟只能保证一个元素有序，这可以从代码中看出，一次保证未排序的数列中最大值有序，例如案例中第一趟只能保证 182 有序，第二趟只能保证 178 有序。

冒泡排序是一种稳定的排序算法，值相同的元素，相对位置不会发生改变。例如案例中有两个身高172cm的人，一个叫小刚，一个叫小李，排序前后小刚一直在小李的左边。

冒泡排序的改进

有时候数列已经有序，可是冒泡排序还会不断遍历比较，只要某一趟没有交换两个数，说明数列有序，退出循环。

全部代码

#include <iostream>
using namespace std;

void swap(int *num1,int *num2) //交换两个数
{
	int tmp;
	tmp = *num1;
	*num1 = *num2;
	*num2 = tmp;
}

void BubbleSort(int arr[],int len)
{
	for(int i=0;i<len-1;i++) // n个元素，只需要让n-1个元素有序
	{
		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(void) 
{
	int arr[] = {1,3,7,3,6,9};
	int len = sizeof(arr)/sizeof(arr[0]);

	
	BubbleSort(arr,len);
	
	for(int i=0;i<len;i++)
	{
		cout<< arr[i] <<" ";
	}

	return 0;
}

可以自己添加调试代码，看看排序过程，并且理解遍历趟数和交换次数。