交换排序

冒泡排序

算法思想

从后往前(或从前往后)两两比较相邻元素的值，若为逆序(即A[i - 1] > A[i]),则交换他们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序的第一个位置(或将最大的元素交换到待排序序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不在参与比较，每趟冒泡的结果是把序列中最小元素或(最大元素)放到序列的最终位置…….这样最多做n - 1趟冒泡就能把所有元素排好序。

模板代码

void BubbleSore(ElemType A[],int n){
    for(int i = 0;i < n - 1;i ++){
        bool flag = false;                  //表示本趟冒泡是否发生交换的标志
        for(int j = n - 1;j > i;j --)       //一趟冒泡过程
            if(A[j - 1] > A[j]){            //若为逆序
                swap(A[j - 1],A[j]);        //交换    
                flag = true;
            }
        if(flag == false)
            return ;                        //本趟遍历后没有发生交换，说明表已经有序
    }
}

性能分析

1. 空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)。
2. 时间效率：最坏情况下的时间复杂度为O(n²),平均时间复杂度为O(n²)。
3. 稳定性： 由于i > j 且 A[i] = A[j] 时，不会发生交换，因此冒泡排序是一种稳定的排序方法。
4. 注意：冒泡排序中所产生的有序子序列一定是全局有序的(不同于直接插入排序)，也就是说，有序子序列中的所有元素的关键字一定小于(或大于)无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。

快速排序

算法思想

快速排序的基本思想是基于分治法的：在待排序表L[1…n]中任取一个元素pivot作为数轴(或称基准，通常取首元素)，通过一趟排序将待排序表划分成为独立的两部分L[1…K-1]和L[k+1…n],使得L[1…k-1]中所有元素小于pivot,L[k+1…n]中所有元素大于或等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次划分。然后分别递归地对两个子表重复上述过程，直至每部分内中只有一个元素或空为止，即所有元素放在了其最终位置上。

void QuickSort(ElemType A[],int low,int high){
    if(low < high>){                                //递归跳出的条件
    // Partition()就是划分操作将表A[low...high]划分为满足上述条件的两个子表
        int pivotpos = Partition(A,low,high);       //划分    
        QuickSort(A,low,pivotpos - 1);              //依次对两个子表进行递归排序
        QuickSort(A,pivotpos + 1,high);
    }
}

int Partition(ElemType A[],int low,int high){       //一趟划分
    ElemType pivot = A[low];                        //将当前表中第一个元素设为枢轴，对表进行划分
    while(low < high){                              //循环跳出条件
        while(low < high && A[high] >= pivot) -- high;
        A[low] = A[high];                           //将比枢轴小的元素移动到左端
        while(low < high && A[low] <= pivot) ++ low;
        A[high] = A[low];                           //将比枢轴大的元素移动到右端
    }
    A[low] = pivot;                                 //枢轴元素存放到最终位置
    return low;                                     //返回存放枢轴的最终位置
}

性能分析

1. 空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量与递归调用的最大深度一致。最好情况下为O(log₂ⁿ);最坏情况下，因为要进行n - 1次递归调用，所以栈的深度为O(n);平均情况下，栈的深度为O(log₂ⁿ)。
2. 时间效率：快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含n - 1个元素和0个元素时，这种最大限度的不对称若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为O(log₂ⁿ)。
   在理想状态下，即Partition()可能做到最平衡的划分，得到的两个子问题的大小都不可能大于n/2，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为O(nlog₂ⁿ)。
   ※快速排序是所有内部排序算法中平均性能最优的排序算法。
3. 稳定性：在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。
4. 最小递归次数 log₂ⁿ + 1 次
   最大递归次数 n
   时间复杂度 = O(n * 递归层数)———— 最好—->nlog₂ⁿ 最坏—->n².

习题总结

1. 冒泡排序始终在调整“逆序”，因此交换次数为排列中逆序的个数。
2. 当待排序数据为基本有序时，每次选取第n个元素为基准，会导致划分区间分配不均匀，不利于发挥快速排序算法的优势。相反，当待排序数据分布比较随机时，基准元素能将序列划分为两个长度大致相等的序列，这时才能发挥快速排序的优势
3. 快速排序过程构成一个递归树，递归的深度即递归树的高度。枢轴值每次都将子表等分时，递归树的高度为log₂ⁿ；枢轴值每次都是子表的最大值或最小值时，递归树退化为单链表，树高为n。
4. 采用递归方式对顺序表进行快速排序，递归的次数与个元素的初始排列有关。若每次划分后分区比较平衡，则递归次数少；若分区不平衡，递归次数多。递归次数与处理顺序是没有关系的。
5. 快速排序空间复杂度只在最坏情况下才会达到O(n),平均情况下为O(log₂ⁿ)