交换排序

交换排序的思想

基于两个关键字的比较结果来交换元素的位置。

相关算法

冒泡排序

从前到后扫描n次，交换逆序对。
每一趟都能找到一个最大（或最小）的元素，并使其到达最终位置。

空间复杂度：，时间复杂度：，排序是稳定的（因为关键字相同的元素不构成逆序对，不会发生交换。）。

快速排序

找一个元素作为基准，将序列分为两个部分，然后递归地进行划分。

空间复杂度：，时间复杂度：
不稳定的，因为存在两个元素交换位置。

注：

• 快速排序会保证每一次排序后基准位置的元素都位于最终位置上；
• 是一种平均性能最优的算法

一次划分的算法实现（升序排列）：

1. 设置两个指针，分别从两端向中间进行扫描
2. 最开始将 pivot 元素挖走（假设取最左边的元素），然后从右边开始扫描
3. 当找到比 pivot 更小的元素时，就将这个元素填充在空缺处，然后继续从左边扫描
4. 当找到比 pivot 更大的元素时，就将这个元素填充在空缺处，然后继续从右边扫描
5. 重复上述 3，4 两个步骤

int Partition(int A[], int low, int high) {
    int 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;
}