冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访要排序的序列，一次比较两个相邻元素，如果它们的顺序错误就把它们交换过来。重复执行走访序列的过程，直到没有再需要交换的元素，这样序列就完成了排序。排序过程中，越小的元素经由交换后会慢慢“浮”到序列的顶端，冒泡排序这一算法名字也由此而来。

由上面展示冒泡排序过程的动图可知，冒泡排序的基本操作是将序列两两相邻的元素依次比较，如果发现顺序不对则交换。冒泡排序是将序列后面部分变得有序，并且将有序的区间逐步扩大直到整个序列有序。正因为在排序过程中后面部分是有序的，所以每次冒泡的过程中只需要将序列前面无序部分的元素两两比较并考虑是否交换。

对于 \(n\) 个元素的序列，经过 \(n-1\) 次冒泡排序，序列的后 \(n-1\) 个元素已经有序了，那么整个序列也就有序了。所以 \(n\) 个元素的序列只需要 \(n-1\) 趟冒泡排序即可：

//冒泡排序：对数组的r[0]~r[n-1]区域排序（升序排序）
void BubbleSort(int r[],int n){
	//一共n-1次冒泡过程 
	for(int i=0;i<n-1;i++){
		//依次比较r[0]和r[1]、r[1]和r[2]、… 、r[n-i-2]和r[n-i-1]
		for(int j=0;j<n-i-1;j++){
			if(r[j+1]<r[j]){     //顺序不对则交换
				int t = r[j];r[j] = r[j+1];r[j+1] = t;
			}
		}
	}
}
//调用方法举例：BubbleSort(a,10);
//调用方法举例：BubbleSort(a,n);

其实在某一次冒泡的过程中，如果没有发生任何交换，那么序列肯定已经有序了，不需要再进行后续的冒泡环节，可以进一步改进算法提高效率：

//冒泡排序：对数组的r[0]~r[n-1]区域排序（升序排序）
void BubbleSort(int r[],int n){
	//一共n-1次冒泡过程 
	for(int i=0;i<n-1;i++){
		bool exchange = false;
		//依次比较r[0]和r[1]、r[1]和r[2]、… 、r[n-i-2]和r[n-i-1]
		for(int j=0;j<n-i-1;j++){
			if(r[j+1]<r[j]){     //顺序不对则交换
				int t = r[j];r[j] = r[j+1];r[j+1] = t;
				exchange = true;
			}
		}
		if(!exchange) break;
	}
}
//调用方法举例：BubbleSort(a,10);
//调用方法举例：BubbleSort(a,n);

仿照 sort 函数的写法，用两个指针作为函数参数来指定排序的区域：

//冒泡排序：对指针begin~end区域排序（升序排序，不包括end）
void BubbleSort(int *begin,int *end){
    //一共 end-begin-1 次冒泡过程 
    for(int i=0;i<end-begin-1;i++){
        bool exchange = false;
        //依次比较 *begin和 *(begin+1)、*(begin+1)和*(begin+2)、… 、*(end-i-2)和*(end-i-1)
        for(int *q=begin;q<end-i-1;q++){
            if(*(q+1) < *q){     //顺序不对则交换
                int t = *q;*q = *(q+1);*(q+1) = t;
                exchange = true;
            }
        }
        if(!exchange) break;
    }
}
//调用方法举例：BubbleSort(a,a+10);
//调用方法举例：BubbleSort(a,a+n);
//调用方法举例：BubbleSort(a+1,a+n+1);

冒泡排序的时间复杂度是 \(O(n^2)\)，因为每次都是相邻的两个数比较和交换，所以冒泡排序是稳定的。