---恢复内容开始---
冒泡排序：
一般冒泡排序我们都很容易想到以下的方法，但事实上冒泡排序还有一些地方可以改进。最主要的方法是引入标志位。
void print(int *p, int length) {
for (int i = 0; i < length; i++) {
cout << p[i] << ",";
}
}
void BubbleSort(int *p, int length) {
for (int i = 0; i < length; i++) {
for (int j = 0 ; j < length-i-1; j++) {
if (p[j]>p[j+1]) {
swap(p[j], p[j+1]);
}
}
}
print(p,length)
}
int main()
{
int arr[7] = {2,4,5,1,7,3,6};
int length = sizeof(arr) / sizeof(int);
BubbleSort(arr,length);
return 0;
}
（最后一行是输出的结果）
改进方案一
看到上面运行结果，第4,5,6,7趟都是没有发生逆序对的互换，但算法还是依旧进行了比较。
为此，引入一个排序标志。
void BubbleSort(int *p, int length) {
for (int i = 0; i < length; i++) {
bool sorted = true;
for (int j = 0 ; j < length-i-1; j++) {
if (p[j]>p[j+1]) {
swap(p[j], p[j+1]);
sorted = false; //如果有逆序对，说明还没有排好序
}
}
if (sorted) { //没有逆序对，说明已经排好序了，可以直接输出。
break;
}
}
print(p,length);
}
（最后一行是输出的结果）
由此可见，到第4趟发现没有逆序对了，就会停止。
假设这段有序的区间是[0,n1/2)，那么按照这个算法算出来的复杂度就是 O(n2/3) ，即 n*n1/2
改进方案二（比方案一更优化）
由方案一我们得到启发，如果我们能够对已经排好序的部分不再去比较的话，那么性能会更好。例如
假设int arr[12] = {2,4,5,1,7,3,6,8,9,10,11,12};
如果我们得到6的位置的话，那么6之后的我们就不去比较了。
那6这个位置怎么得到呢？
我们可以设置一个变量，记录最后一次逆序对发生变化的位置。得到的就是排好序的部分里面排在最前的位置，也就是6的位置。
void BubbleSort(int *p, int length) {
int pos_temp = length - 1;
for (int i = 0; i < length; i++) {
int pos = pos_temp;
for (int j = 0 ; j < pos; j++) {
if (p[j]>p[j+1]) {
swap(p[j], p[j+1]);
pos_temp = j;//记录最后一次逆序对发生变化的位置
}
}
if (pos== pos_temp) {//如果没变过，说明没有逆序对了，可以直接输出
break;
}
}
print(p,length);
}
如上图，进行过一趟比较之后，我们就记录好了6的位置，也就是第6位。那么此后我们就不管6之后的数据了。
原文：http://www.cnblogs.com/yuqinweb/p/6665046.html