交换排序

下述算法实现中使用到的temp()函数：

void temp(int &a,int &b){
    int t = a;
    a = b;
    b = t;
}

冒泡排序

void bubbleSort(int arr[],int n){
    //采用冒泡排序的方法对数组arr中的 n 个元素排序
    int x;
    int i,j,flag;
    for(i=1;i<n-1;i++){ // i 表示趟数，最多进行 n-1 趟
        flag = 0;   // flag 表示每一趟是否有交换
        for(j=n-1;j>=i;j--) //进行第 i 趟排序
            if(arr[j]<arr[j-1]){
                temp(arr[j],arr[j-1]);
                flag = 1;   //置 1 表示有交换
            }
        if(flag==0)return;  //进行一趟后若无交换则排序完成返回
    }
}

算法效率

【最好情况】待排序元素为正序，则只需进行一趟排序，元素的比较次数为 $n - 1$ ，其算法的时间复杂度为 $O (n)$ 。
【最坏情况】待排序元素逆序，则需进行 $n - 1$ 趟排序，其比较次数为 $\sum_{i=1}^{n-1}(n-i) = \displaystyle{\frac{1}{2}}n(n-1)$ 次，移动次数为 $\sum_{i=1}^{n-1}3(n-i) = \displaystyle{\frac{3}{2}}n(n-1)$ 次，因为每次交换需要移动三次记录，其时间复杂度为 $O (n^{2})$ 。
【一般情况】在平均情况下，比较和移动记录的总次数大约为最坏情况下的一半，其时间复杂度为 $O (n^{2})$

快速排序

void quickSort(int arr[],int s,int t){
    //采用快速排序方法对数组arr中arr[s]至arr[t]区间进行排序
    //开始进行非递归调用时 s 和 t的初值应分别为 0 和 n-1
    //对当前排序区间进行一次划分
    int i=s+1,j=t;  //给 i 和 j 赋初值
    int x = arr[s]; //把基准元素的值暂存在 x 中
    while(i<=j){
        while(arr[i]<=x && i<=j) i++;   //从前向后顺序比较
        while(arr[j]>=x && j>=i) j--;   //从后向前顺序比较
        if(i<j){
            temp(arr[i],arr[j]);    //当条件成立时交换arr[i]和arr[j]的值
            i++; j--;
        }
    }
    //交换arr[s]和arr[j]的值，得到前后两个子区间arr[s]~arr[j-1]和arr[j+1]~arr[t]
    if(s!=j){arr[s]=arr[j];arr[j]=x;}
    //在当前左区间内超过一个元素的情况下递归处理左区间
    if(s<j-1)quickSort(arr,s,j-1);
    //在当前右区间内超过一个元素的情况下递归处理右区间
    if(j+1<t)quickSort(arr,j+1,t);
}

算法效率

【最好情况】在快速排序过程中得到的是一颗理想的平衡树的情况下，其算法的时间复杂度为 $O (n l b n)$ 。
【一般情况】由快速排序得到的是一颗随机的搜索二叉树，其算法的时间复杂度仍为 $O (n l b n)$ ，并且系数比其他同数量级的排序方法要小。
【最坏情况】得到的搜索二叉树为一颗单支树，如待排序区间上的记录为正序或者逆序时，总的比较次数为 $\sum_{i=1}^{n-1}(n-i+1) = \displaystyle{\frac{1}{2}}(n^2+n-2)$ ，即时间复杂度为 $(n^{2})$ 。另外，这种情况下需要递归处理 $n - 1$ 次，所以空间复杂度为 $O (n)$ 。
【避免最坏情况发生的方法】

事先知道记录基本有序，采用其他排序方法。
在每次划分前比较当前区间的第一个元素、最后一个元素和中间一个元素的排序码，取排序码居中的一个元素作为基准元素并调换到第一个元素的位置。

题目

alt

答案	快速排序二叉树
A