数据结构之交换排序

冒泡排序

基本思想:
冒泡排序是一种简单的排序算法，其核心思想是通过两两比较相邻元素的大小来进行排序。具体过程如下：

从序列的前面开始，逐对比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。
经过一趟比较后，最大的元素会被移动到序列的末尾（或最小的元素被移动到开头）。
重复这一过程，直到所有元素都有序。

排序过程:

每次通过比较和交换，将最大的元素“沉”到序列的末尾，或将最小的元素“浮”到序列的开头。
每次排序后，已排序的元素不再参与后续的比较，最多进行 $n-1$ 轮排序，最终得到有序序列。

示例:
假设序列为 $27, 49, 13, 76, 65, 38, 49, 97$，经过冒泡排序的过程如下：

第一趟冒泡:
- 比较并交换过程：
  - $27 < 49$（不交换）
  - $13 < 27$（不交换）
  - $76 > 13$（交换）→ $27, 49, 13, 65, 76, 38, 49, 97$
  - 继续此过程，直到最小的元素在第一位。
第二趟冒泡:
- 对剩余子序列进行同样的排序。
最后结果:
- 如果经过一轮排序后没有发生交换，说明序列已经有序，冒泡排序结束。

冒泡排序算法的代码示例

void BubbleSort(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) return;  // 本趟遍历后没有发生交换，说明表已经有序
    }
}

性能分析

空间复杂度:
仅使用常数个辅助单元，因此空间复杂度为 $O(1)$。
时间复杂度:
- 最好情况: 当初始序列有序时，第一趟冒泡后 flag 依然为 false，直接跳出循环，比较次数为 $n - 1$，移动次数为 0。此时的时间复杂度为 $O(n)$。
- 最坏情况: 当初始序列为逆序时，需要进行 $n-1$ 趟排序，第 $i$ 趟排序要进行 $n-i$ 次关键字的比较。每次比较后都必须移动元素3次来交换元素位置。因此，最坏情况下的时间复杂度为 $O(n^2)$。
1. 比较次数

在每一趟冒泡中，都会对相邻的元素进行比较。具体的比较次数可以通过分析每一趟的比较来计算：
- 第 $i$ 趟 (其中 $i$ 从 $0$ 到 $n-2$) 的比较次数为 $n - 1 - i$。
  - 这意味着在第一趟（$i=0$）中比较了 $n-1$ 次；
  - 在第二趟（$i=1$）中比较了 $n-2$ 次；
  - 依此类推，在最后一趟（$i=n-2$）中只比较了 1 次。
因此，总的比较次数可以表示为：

$ = (n - 1) + (n - 2) + + 1 $

这个和是一个等差数列的和，可以通过以下公式计算：

$ = $

因此，最坏情况下的比较次数为 $O(n^2)$。

2. 移动次数

在每一次的比较中，如果发现需要交换（即两个元素的顺序是逆序），就会进行一次交换操作。在冒泡排序中，每次交换通常涉及两个元素的位置互换，因此在最坏情况下，我们需要考虑的移动次数是 3 倍的交换次数：
- 第 $i$ 趟 冒泡的交换次数在最坏情况下（即原序列完全逆序）为 $n - 1 - i$ 次。每次交换需要移动 3 次（例如，临时存储、写回两个元素），所以可以表示为：
$ = 3 $

因此总的移动次数为：

$ = 3 ((n - 1) + (n - 2) + + 1) = 3 $

这一部分在最坏情况下同样是 $O(n^2)$，因为即使每次都需要交换，还是和比较次数是相同的。
- 平均情况: 也是 $O(n^2)$。
稳定性:
冒泡排序是一种稳定的排序方法，因为在比较相等元素时不会交换它们的位置。

特点

冒泡排序所产生的有序子序列一定是全局有序的，即有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字。每趟排序都会将一个元素放置到其最终位置。

快速排序

快速排序是一种高效的排序算法，其核心思想是采用分治法。

1. 快速排序的基本思想

快速排序通过选择一个元素作为枢轴（pivot），将待排序数组分成两个部分，使得左边部分的所有元素小于枢轴，右边部分的所有元素大于等于枢轴。通过这样的划分，枢轴元素将处于其最终位置上。然后递归地对这两个部分继续进行快速排序，直到每个部分只包含一个元素或为空为止。

2. 一趟快速排序的过程

假设我们有一个待排序的数组，我们从数组中选择第一个元素作为枢轴。以下是详细的过程：

初始化指针：
- 指针 i 从 low 开始，指向当前待排序数组的开始位置。
- 指针 j 从 high 开始，指向当前待排序数组的结束位置。
选择枢轴：
- 将第一个元素 A[low] 作为枢轴 pivot。
指针搜索与交换：
- 指针 j 从后向前查找，直到找到一个小于 pivot 的元素，将该元素与指针 i 所指的元素交换。
- 指针 i 从前向后查找，直到找到一个大于枢轴的元素，将该元素与指针 j 所指的元素交换。
- 重复上述步骤，直到 i 和 j 相遇。此时，i 或 j 指向的元素就是枢轴应放置的位置。
放置枢轴：
- 将枢轴放入指针 i 或 j 指向的位置，完成一趟排序。

3. 划分算法（Partition）

划分操作是快速排序的核心，下面是一个具体的划分函数实现示例：

int Partition(ElemType A[], int low, int high) {
    ElemType pivot = A[low];  // 将当前表中第一个元素设为枢轴
    while (low < high) {
        // 从后往前找，找到第一个小于 pivot 的元素
        while (low < high && A[high] >= pivot) 
            --high;
        A[low] = A[high];  // 交换

        // 从前往后找，找到第一个大于 pivot 的元素
        while (low < high && A[low] <= pivot) 
            ++low;
        A[high] = A[low];  // 交换
    }
    A[low] = pivot;  // 将 pivot 放入最终位置
    return low;      // 返回枢轴元素最终位置
}

4. 快速排序的递归实现

快速排序的递归实现结构如下：

void QuickSort(ElemType A[], int low, int high) {
    if (low < high) {  // 递归跳出的条件
        int pivotpos = Partition(A, low, high);  // 划分
        QuickSort(A, low, pivotpos - 1);         // 对左子数组递归排序
        QuickSort(A, pivotpos + 1, high);        // 对右子数组递归排序
    }
}

5. 性能分析

时间复杂度

最佳情况：若每次划分都能将数组分成相等的两部分，时间复杂度为 $O(n \log n)$。
平均情况：同样是 $O(n \log n)$，快速排序的平均性能是非常优秀的。
最坏情况：当数组基本有序或逆序时，划分极其不平衡，时间复杂度为 $O(n^2)$。例如，始终选择第一个元素作为枢轴，在已排序数组中会导致每次只划分出一个元素。

空间复杂度

快速排序使用递归，因此需要额外的栈空间来保存递归状态：

最佳情况：空间复杂度为 $O(\log n)$，因为递归深度较小。
最坏情况：空间复杂度为 $O(n)$，当每次划分只剩下一个元素时。

6. 稳定性

快速排序是不稳定的排序算法。在划分过程中，相同值的元素可能会被交换，导致它们的相对顺序发生变化。例如，在序列 {3, 2, 2} 中经过划分后可能变成 {2, 2, 3}，因此相同元素之间的顺序可能被改变。

7. 优化方法

为了提高快速排序的效率，可以采用以下优化策略：

选择合适的枢轴：可以随机选择枢轴或使用三数取中法（选择头、尾和中间元素的中位数作为枢轴）来减少最坏情况的发生。
小数组的优化：对于小规模数组，可以使用插入排序等简单排序算法代替快速排序，以提高性能。