交换排序（冒泡排序和快速排序）

交换排序主要是根据记录的关键字的大小，将记录交换来进行排序的。交换排序的特点是：将关键字值较大的记录向序列的后部移动，关键字较小的记录向前移动。这里介绍两种交换排序方法，它们是冒泡排序和快速排序。

一．冒泡排序

将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

1.算法思路

(1)让j取n至2，将r[j].key与r[j-1].key比较，如果r[j].key，则把记录r[j]与r[j-1]交换位置，否则不进行交换。最后是r[2].key与r[1].key对比，关键字较小的记录就换到r[1]的位置上，到此第一趟结束。最小关键字的记录就象最轻的气泡冒到顶部一样换到了文件的前边。

(2)让j取n至3，重复上述的比较对换操作，最终r[2]之中存放的是剩余n-1个记录(r[1]除外)中关键字最小的记录。

(3) 让j取n至i+1，经过一系列对联对比交换之后，r[i]之中是剩余若干记录中关键字最小的记录。

(4) 让j取n至n-1，将r[n].key与r[n-1].key对比，把关键字较小的记录交换到r[n-1]之中。

【例】设有一组关键字序列｛ 55 ， 22 ， 44 ， 11 ， 33 ｝，这里 n=5 ，即有 5 个记录。请将其按由小到大的顺序排序。

2.具体算法

template

  bubblesort(T r[],int n)

   { int t=1,tag,j;T x;

     do{ tag=0;

         for(j=n;j>=i;j--)

         if(r[j].key

         r[j-1]=x;tag=1;

        }

     i++;

   }while(tag==1&&i

 } //bubblesort

3.算法时间复杂度

该算法的时间复杂度为O(n²)。但是，当原始关键字序列已有序时，只进行一趟比较就结束，此时时间复杂度为O(n)。

4.算法的稳定性：

算法是稳定的。

二．快速排序

快速排序由霍尔 (Hoare) 提出，它是一种对冒泡排序的改正。由于其排序速度快，故称快速排序 (quick sort) 。快速排序方法的实质是将一组关键字 [K 1 ,K 2 ,…,K n ] 进行分区交换排序。

1.算法思路

①以第一个关键字 K 1 为控制字，将 [K 1 ,K 2 ,…,K n ] 分成两个子区，使左区所有关键字小于等于 K 1 ，右区所有关键字大于等于 K 1 ，最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。

②将右区首、尾指针 ( 记录的下标号 ) 保存入栈，对左区进行与第①步相类似的处理，又得到它的左子区和右子区，控制字居中。

③重复第①、②步，直到左区处理完毕。然后退栈对一个个右子区进行相类似的处理，直到栈空。

由以上三步可以看出：快速排序算法总框架是进行多趟的分区处理；而对某一特定子区，则应把它看成又是一个待排序的文件，控制字总是取子区中第一个记录的关键字。现在设计一个函数 hoare ，它仅对某一待排序文件进行左、右子区的划分，使控制字居中；再设计一个主体框架函数 quicksort ，在这里多次调用 hoare 函数以实现对整个文件的排序。

快速排序各次划分后的状态变化
[49 38 65 97 76 13 27 49] //初始关键字
[27 38 13] 49 [76 97 65 49] //第1次划分完成之后，对应递归树第2层
[13] 27 [38] 49 [49 65] 76 [97] //对上一层各无序区划分完成后，对应递归树第3层

13 27 38 49 49 [65] 76 97 //对上一层各无序区划分完成后，对应递归树第4层
13 27 38 49 49 65 76 97 //最后的排序结果

2.具体算法：

void qsort(int *a,int l,int r){

     int i=l,j=r;

     int flag=a[l];//记录i记录的数值，这就是与它为标志，排序后能保证这个数左边小于等于它，右边大于等                       于它

    while(i

         //J找到一个比标志小的值并把它放在i下标处

        while(i

        if(i

        //i找到一个比标志小的值并把它放在j下标处

        while(i

        if(i

    }a[i]=flag;//经过上面的步骤之后能保证i=j,这时能确定标志数放在这里

    i--,j++;

    if(l左边递归

    if(j右边递归

}

3.快速排序算法分析

快速排序的非递归算法引用了辅助栈，它的深度为 log2n 。假设每一次分区处理所得的两个子区长度相近，那么可入栈的子区长度分别为：n/21n/22，n/23 ，n/24 , … ，n/2k ，又因为 n/2k=1, 所以 k= log2n 。分母中 2 的指数恰好反映出需要入栈的子区个数，它就是 log2n ，也即栈的深度。在最坏情况下，比如原文件关键字已经有序，每次分区处理仅能得到一个子区。可入的子区个数接近 n, 此时栈的最大深度为 n.

快速排序主体算法时间运算量约 O(log2n) ，划分子区函数运算量约 O(n) ，所以总的时间复杂度为 O(nlog2n) ，它显然优于冒泡排序 O(n2). 可是算法的优势并不是绝对的。试分析，当原文件关键字有序时，快速排序时间复杂度是 O(n2), 这种情况下快速排序不快。而这种情况的冒泡排序是 O(n), 反而很快。在原文件记录关键字无序时的多种排序方法中，快速排序被认为是最好的一种排序方法。

4.算法稳定性：快速排序是不稳定的。