算法—冒泡排序

1.基本思想

两个数比较大小，较大的数下沉，较小的数冒起来。

2.过程

·每次比较相邻的两个数，如果第二个数小，就交换位置。（升序或降序）

·然后两两比较，一直到比较最后的数据。最终最小（大）数被交换到开始（结束）位置，这样第一个最小（大）数的位置就排好了。

·继续重复上述过程，依次将第2,3…n-1个最小数排好位置。

动图过程：

举例说明：【1 4 3 2】

第一趟排序：

第一次排序：1和4比较，1小于4，不交换位置。 【1 4 3 2】

第二次排序：4和3比较，4大于3，交换位置。 【1 3 4 2】

第三次排序：4和2比较，4大于2，交换位置。 【1 3 2 4】

第二趟排序：

第一次排序：1和3比较，1小于3，不交换位置。 【1 3 2 4】

第二次排序：3和2比较，3大于2，交换位置。 【1 2 3 4】

第三次排序： 3和4比较，3小于4，不交换位置。 【1 2 3 4】

第三趟排序：

第一次排序，1和2比较，1小于2，不交换位置。 【1 2 3 4】

第二次排序，2和3比较，2小于3，不交换位置。 【1 2 3 4】

第三次排序，3和4比较，3小于4，不交换位置。 【1 2 3 4】

---

2.注意点

---

在冒泡排序中，两个数比较大小，只需要比较一次就行。

n个数比较大小（选出最大或者最小），比较n-1次就行。

---

3.参考代码

#include<iostream>
using namespace std;
int main()
{
	 int arr[]={12,45,13,88,79,11,52}; //定义数组
	 int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度 
	 int length = len-1; //排序总轮数() 
	 for(int i=0;i<length;i++)
	 {
	 	for(int j=0;j<length-i;j++)
	 	{
			if (arr[j]>arr[j+1])  //如果前一个数比后一个大 
			{
				int temp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] =temp; 
			} 
	    }
	    /*
		for(int i=0;i<length;i++)
	 		cout<<arr[i]<<" "; 
	 	cout<<endl;
		*/
	 }
	 //输出
	 for(int i=0;i<length;i++)
	 	cout<<arr[i]<<" "; 
	 return 0; 
}

4.问题及改进

由程序输出可以看出，在第5次的时候已经排序完了，后面的元素都没有交换过，也就说后面几次排序都是没有意义的。这样就可以改进一下排序算法，设置一个元素位置交换标志记录本次排序是否有位置发生变化，如果没有则认为已经排序完了，不需要再执行了。

#include<iostream>
using namespace std;
int main() {
	int arr[]= {12,45,13,88,79,11,52,66}; //定义数组
	int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度
	int length = len-1; //排序总轮数
	bool flag = true; //标志位，记录每次排序是否有元素位置交换
	for(int i=0; i<length && flag!=false; i++) { //如果上次排序元素位置未改变过，
		flag = false; //每次排序前，标志位复位
		for(int j=0; j<length-i; j++) {
			if (arr[j]>arr[j+1]) { //如果前一个数比后一个大
				flag = true; //发生位置交换，改变标志位
				int temp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] =temp;
			}
		}
		 /*
		for(int i=0;i<length;i++)
	 		cout<<arr[i]<<" "; 
	 	cout<<endl;
		*/
	}
	
	//输出
	 for(int i=0;i<length;i++)
	 	cout<<arr[i]<<" "; 
	return 0;
}

---

返回目录：算法

---