排序算法 - Yuchen's Blog

排序算法稳定性

常用排序稳定性

我暂时还没具体分析锦标赛排序为什么是不稳定的。

Stable Sorting Algorithms:

Insertion Sort、Merge Sort、Bubble Sort、Tim Sort、Counting Sort、Block Sort、Quadsort、Library Sort、Cocktail shaker Sort、Gnome Sort、Odd–even Sort

Unstable Sorting Algorithms:

Heap sort、Selection sort、Shell sort、Quick sort、Introsort (subject to Quicksort)、Tree sort、Cycle sort、Smoothsort、Tournament sort(subject to Heapsort)

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定
直接选择排序	O(n²)	O(n²)	O(n)	O(1)	不稳定
直接插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定
快速排序	O(nlogn)	O(n²)	O(nlogn)	O(nlogn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
希尔排序	O(nlogn)	O(ns)	O(n)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定
基数排序	O(N*M)	O(N*M)	O(N*M)	O(M)	稳定

交换的实现

template <typename T>
void Swap(T &a, T &b) {
  T temp = a;
  a = b;
  b = temp;
}

简单选择排序

它的工作原理是每次找出第 \(i\) 小的元素（也就是 \(A_{i\dots n}\) 中最小的元素），然后将这个元素与数组第 \(i\) 个位置上的元素交换。

template <typename T>
void selection_sort(std::vector<T> &arr) {
  int len = arr.size();
  for (int i = 0; i < len; ++i) {
    int idx = i;
    for (int j = i + 1; j < len; ++j) {
      if (arr[j] < arr[idx]) idx = j;  // 此处需要类型T重载"<"运算符
    }
    std::swap(arr[i], arr[idx]);
  }
}

冒泡排序

它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。经过 \(i\) 次扫描后，数列的末尾 \(i\) 项必然是最大的 \(i\) 项，因此冒泡排序最多需要扫描 \((n-1)\) 遍数组就能完成排序。 [ 冒泡排序的两点优化 ]

template <typename T>
void bubble_sort_opt(std::vector<T> &arr) {
  int len = arr.size();
  bool swapped = true;
  while (swapped) {
    swapped = false;
    for (int i = 1; i < len; ++i) {
      if (arr[i] < arr[i - 1]) {
        swapped = true;
        std::swap(arr[i - 1], arr[i]);
      }
    }
    // --len; // 可优化，第i轮扫描可以确定前i大的数字
  }
}

插入排序

它的工作原理为将待排列元素划分为“已排序”和“未排序”两部分，每次从“未排序的”元素中选择一个插入到“已排序的”元素中的正确位置。

template <typename T>
void insertion_sort(std::vector<T> &arr) {
  int len = arr.size();
  for (int i = 1; i < len; ++i) {
    T key = arr[i];
    int idx = i - 1;
    while (idx >= 0 && key < arr[idx]) {
      arr[idx + 1] = arr[idx];
      --idx;
    }
    arr[idx + 1] = key;  //可知arr[idx] <= key, 插入位置为idx + 1
  }
}

template <typename T>
void insertion_sort(std::vector<T> &arr) {
  int len = arr.size();
  if (len <= 1) return;
  for (int i = 1; i < len; ++i) {
	for (int j = i; j >= 1 && arr[j] < arr[j-1]; --j) {
      std::swap(arr[j], arr[j-1]);
    }
  }
}

快速排序

快排，又被称作分区交换排序（partition-exchange sort），基本思想是分治，步骤如下：

将数列划分为两部分（要求保证相对大小关系）；
递归到两个子序列中分别进行快速排序；
不用合并，因为此时数列已经完全有序。

template <typename T>
int partition(std::vector<T> &arr, int low, int high) {
  T key = arr[low];
  while (low < high) {
    // 先处理右侧
    while (low < high && arr[high] >= key) --high;
    arr[low] = arr[high];
    // 处理左侧
    while (low < high && arr[low] <= key) ++low;
    arr[high] = arr[low];
  }
  arr[low] = key;

  return low;
}

template <typename T>
void quick_sort(std::vector<T> &arr, int low, int high) {
  if (low < high) {
    int idx = partition(arr, low, high);
    quick_sort(arr, low, idx - 1);
    quick_sort(arr, idx + 1, high);
  }
}

快排的优化技巧：随机化选取key，取三个key的中间数，待排序序列规模较小时使用插入排序

归并排序

归并排序分为三个步骤：

将数列划分为两部分；
递归地分别对两个子序列进行归并排序；
合并两个子序列。

// 递归写法
template <typename T>
void merge(std::vector<T> &arr, int low, int mid, int high) {
  std::vector<T> tmp_arr;
  tmp_arr.reserve(high - low + 1); // 其实这里还不是很完美
  int left_idx = low;
  int right_idx = mid + 1;
  while (left_idx <= mid && right_idx <= high) {
    if (arr[left_idx] < arr[right_idx]) {
      tmp_arr.push_back(arr[left_idx]);
      ++left_idx;
    } else {
      tmp_arr.push_back(arr[right_idx]);
      ++right_idx;
    }
  }
  while (left_idx <= mid) {
    tmp_arr.push_back(arr[left_idx]);
    ++left_idx;
  }
  while (right_idx <= high) {
    tmp_arr.push_back(arr[right_idx]);
    ++right_idx;
  }
  std::cout << tmp_arr.size() << " " << tmp_arr.capacity() << std::endl;
  for (int i = 0; i < high - low + 1; ++i) arr[low + i] = tmp_arr[i];
}

template <typename T>
void merge_sort(std::vector<T> &arr, int low, int high) {
  if (low < high) {
    int mid = low + (high - low) / 2;
    merge_sort(arr, low, mid);
    merge_sort(arr, mid + 1, high);
    merge(arr, low, mid, high);
  }
}

// 迭代写法
template <typename T>
void merge_sort2(std::vector<T> &arr, int low, int high) {
  int len = high - low + 1;
  std::vector<T> tmp_arr;
  tmp_arr.reserve(len);
  for (int seg = 1; seg < len; seg += seg) {
    for (int idx = 0; idx < len; idx += seg * 2) {
      int left = idx;
      int mid = std::min(idx + seg, len);
      int right = std::min(idx + seg * 2, len);
      int tmp_idx = left;
      int idx1 = left;
      int idx2 = mid;
      // 归并
      while (idx1 < mid && idx2 < right) {
        tmp_arr[tmp_idx++] =
            (arr[idx1] < arr[idx2]) ? arr[idx1++] : arr[idx2++];
      }
      while (idx1 < mid) tmp_arr[tmp_idx++] = arr[idx1++];
      while (idx2 < high) tmp_arr[tmp_idx++] = arr[idx2++];
    }
    std::swap(arr, tmp_arr);
  }
}

[ 归并排序 - 维基百科 ]

堆排序

数组从小到大排序应当建立大顶堆：将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质；之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；以此类推，在第 \(n-1\) 次操作后，整个数组就完成了排序。

在STL中，优先队列priority_queue默认是小顶堆，所以输出序列是从大到小排序。

template <typename T>
void sift_down(std::vector<T> &arr, int low, int high) {
  int parent = low;
  int child = parent * 2 + 1;
  while (child <= high) {
    if (child + 1 <= high && arr[child] < arr[child + 1]) {  // 小顶堆改成arr[child] > arr[child + 1]
      ++child;
    }
    if (arr[parent] >= arr[child]) {  //  小顶堆改成arr[parent] <= arr[child]
      break;
    } else {
      std::swap(arr[parent], arr[child]);
      parent = child;
      child = parent * 2 + 1;
    }
  }
}

template <typename T>
void heap_sort(std::vector<T> &arr) {
  int len = arr.size();
  // 建堆
  for (int i = len / 2 - 1; i >= 0; --i) sift_down(arr, i, len - 1);
  // 排序, 将堆顶元素与第i个元素 (当前堆的最后一个) 交换位置
  for (int i = len - 1; i > 0; --i) {
    std::swap(arr[0], arr[i]);
    sift_down(arr, 0, i - 1);
  }
}

希尔排序

希尔排序又称递减增量排序算法，具体介绍见 [ 希尔排序 - 维基百科 ]

template <typename T>
void shell_sort(std::vector<T> &arr, int low, int high) {
  int len = high - low + 1;
  for (int step_size = len >> 1; step_size > 0; step_size >>= 1) {
    for (int i = step_size; i < len; ++i) {
      for (int j = i; j >= step_size && arr[j] < arr[j - step_size];
           j -= step_size) {
        std::swap(arr[j], arr[j - step_size]);
      }
    }
  }
}

分割线

下面几种排序的重要性较弱。

计数排序适合数据范围不大的一组数进行排序。
基数排序要求数据之间明显存在可进行关键字比较的特征。
桶排序同样适用于数据范围不大的情况，它可以视作对计数排序的改进，减少了空间浪费。

计数排序

它的工作过程分为三个步骤：

计算每个数出现了几次；
求出每个数出现次数的前缀和；
利用出现次数的前缀和，从右至左计算每个数的排名（保证排序算法的稳定性，即相同大小的数字，原先在右侧的仍然在右侧）。

// C++ Version
const int N = 100010;
const int W = 100010;

int n, w, a[N], cnt[W], b[N];

void counting_sort() {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i]];
  for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
}

基数排序

它的工作原理是将待排序的元素拆分为 \(k\) 个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第 \(k\) 关键字进行稳定排序，再对第 \((k-1)\) 关键字进行稳定排序，再对第 \((k-2)\) 关键字进行稳定排序……最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。

==基数排序需要借助一种 稳定算法 完成内层对关键字的排序。==

/* 基数排序
 * 假设所有数都是非负的整数, 关键字的排序使用计数排序
 */

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

void counting_sort(std::vector<unsigned int> &arr, unsigned int mod) {
  int len = arr.size();
  std::vector<unsigned int> cnt(10, 0);
  std::vector<unsigned int> tmp_arr(len, 0);
  // 计数
  for (auto n : arr) {
    ++cnt[(n / mod) % 10];
  }
  // 求cnt前缀和
  for (int i = 1; i < cnt.size(); ++i) {
    cnt[i] += cnt[i - 1];
  }
  // 自右向左排序
  for (int i = len - 1; i >= 0; --i) {
    int key = (arr[i] / mod) % 10;
    tmp_arr[cnt[key] - 1] = arr[i];
    --cnt[key];
  }
  arr = tmp_arr;
}

void radix_sort(std::vector<unsigned int> &arr) {
  unsigned int max_num = *std::max_element(arr.begin(), arr.end());
  // 取出最大的数用于判断关键字数量，按关键字(0-9)排序，其余较短数字缺位补0
  // 此处关键字比较顺序是从个位开始，向高位比较
  for (unsigned int mod = 1; max_num / mod > 0; mod *= 10) {
    counting_sort(arr, mod);
  }
}

int main() {
  std::vector<unsigned int> arr = {53,  3,  542, 748, 14, 214,
                                   154, 14, 63,  616, 589};
  radix_sort(arr);
  std::copy(arr.begin(), arr.end(),
            std::ostream_iterator<unsigned int>(std::cout, " "));
  return 0;
}

桶排序

工作的原理是将数组分到有限数量的桶里，每个桶再各自排序（配合其它排序算法），步骤如下：

设置一个定量的数组当作空桶。
寻访序列，并且把项目逐个放到对应的桶内。
对每个非空桶进行排序。
合并所有非空桶内数据，还原成有序序列。

[ 桶排序 - 维基百科 ] 这里有基于链表的桶排序实现。

// 假设只有10个桶，数字范围是[0, 99]
const int NUM_BUCKETS = 10;

template <typename T = int>
void _insertion_sort(std::vector<T> &arr) {
  int len = arr.size();
  if (len <= 1) return;
  for (int i = 1; i < len; ++i) {
    for (int j = i; j >= 1 && arr[j] < arr[j - 1]; --j) {
      std::swap(arr[j], arr[j - 1]);
    }
  }
}

template <typename T = int>
void bucket_sort(std::vector<T> &arr, int low, int high) {
  // 元素分桶
  std::vector<std::vector<T>> buckets(NUM_BUCKETS, std::vector<T>{});
  for (auto n : arr) {
    int idx = n / NUM_BUCKETS;
    buckets.at(idx).push_back(n);
  }
  // 桶内排序, 同时合并结果
  int k = 0;
  for (int i = 0; i < NUM_BUCKETS; ++i) {
    _insertion_sort(buckets.at(i));
    for (auto n : buckets.at(i)) {
      arr[k++] = n;
    }
  }
}

算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

从小爱刷题！上一篇

C++知识点小结下一篇