考研数据结构 09 排序

一、插入排序

  插入排序的思路：将数据列分成两组，一组是已排序的序列A，另一组是未排序的序列B。遍历B将B中的元素插入到A中，从而使序列有序。

1.1 直接插入排序

  将序列分成两部分，从头到尾遍历序列完成排序。现在我们有：

• 序列L[0, n-1]
• 有序序列A[0, i-1]
• 无序序列B[i, n-1]

算法简述：

1. 选择B的头部，顺序查找找到其在A中插入的位置k
2. 将B插入到L[k]；向后移动L[k, i-1]，到L[k+1, i]。
3. 重复直到遍历完数组

  算法分析：

• 空间效率：复杂度O(1)
• 时间效率：在排序过程中，向A中指向了n-1次插入操作。在最好情况下，只用插入不用移动，时间复杂度为O(n)；在最坏情况下，每次插入都移动i+1次，移动的总次数为：。注意，这里下标i从1开始，数组的1号位置下标为0。在平均情况下，时间复杂度约为n² / 4。因此其时间复杂度为O(n²)。
• 稳定性：因为是从后向前比较（或是反之），所以不用担心相同元素的相对位置发生变化，之间插入排序是一个稳定的排序算法。
• 适用性：顺序表、链表。

1.2 折半插入排序

  和直接插入排序一样，只是查找的过程变为折半查找。

1.3 希尔排序

  算法描述：

0. 初始化 di = n / 2;
1. 选取步长d_i，将序列分成间隔d_i的n/d_i组;
2. 在组内进行插入排序;
3. 令d_i+1 = d_i / 2;
4. 重复(1, 4)步直到di == 1;

  算法分析：

• 空间效率：复杂度O(1)。
• 时间效率：平均情况下为O(n^1.3)，最坏情况下为O(n²)
• 稳定性：分组的原因可能会改变相同元素的相对位置，其是不稳定的排序方法。
• 适用性：顺序表。

二、交换排序

2.1 冒泡排序

  大部分人学习的第一个排序方法，按照排序准则将“最大/小”的元素放入序列的首部或末尾。

void BubbleSort(std::vector<ElementType>& Seq)
{
    // i表示第i次排序，此时针对第i个元素，比较它和序列中剩下元素的大小，选出最小的放入第i个位置（交换ij的位置）
    for (int i = 0; i < Seq.size(); ++i)
    {
        // 用于判断本次(i)是否发生了交换
        bool flag { false };
        for (int j = i; j < Seq.size(); ++j)
        {
            // 这里使用 < 作为排序准则
            if (Seq[i] < Seq[j])
            {
                swap(Seq[i], Seq[j]);
                flag = true;
            }
        }

        // 如果没有发生交换，则说明序列已经有序
        if (!flag)   return;
    }

    return;
}

  算法分析：

• 空间效率：swap需要使用一个中间变量，复杂度O(1)。
• 时间效率：当序列有序时，比较n-1次、移动0次，从而最好情况下的时间复杂度为O(n)；当序列逆序时，比较：Sigma_i=1^n-1(n-i) = n(n-1) / 2、移动Sigma_i=1^n-13(n-i) = 3n(n-1) / 2，从而最坏情况下时间复杂度为O(n²)。
• 稳定性：不改变相同元素的相对位置，是稳定的排序方法。

2.2 快速排序

  下面我们通过一个实例来说明，考虑序列：49、38、65、97、76、13、27、49。这里使用“<”作为排序准则。

图1：快排实例[/caption]

void QuickSort(std::vector<ElemType>& seq, int head, int tail)
{
    if (head < tail)    // 递归跳出条件
    {
        // 划分序列
        int pos = Partition(seq, head, tail);

        // 子序列快排
        QuickSort(seq, head, pos - 1);
        QuickSort(seq, pos + 1, tail);
    }
}

// 序列分组
int Partition(std::vector<ElemType>& seq, int head, int tail)
{
    OP op;
    while (head < tail)
    {
        // 移动尾部指针，意图找到!(*head op *tail)
        while (head < tail && op(seq[head], seq[tail])) --tail;
        swap(seq[head], seq[tail]);
        // 移动首部指针，意图找到!(*head op *tail)
        while (head < tail && op(seq[head], seq[tail])) ++head;
        swap(seq[head], seq[tail]);
    }
    return head;
}

// 排序准则，这里使用<=
class OP
{
public:
    bool operator()(ElemType A, ElemType B)
    {
        return A <= B;
    }
}

  算法分析：

• 空间效率：递归需要借助一个工作栈完成，其容量与递归深度一致，最好情况下为O(log₂n)，最坏情况下为O(n-1)，平均为O(log₂n)。
• 时间效率：O(n²)。
• 稳定性：子序列以及排序准则（<或<=一类）的选择，其不稳定。

三、选择排序

3.1 简单选择排序

  算法描述：

// 这里使用升序排序
void SelectSort(std::vector<ElemType> seq)
{
    for (int i = 0; i < seq.size(); ++i)
    {
        // 选取最小元素的*位置*
        ElemType minElePos = i;

        for (int j = i + 1; j < seq.size(); ++j)
        {
            minElePos = (i < j) ?
                        i:
                        j;
        }

        if (minElePos != i) swap(seq[i], seq[minElePos]);
    }
}

  算法分析：

• 空间效率：swap消耗1个单位的中间变量，O(1)。
• 时间效率：O(n²)。
• 稳定性：不稳定。

3.2 堆排序

  一个看着好像强无敌的排序方法，实际上没有那么强无敌，可能直接建立avl的效率更高。下面我们来看一下什么是堆、大根堆、小根堆。

图2：大根堆[/caption]

  在上图中，L(i) >= max(L(2i), L(2i+1))，其是一个大根堆，也可以将该数组视为一个完全二叉树。大根堆的最大元素存放在堆顶，其任意非根节点的值小于其父节点。
  堆排序的简单思路：

1. 构造大根堆、小根堆
2. 遍历，调整最大、最小元素到堆顶
3. 移除堆顶元素，将最末元素移动到堆顶
4. 重复直到堆中只有一个元素

  下面我们通过一个实例来演示：

图3：堆排序[/caption]

/* ===== 重复构造大根堆 ===== */
void BuildMaxHeap(std::vector<ElemType>& seq, int len)
{
    // 下标范围[0, len-1]
    for (int i = len / 2; i >= 0; --i)
    {
        HeadAdjust(seq, i, len);
    }
}

/* ===== 节点移动 ===== */
void HeadAdjust(std::vector<ElemType>& seq, int rootK, int len)
{
    // 对以rootK为根节点的子树进行调整
    ElemType elemRootK = seq[rootK];

    // 下标范围[0, len-1]
    for (i = 2 * rootK; i < len; i *= 2)
    {
        // 选取更大的子节点，i或i+1
        if (i < len && seq[i] < seq[i+1]) i++;

        // 已经满足大根堆，跳出
        if (elemRootK > seq[i])
        {
            break;
        }
        else
        {
            // 将i的值交给rootK，继续查看i的子树是否需要调整
            seq[rootK] = seq[i];
            rootK = i;
        }
    }

    seq[rootK] = elemRootK;
}

/* ===== 堆排序 ===== */
void HeapSort(std::vector<ElemType>& seq)
{
    BuildMaxHeap(seq, seq.size());
    for (i = seq.size(); i > 0; --i)
    {
        // 移出堆顶seq[0]到堆底
        swap(seq[i], seq[0]);

        // 调整剩余的元素
        HeadAdjust[seq, 0, i-1];
    }
}

  算法分析：

• 空间效率：O(1)。
• 时间效率：O(nlog₂n)。
• 稳定性：不稳定。

四、并归排序和基数排序

4.1 并归排序

  将数组分为n个列表，通过不断合并列表来实现排序，下面我们通过一个列子来演示：

/*
    有序合并seq[low, mid-1]和seq[mid, high-1]
*/
void Merge(std::vector<ElemType>& seq, int low, int mid, int high)
{
    // 用于存放seqLow和seqHigh的合并结果，最后写回到seq中
    std::vector<ElemType> temp {seq};

    for (int i{ low }, j{ high }, k{ 0 }
        i < mid && j < high;
        ++k;)
    {
        seq[k] = (temp[i] < temp[j]) ?
                    temp[i++]:
                    temp[j++];
    }

    // 若seqL（tempL）未检测完，则全部拷贝入seq
    while (i < mid) seq[k++] = temp[i++];
    // 若seqH（tempH）未检测完，则全部拷贝入seq
    while (j < high) seq[k++] = temp[j++];
}

void MergeSort((std::vector<ElemType>& seq, int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2;
        // 递归排序左子列
        MergeSort(seq, low, mid);
        // 递归排序右子列
        MergeSort(seq, mid+1, high);
        //合并
        Merge(seq, low, high);
    }
}

  算法分析：

• 空间效率：O(n)。
• 时间效率：O(nlog₂n)。
• 稳定性：稳定。

4.2 基数排序

  看名字说得很抽象，下面我们来看一个实例：

图4：基数排序[/caption]

  算法分析：

• 空间效率：O(r)，r个队列的头、尾指针。
• 时间效率：O(d(n+r))，即d次分配+收集，每次分配构造使用n的时间，收回使用r的时间。
• 稳定性：稳定。