1 常见排序的时间复杂度[1]

  • 冒泡、选择、插入：O(n2)
  • 快速、推、归并、希尔：O(n*log2n)
  • 计数：O(n+m)
  • 桶：O(n) | 排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 | | —- | —- | —- | —- | —- | | 冒泡排序 | O(n2) | O(n2) | O(1) | 稳定 | | 选择排序 | O(n2) | O(n2) | O(1) | 数组不稳定、链表稳定 | | 插入排序 | O(n2) | O(n2) | O(1) | 稳定 | | 快速排序 | O(nlog2n) | O(n2) | O(log2n) | 不稳定 | | 堆排序 | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 | | 归并排序 | O(nlog2n) | O(nlog2n) | O(n) | 稳定 | | 希尔排序 | O(nlog2n) | O(n2) | O(1) | 不稳定 | | 计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 | | 桶排序 | O(n) | O(n) | O(m) | 稳定 | | 基数排序 | O(k*n) | O(n2) | | 稳定 |

2 常规排序算法的实现

2.1 冒泡排序

  • 比较相邻元素，前者大于后者，则交换

  • 常规

    1. void bubbleSort(vector<int>& v) {
    2.   int len = v.size();
    3.   for (int i = 0; i < len - 1; ++i) {
    4.       for (int j = 0; j < len - i - 1; ++j) {
    5.           if (v[j] > v[j+1]) {
    6.               swap(v[j], v[j+1]);
    7.           }
    8.       }
    9.   }
    10. }

  • 模板实现

    1. template<typename T> 
    2. void bubbleSort(T arr[], int len) {
    3.   for (int i = 0; i < len - 1; ++i) {
    4.       for (int j = 0; j < len - i - 1; ++j) {
    5.           if (arr[j] > arr[j + 1]) {
    6.               swap(arr[j], arr[j + 1]);
    7.           }
    8.       }
    9.   }
    10. }

    2.2 选择排序

  • 在无序区找最小值放到有序区后面

    1. void selectionSort(vector<int>& v) {
    2.   int min, len = v.size();
    3.   for (int i = 0; i < len - 1; ++i) {
    4.       min = i;
    5.       for (int j = i + 1; j < len; ++j) {
    6.           if (v[j] < v[min]) min = j;
    7.       }
    8.       if (i != min) swap(v[i], v[min]);
    9.   }
    10. }

  • 模板实现

    1. template<typename T>
    2. void selectionSort(std::vector<int>& v) {
    3.   int len = v.size();
    4.   int min, len = v.size();
    5.   for (int i = 0; i < len - 1; ++i) {
    6.       min = i;
    7.       for (int j = i + 1; j < len; ++j) {
    8.           if (v[j] < v[min]) min = j;
    9.       }
    10.       if (i != min) swap(v[i], v[min]);
    11.   }
    12. }

    2.4 快速排序

  1. 选取第一个数为基准
  2. 将比基准小的数交换到前面，比基准大的数交换到后面

  3. 对左右区间重复第二步，直到各区间只有一个数

    1. void quickSort(vector<int>& v, int low, int high) {
    2.  if (low >= high)        // 结束标志
    3.      return;
    4.  int first = low;        // 低位下标
    5.  int last = high;        // 高位下标
    6.  int key = v[first];        // 设第一个为基准
    8.  while (first < last)
    9.  {
    10.      // 从后往前，将比第一个小的移到前面
    11.      while (first < last && v[last] >= key)
    12.          last--;
    13.      if (first < last)
    14.          v[first++] = v[last];
    16.      // 从前往后，将比第一个大的移到后面
    17.      while (first < last && v[first] <= key)
    18.          first++;
    19.      if (first < last)
    20.          v[last--] = v[first];
    21.  }
    22.  // 基准置位
    23.  v[first] = key;
    24.  // 前半递归
    25.  quickSort(v, low, first - 1);
    26.  // 后半递归
    27.  quickSort(v, first + 1, high);
    28. }

    3 应用场景[3]

  • 规模较小：插入、选择
  • 规模较大：快排、堆排序、归并
  • 文件初始状态基本有序：插入、冒泡、快排

参考

  1. https://gitee.com/vict0r/interview#%EF%B8%8F-%E7%AE%97%E6%B3%95
  2. https://gitee.com/vict0r/interview#%E6%8E%92%E5%BA%8F
  3. https://www.pianshen.com/article/41091661394/