交换排序

冒泡排序

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

冒泡排序算法的代码如下：

void BubbleSort(ElemType A[], int n) {
    int temp;
    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]) {
                temp = A[j - 1];  // 交换
                A[j - 1] = A[j];
                A[j] = temp;
                flag = true;
            }
        }
        if (flag == false) {
            return;  // 本次遍历后没有发生交换，说明表已经有序
        }
    }
}

冒泡排序的性能分析如下：

• 空间效率：仅使用了常数个辅助单元，因而空间复杂度为 #card=math&code=O%281%29&id=YEU4E) 。
• 时间效率：当初始序列有序时，显然第一趟冒泡后 flag 依然为 false （本趟冒泡没有元素交换），从而直接跳出循环，比较次数为 ，移动次数为 0，从而最好情况下的时间复杂度为 #card=math&code=O%28n%29&id=nUsf5) ；当初始序列为逆序时，需要进行 趟排序，第 趟排序要进行 次关键字的比较，而且每次比较后都必须移动元素 3 次来交换元素位置。这种情况下，比较次数= %7D%7B2%7D#card=math&code=%5Cfrac%7Bn%28n-1%29%7D%7B2%7D&id=dP0sm) ，移动次数 = %7D%7B2%7D#card=math&code=%5Cfrac%7B3n%28n-1%29%7D%7B2%7D&id=U15gp) 从而，最坏情况下的时间复杂度为 #card=math&code=O%28n%5E2%29&id=FdDG5) ，其平均时间复杂度也为 #card=math&code=O%28n%5E2%29&id=q7esL) 。
• 稳定性：由于 i>j 且 A[i]=A[j] 时，不会发生交换，因此冒泡排序是一种 稳定的排序方法。

注意：冒泡排序中所产生的有序子序列一定是全局有序的（不同于直接插入排序），也就是说，有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。

快速排序

快速排序的基本思想是基于分治法的：在待排序表 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(int A[], int low, int high) {
    if (low < high) {  //递归跳出的条件
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos - 1);   // 划分左子表
        QuickSort(A, pivotpos + 1, high);  // 划分右子表
    }
}

// 用第一个元素将待排序序列划分成左右两个部分
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;
}

快速排序算法的性能分析如下：

空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。 最好情况下为 #card=math&code=O%28%5Clog%7B2%7D%7Bn%7D%29&id=ph44U) ；最坏情况下，因为要进行 次递归调用，所以栈的深度为 #card=math&code=O%28n%29&id=EFQtQ) ；平均情况下，栈的深度为 #card=math&code=O%28%5Clog_%7B2%7D%7Bn%7D%29&id=DCiMH)。

时间效率：快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含 个元素和 0 个元素时，这种最大程度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为 #card=math&code=O%28n%5E2%29&id=o2SuW)。

有很多方法可以提高算法的效率：一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素；或者随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。

在最理想的状态下，即 Partition() 可能做到最平衡的划分，得到的两个子问题的大小都不可能大于 ，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为 #card=math&code=O%28n%5Clog_%7B2%7D%7Bn%7D%29&id=fh2Zw) 。 好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。

稳定性：在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。

注意：在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴（基准）元素放到其最终的位置上。