交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。
基本思想
1.冒泡排序算法的过程：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
（1）初始
R[1..n]为无序区。
（2）第一趟扫描
从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换R[j+1]和R[j]的内容。
第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。
（3）第二趟扫描
扫描R[2..n]。扫描完毕时，"次轻"的气泡飘浮到R[2]的位置上……
最后，经过n-1 趟扫描可得到有序区R[1..n]
注意：
第i趟扫描时，R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R[i]上，结果是R[1..i]变为新的有序区。
算法排序动画演示
对关键字序列为xx,xx,xx,xx（需要自己输入）进行冒泡排序的过程演示。
【动画演示过程】
算法实现
1.方法一，按照定义实现的C程序
#include <stdio.h>
void bubbleSort(int arr[], int count)
{
int i = count, j;
int temp;
while(i > 0)
{
for(j = 0; j < i - 1; j++)
{
if(arr[j] > arr[j + 1])
{ temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
i--;
}
}
算法性能分析
| 最差时间复杂度 |  |
|---|---|
| 最优时间复杂度 | |
| 平均时间复杂度 | |
| 最差空间复杂度 | 总共，需要辅助空间 |
算法改进的三种方法
1.设置标志的冒泡排序
#include <iostream>
using namespace std;
void bubble_sort(int d[], int size)
{
//#假定两两交换发生在数组最后的两个位置#%
int exchange = size - 1;
while(exchange)
{
//#记录下发生数据交换的位置#%
int bound = exchange;
exchange = 0; //#假定本趟比较没有数据交换#%
for(int i = 0; i < bound; i++)
{
if (d[i] > d[i + 1])
{
//#交换#%
int t = d[i];
d[i] = d[i + 1];
d[i + 1] = t;
exchange = i;
}
}
}
}
2.记住最后一次交换发生位置的lastExchange冒泡排序
在每趟扫描中，记住最后一次交换发生的位置lastExchange，（该位置之前的相邻记录均已有序）。下一趟排序开始时，R[1..lastExchange-1]是有序区，R[lastExchange..n]是无序区。这样，一趟排序可能使当前有序区扩充多个记录，从而减少排序的趟数。程序如下：（from author MoreWindows）
void BubbleSort(int a[], int n)
{
int j, k;
int flag;
flag = n;
while (flag > 0)
{
k = flag;
flag = 0;
for (j = 1; j < k; j++)
if (a[j - 1] > a[j])
{
Swap(a[j - 1], a[j]);
flag = j;
}
}
}
3.冒泡算法的不对称性
（1）能一趟扫描完成排序的情况：
只有最轻的气泡位于R[n]的位置，其余的气泡均已排好序，那么也只需一趟扫描就可以完成排序。
【例】对初始关键字序列12，18，42，44，45，67，94，10就仅需一趟扫描。
需要n-1趟扫描完成排序情况：
当只有最重的气泡位于R[1]的位置，其余的气泡均已排好序时，则仍需做n-1趟扫描才能完成排序。
【例】对初始关键字序列：94，10，12，18，42，44，45，67就需七趟扫描。
（2）造成不对称性的原因
每趟扫描仅能使最重气泡"下沉"一个位置，因此使位于顶端的最重气泡下沉到底部时，需做n-1趟扫描。
（3）改进不对称性的方法
在排序过程中交替改变扫描方向，可改进不对称性。
（4）采用交替扫描改进的冒泡算法实现：
（a）改变扫描方向, 改成从顶往底扫描, 则算法伪码如下 ：
void BubbleSort( SeqList R)
{// R( l11n) 是待排序的文件, 采用自上向下扫描, 对R 做冒泡排序
int i,j;
Boolean exchange; // 交换标志
for( i= n; i< 2; i- - )
{// 最多做n- 1 趟排序
exchange= FALSE; // 本趟排序开始前, 交换标志应为假
for(j= 1;j< = i;j+ + ) // 扫描方向从顶到i
if( R[j+ 1] 1key< R[ j] 1key) { // 交换记录
R[0] = R[j+1]; // R[ 0] 不是哨兵, 仅做暂存单元
R[j+1] = R[j];
R[j] = R[0];
exchange= TRUE; // 发生了交换, 故将交换标志置为真
}
if( ! exchange) // 本趟排序未发生交换, 提前终止算法
return;
}// endfor( 外循环)
}// BubbleSort
这样,R[ 1,i] 是无序区, R[ i+ 1,n] 是有序区。
（b）交替改变扫描方向
在排序过程中交替改变扫描方向, 即每趟扫描方向都进行改变, 就可以改变排序的不对称问题。如第一趟是从底向上, 第二趟是从上向底的交替冒泡排序算法伪码如下：
void BubbleSort( SeqList R)
{// R( l11n) 是待排序的文件, 采用先下向上扫描, 再从上向下的交替扫描, 对R 做冒泡排序
int i,j, k; // j 控制趟内扫描过程
Boolean exchange; // 交换标志
i= 1; k= n; // i: 每趟扫描的起始位置; k: 每趟扫描的结束位置即无序区R[ i ,k]
while( i< k) {
exchange= FALSE; // 本趟排序开始前, 交换标志应为假
for(j= k- 1; j> = i; j- - ) // 对当前无序区R[ i11k] 自下向上扫描
if( R[ j+ 1] 1key< R[j] 1key) {/ / 交换记录
R[ 0] = R[ j+ 1] ; // R[ 0] 不是哨兵, 仅做暂存单元
R[j+ 1] = R[j] ;
R[j] = R[ 0] ;
exchange= TRUE; // 发生了交换, 故将交换标志置为真
}
if( ! exchange) return; // 本趟排序未发生交换, 提前终止算法
for(j= i;j< = k- 1; j+ + ) // 对当前无序区R[ i11k] 自上向下扫描
if( R[j+ 1] 1key< R[ j] 1key) { // 交换记录
R[ 0] = R[ j+ 1] ; // R[ 0] 不是哨兵, 仅做暂存单元
R[j+ 1] = R[j] ;
R[j] = R[ 0] ;
exchange= TRUE; // 发生了交换, 故将交换标志置为真
}
if( ! exchange) return; // 本趟排序未发生交换, 提前终止算法
}// endfor( 外循环)
}/ BubbleSort
参考文献：采用交替扫描改进冒泡排序的不对称性（Improving the Asymmetry of Bubble Sort using Alternate Scanning）。
