冒泡排序

一、简介

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

冒泡排序是一种稳定的排序；

冒泡排序在最好的情况下，所有都是正序时，只需一次扫描即可完成排序，所以最好的时间复杂度为O(n)；若初始文件是反序的，需要进行 n-1 趟排序。每趟排序要进行 n-i 次关键字的比较(1 ≤ i ≤ n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值，所以，最坏时间复杂度是 O(N^2)。综合的来说，其平均时间复杂度为 O(N^2)。

上一次研究的桶排序有一个非常致命的问题就是在某些情况下，它十分的浪费空间。而冒泡排序则可以很好的解决这个问题。冒泡排序的基本思想是每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。

冒泡排序的核心部分是双重嵌套循环。

冒泡排序的时间复杂度是一个非常高的时间复杂度。冒泡排序虽然解决了桶排序在空间浪费上的问题，但是在算法的执行效率上牺牲了很多。

二、简单实现

/**
*简单的冒泡排序的实现
*/
#include <stdio.h>

void main() {
	int a[100],i,j,t,n;
	scanf("%d",&n); //接收排序数组长度
	for (i = 0; i < n; i++) {
		scanf("%d",&a[i]);// 将待排序数字存入数组当中
	}
	for (i = 0; i < n-1; i++) { //排序n个数字，只需冒泡n-1次
		//除第一次冒泡时，数组中存在已经排序完成的部分
		for (j = 0; j < n-i-1; j++) { 
			if(a[j] < a[j+1]){ //判断是否满足条件，是否交换值
				t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
			}
		}
	}
	for (i = 0; i < n; i++) {
		printf("%d ",a[i]);
	}
}

三、适用场景

根据数据量的大小，其排序所需时间会以平方式的增长，所以仅仅适合数据量小的时候，随着现在硬件价格的下降，在一般场景下一般来说很少用。

四、排序过程

如果有 n 个数进行排序，只需将 n-1 个数归位，也就是说要进行 n-1 次操作。而“每一次”都需要从第 1 位开始进行相邻两个数的比较，将较小的一个数放 在后面，比较完毕后向后挪一位继续比较下面两个相邻数的大小，重复此步骤，直到后一 个尚未归位的数，已经归位的数则无需再进行比较（你想这么做的话也不是不可以。。。）。