冒泡排序

缘起

邓俊辉 数据结构和算法(C++语言版) 第二章的例子

分析

每趟冒泡记录下最后一次逆序的位置, 则下一次就只需遍历到那个位置即可. 这属于冒泡的优化. 比原先看过的加一个变量flag表示是否已经有序来的实际多了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include "stdafx.h"
#include <iostream>
#include <algorithm>

#define LOCAL
#define N 8

using namespace std;

// a是数组, n是数组元素的个数
void sort(int *a, int n)
{
	int last = n-1, nextlast;
	for (int i = n-1; i&&last; i--) // 思想是大的沉底, last 表示如果已经没变化了, 就表示已经有序了
	{
		nextlast = 0; 
		for (int j = 0; j < last; j++) // 单趟冒泡
		{
			if (a[j]> a[j+1]) // 逆序
			{
				nextlast = j+1; // 更新最后逆序的
				swap(a[j],a[j+1]); // 交换
			}
		}
		last = nextlast; // 下次单趟冒泡就只需要到last为止 
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif

	int a[N];
	for (int i = 0; i < N; i++) scanf("%d", &a[i]);
	sort(a, N);
	for (int i = 0; i < N; i++) cout<< a[i]<< endl;
	return 0;
}

显然，冒泡是稳定的，复杂度是O(n^2), 属于就地算法.