考研数据结构 09 排序

发布于 2021-12-01  12 次阅读


一、插入排序

  插入排序的思路:将数据列分成两组,一组是已排序的序列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。在平均情况下,时间复杂度约为n2 / 4。因此其时间复杂度为O(n2)。
  • 稳定性:因为是从后向前比较(或是反之),所以不用担心相同元素的相对位置发生变化,之间插入排序是一个稳定的排序算法。
  • 适用性:顺序表、链表。

1.2 折半插入排序

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

1.3 希尔排序

  算法描述:

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

  算法分析:

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

二、交换排序

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);当序列逆序时,比较:Sigmai=1n-1(n-i) = n(n-1) / 2、移动Sigmai=1n-13(n-i) = 3n(n-1) / 2,从而最坏情况下时间复杂度为O(n2)。
  • 稳定性:不改变相同元素的相对位置,是稳定的排序方法。

2.2 快速排序

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

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(log2n),最坏情况下为O(n-1),平均为O(log2n)。
  • 时间效率:O(n2)。
  • 稳定性:子序列以及排序准则(<或<=一类)的选择,其不稳定。

三、选择排序

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(n2)。
  • 稳定性:不稳定。

3.2 堆排序

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

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

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

  下面我们通过一个实例来演示:
图3

/* ===== 重复构造大根堆 ===== */
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(nlog2n)。
  • 稳定性:不稳定。

四、并归排序和基数排序

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(nlog2n)。
  • 稳定性:稳定。

4.2 基数排序

  看名字说得很抽象,下面我们来看一个实例:
图4

  算法分析:

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