数据结构和算法笔记 (2) —— 排序算法

发表于 更新于 分类于 阅读次数：

常用排序算法的总结和 C++ 实现。

冒泡排序 (Bubble Sort)

原理

在一次冒泡过程中，比较相邻的两个元素：如果逆序（左边元素大于右边元素），则二者交换。一次冒泡后，序列中最大的元素将位于序列的末尾，对剩余元素依次进行冒泡操作，直到没有任何一对数字需要比较。

实现

1
2
3
4
5
6
7
8
9
10
template <typename RandomIt>
void bubble_sort(RandomIt first, RandomIt last) {
  for (auto i = first; i < last; ++i) {
    for (auto j = first; j < last - 1; ++j) {
      if (*j > *(j + 1)) {
        std::swap(*j, *(j + 1));
      }
    }
  }
}

分析

  • 稳定排序算法
  • 最坏时间复杂度：\(O(n^{2})\)
  • 最优时间复杂度：\(O(n)\)
  • 平均时间复杂度：\(O(n^{2})\)
  • 最坏空间复杂度：共 \(O(n)\)，需要辅助空间 \(O(1)\)

归并排序 (Merge Sort)

原理

分治法 (Divide and Conquer)：递归地将序列平均分割为两个子序列，直到序列中只含有一个元素（即有序）；再利用归并操作 (merge) 将有序序列合并起来。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 利用辅助空间的合并
template <typename RandomIt>
void merge(RandomIt first, RandomIt mid, RandomIt last) {
  using data_type = typename std::remove_reference<decltype(*first)>::type;
  vector<data_type> left_sub(first, mid);
  vector<data_type> right_sub(mid, last);

  auto left_it = left_sub.cbegin();
  auto right_it = right_sub.cbegin();

  for (auto it = first; it != last; ++it) {
    if (left_it == left_sub.cend()) {
      *it = *right_it;
      ++right_it;
    } else if (right_it == right_sub.cend()) {
      *it = *left_it;
      ++left_it;
    } else if (*left_it < *right_it) {
      *it = *left_it;
      ++left_it;
    } else {
      *it = *right_it;
      ++right_it;
    }
  }
}

// 利用 3 次反转，原地合并两个有序序列
template <typename RandomIt>
void inplace_merge(RandomIt first, RandomIt mid, RandomIt last) {
  while (first < mid && mid < last) {
    while (first < mid && *first < *mid) {
      ++first;
    }
    auto index = mid;
    while (mid < last && *mid < *first) {
      ++mid;
    }

    std::reverse(first, index);
    std::reverse(index, mid);
    std::reverse(first, mid);

    first += mid - index + 1;
  }
}

template <typename RandomIt>
void merge_sort(RandomIt first, RandomIt last) {
  if (last - first <= 1) {
    return;
  }

  auto mid = first + (last - first) / 2;
  merge_sort(first, mid);
  merge_sort(mid, last);
  inplace_merge(first, mid, last);
}

分析

  • 稳定排序算法
  • 最坏时间复杂度：\(O(n \log{n})\)
  • 最优时间复杂度：\(O(n \log{n})\)
  • 平均时间复杂度：\(O(n \log{n})\)
  • 最坏空间复杂度：共 \(O(n)\)

选择排序 (Selection Sort)

原理

将序列划分为已排序和未排序两个子序列。起始时，已排序序列为空，未排序序列为整个原始序列。依次在未排序序列中找到最小元素，并将其放到已排序序列的末尾，直到未排序序列未空。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename RandomIt>
void selection_sort(RandomIt first, RandomIt last) {
  for (auto i = first; i < last - 1; ++i) {
    auto min_it = i;
    for (auto j = i; j < last; ++j) {
      if (*j < *min_it) {
        min_it = j;
      }
    }

    std::swap(*i, *min_it);
  }
}

分析

  • 最坏时间复杂度：\(O(n^{2})\)
  • 最优时间复杂度：\(O(n^{2})\)
  • 平均时间复杂度：\(O(n^{2})\)
  • 最坏空间复杂度：共 \(O(n)\)，需要辅助空间 \(O(1)\)

插入排序 (Insertion Sort)

原理

对于未排序序列中的每个元素，从前向后扫描已排序元素，找到相应位置并将其插入已排序序列。

实现

1
2
3
4
5
6
7
8
9
10
11
template <typename RandomIt>
void insertion_sort(RandomIt first, RandomIt last) {
  for (auto i = first + 1; i < last; ++i) {
    auto temp = *i;
    auto j = i - 1;
    for (; first <= j && temp < *j; --j) {
      *(j + 1) = *j;
    }
    *(j + 1) = temp;
  }
}

分析

  • 最坏时间复杂度：\(O(n^{2})\)
  • 最优时间复杂度：\(O(n)\)
  • 平均时间复杂度：\(O(n^{2})\)
  • 最坏空间复杂度：共 \(O(n)\)，需要辅助空间 \(O(1)\)

快速排序 (Quick Sort)

原理

分治法：

  1. 挑选基准值：从序列中挑选出一个 “基准” 元素
  2. 重新排列序列，使得所有比基准元素小的元素都在其左边，比基准元素大的元素都在其右边，此时基准元素已经就位
  3. 递归地排序基准元素左、右两边的子序列

选取基准的方式：

  • 固定位置：取序列第一个或最后一个元素作为基准值
  • 随机选取：随机选取待排序序列中任意一个元素作为基准值
  • 三数取中：选择最左端、最右端和中间位置三个元素的中值作为基准值

对于较小的数组，快速排序不如插入排序。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template <typename RandomIt>
void quick_sort(RandomIt first, RandomIt last) {
  if (first == last) {
    return;
  }

  auto pivot = *first;
  auto i = first;
  auto j = last - 1;
  while (i < j) {
    while (i < j && *j >= pivot) {
      --j;
    }
    *i = *j;
    while (i < j && *i <= pivot) {
      ++i;
    }
    *j = *i;
  }
  *i = pivot;

  quick_sort(first, i);
  quick_sort(i + 1, last);
}

分析

  • 最坏时间复杂度：\(\Theta(n^{2})\)
  • 最优时间复杂度：\(\Theta(n \log{n})\)
  • 平均时间复杂度：\(\Theta(n \log{n})\)
  • 最坏空间复杂度：取决于实现方式

堆排序 (Heap Sort)

原理

堆 (Heap)：完全二叉树且满足子节点的值总是小于（或者大于）它的父节点。若父节点的值恒小于等于其子节点的值，则成为最小堆 (Min Heap)；反之，若父节点的值恒大于等于其子节点的值，则成为最大堆 (Max Heap)。

堆通常使用一维数组实现。当数组的起始索引为 \(0\) 时：

  • 节点 \(i\) 的左子节点索引为 \(2 i + 1\)
  • 节点 \(i\) 的右子节点索引为 \(2 i + 2\)
  • 节点 \(i\) 的父节点索引为 \(\lfloor \frac{i - 1}{2} \rfloor\)

堆排序是利用堆这种数据结构进行排序的方法：首先把序列转换为最大堆，依次从最大堆中取出根节点（将根节点和最后一个节点交换，再把最后一个节点移出堆），并让剩余元素仍维持最大堆的性质。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
template <typename RandomIt, typename Distance>
void max_heapify(RandomIt first, Distance begin, Distance end) {
  auto parent = begin;
  auto child = 2 * parent + 1;

  while (child < end) {
    if (child + 1 < end && *(first + child) < *(first + child + 1)) {
      ++child;
    }

    if (*(first + parent) > *(first + child)) {
      return;
    }

    std::swap(*(first + parent), *(first + child));
    parent = child;
    child = 2 * parent + 1;
  }
}

template <typename RandomIt>
void heap_sort(RandomIt first, RandomIt last) {
  // 构造最大堆
  auto len = last - first;
  for (auto i = len / 2 - 1; i >= 0; --i) {
    max_heapify(first, i, len);
  }

  // 依次取出最大值：交换根节点和最后一个节点，再取出最后一个节点
  for (auto i = len - 1; i > 0; --i) {
    std::swap(*first, *(first + i));
    max_heapify(first, static_cast<decltype(i)>(0), i);
  }
}

分析

  • 不稳定排序算法
  • 最坏时间复杂度：\(O(n \log{n})\)
  • 最优时间复杂度：\(O(n \log{n})\)
  • 平均时间复杂度：\(\Theta(n \log{n})\)
  • 最坏空间复杂度：共 \(O(n)\)，需要辅助空间 \(O(1)\)