LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 快速排序，平均时间复杂度 O(n log n)，空间复杂度 O(log n)，不稳定排序。最差情况下每次只能划分出一个元素，最差时间复杂度为 O(n ^ 2)，最差空间复杂度为 O(n)

class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    quickSort(nums, 0, size(nums) - 1);
    return nums;
  }

  void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) {
      return;
    }
    int n = partition(nums, l, r);
    quickSort(nums, l, n - 1);
    quickSort(nums, n + 1, r);
  }

  int partition(vector<int>& nums, int l, int r) {
    int i = l;
    int j = r;
    while (i < j) {
      while (i < j && nums[j] >= nums[l]) {
        --j;
      }
      while (i < j && nums[i] <= nums[l]) {
        ++i;
      }
      if (i < j) {
        swap(nums[i], nums[j]);
      }
    }
    swap(nums[i], nums[l]);
    return i;
  }
};

• 归并排序，时间复杂度 O(n log n)，空间复杂度 O(n)（O(n + log n)），稳定排序

class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    return mergeSort(nums, 0, size(nums) - 1);
  }

  vector<int> mergeSort(vector<int>& nums, int l, int r) {
    if (l > r) {
      return {};
    }
    if (l == r) {
      return {nums[l]};
    }
    int m = l + (r - l) / 2;
    vector<int> a{mergeSort(nums, l, m)};
    vector<int> b{mergeSort(nums, m + 1, r)};
    int i = 0;
    int j = 0;
    vector<int> res;
    while (i < size(a) && j < size(b)) {
      if (a[i] == b[j]) {
        res.emplace_back(a[i++]);
        res.emplace_back(b[j++]);
      } else if (a[i] < b[j]) {
        res.emplace_back(a[i++]);
      } else {
        res.emplace_back(b[j++]);
      }
    }
    while (i < size(a)) {
      res.emplace_back(a[i++]);
    }
    while (j < size(b)) {
      res.emplace_back(b[j++]);
    }
    return res;
  }
};

• 堆排序，时间复杂度 O(n log n)，空间复杂度 O(1)，不稳定排序

class Solution {
 public:
  vector<int> sortArray(vector<int> &nums) {
    heapSort(nums);
    return nums;
  }

  void heapSort(vector<int> &nums) {
    for (int i = size(nums) / 2 - 1; i >= 0; --i) {
      adjustHeap(nums, i, size(nums));
    }
    for (int i = size(nums) - 1; i > 0; --i) {
      swap(nums[0], nums[i]);
      adjustHeap(nums, 0, i);
    }
  }

  void adjustHeap(vector<int> &nums, int i, int m) {
    while (2 * i + 1 < m) {
      int l = 2 * i + 1;
      int r = 2 * i + 2;
      int mx = r < m && nums[l] < nums[r] ? r : l;
      if (nums[i] < nums[mx]) {
        swap(nums[i], nums[mx]);
        i = mx;
      } else {
        break;
      }
    }
  }
};

• 冒泡排序，通过两两交换把最小元素沉到最前。时间复杂度 O(n ^ 2)，空间复杂度 O(1)，稳定排序。最好情况下所有元素已排好序，时间复杂度为 O(n)

class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    bubbleSort(nums);
    return nums;
  }

  void bubbleSort(vector<int>& nums) {  // 依次把最小的元素往前沉
    for (int i = 0; i < size(nums); ++i) {
      for (int j = 0; j < i; ++j) {
        if (nums[i] < nums[j]) {
          swap(nums[i], nums[j]);
        }
      }
    }
  }

  void bubbleSort2(vector<int>& nums) {  // 依次把最大的元素往后沉
    int sz = size(nums);
    if (sz <= 1) {
      return;
    }
    for (int i = 0; i < sz - 1; ++i) {
      bool seq = true;
      for (int j = 0; j < sz - 1 - i; ++j) {
        if (nums[j] > nums[j + 1]) {
          swap(nums[j], nums[j + 1]);
          seq = false;
        }
      }
      if (seq) {
        return;  // 如果比完一轮未交换则已有序，提前结束
      }
    }
  }
};

• 选择排序，每次选一个最小的元素放到最前。时间复杂度 O(n ^ 2)，空间复杂度 O(1)，不稳定排序

class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    selectSort(nums);
    return nums;
  }

  void selectSort(vector<int>& nums) {
    for (int i = 0; i < size(nums) - 1; ++i) {
      int t = i;
      for (int j = i + 1; j < size(nums); ++j) {
        if (nums[j] < nums[t]) {
          t = j;
        }
      }
      swap(nums[t], nums[i]);
    }
  }
};

• 插入排序，把元素一个个添加到序列中，每次添加都保持序列有序。时间复杂度 O(n ^ 2)，空间复杂度 O(1)，稳定排序。最好情况下所有元素已排好序，时间复杂度为 O(n)，如下实现不针对最好情况做优化

class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    insertSort(nums);
    return nums;
  }

  void insertSort(vector<int>& nums) {
    for (int i = 1; i < size(nums); ++i) {
      for (int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; --j) {
        swap(nums[j], nums[j + 1]);
      }
    }
  }
};

• 地精排序，和插入排序过程相同，但写法更简洁。时间复杂度 O(n ^ 2)，空间复杂度 O(1)，稳定排序。最好情况下所有元素已排好序，最好时间复杂度为 O(n)，如下实现不针对最好情况做优化

class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    gnomeSort(nums);
    return nums;
  }

  void gnomeSort(vector<int>& nums) {
    int i = 1;
    while (i < size(nums)) {
      if (i > 0 && nums[i] < nums[i - 1]) {
        swap(nums[i], nums[i - 1]);
        --i;
      } else {
        ++i;
      }
    }
  }
};

• 希尔排序，对相隔一定距离的元素进行插入排序。时间复杂度与选取的间隔有关，目前没有完整的数学分析，The Art of Computer Programming, Volume 3 中由大量实验统计资料得出，数据量很大时，排序码平均比较次数和元素平均移动次数大约在 n ^ 1.25 到 1.6 * n ^ 1.25 范围内。空间复杂度 O(1)，不稳定排序

class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    shellSort(nums);
    return nums;
  }

  void shellSort(vector<int>& nums) {
    for (int gap = size(nums) / 2; gap > 0; gap /= 2) {
      for (int i = gap; i < size(nums); ++i) {
        for (int j = i; j - gap >= 0 && nums[j - gap] > nums[j]; j -= gap) {
          swap(nums[j - gap], nums[j]);
        }
      }
    }
  }
};

• 桶排序，非基于比较的排序，只能用于整数，牺牲空间换时间。桶数量为 m，时间复杂度 O(n + n log n - n log m)（O(n) + O(k * (n / m)) * log(n / m)) = O(n + n * (log n - log m))），空间复杂度度 O(n + m)。最好情况下每个桶只有一个数据（m = n），最好时间复杂度为 O(n)

class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    int mx = *max_element(begin(nums), end(nums));
    int mn = *min_element(begin(nums), end(nums));
    return bucketSort(nums, mn, mx);
  }

  vector<int> bucketSort(vector<int>& nums, int mn, int mx) {
    vector<int> buckets(mx - mn + 1);
    for (auto& x : nums) {
      ++buckets[x - mn];
    }
    vector<int> res;
    for (int i = 0; i < size(buckets); ++i) {
      for (int j = 0; j < buckets[i]; ++j) {
        res.emplace_back(i + mn);
      }
    }
    return res;
  }
};

• STL 提供了 std::sort

class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    sort(begin(nums), end(nums));
    return nums;
  }
};

• std::sort 整合了多种排序算法以尽可能达到最优效果，数据少则直接用插入排序，数据多则先用三路快速排序，如果划分次数到达一定次数则改用堆排序或插入排序。源码分析如下

template <class _RanIt, class _Pr>
inline void sort(const _RanIt _First, const _RanIt _Last, _Pr _Pred) {
  _Adl_verify_range(_First, _Last);             // 判断迭代器范围
  const auto _UFirst = _Get_unwrapped(_First);  // 左边界
  const auto _ULast = _Get_unwrapped(_Last);    // 右边界
  _Sort_unchecked(_UFirst, _ULast, _ULast - _UFirst, _Pass_fn(_Pred));  // 排序
}

template <class _RanIt, class _Pr>
inline void _Sort_unchecked(_RanIt _First, _RanIt _Last,
                            _Iter_diff_t<_RanIt> _Ideal, _Pr _Pred) {
  _Iter_diff_t<_RanIt> _Count;  // 迭代器的范围差
  // _ISORT_MAX是插入排序的最大尺寸，本质是一个整型常量，定义为 32
  while (_ISORT_MAX < (_Count = _Last - _First) &&
         0 < _Ideal) {  // _Ideal 记录递归层次，初始为要处理的元素数
    // 数据量多于 32，且 _Ideal 大于 0，则先用快速排序
    auto _Mid =
        _Partition_by_median_guess_unchecked(_First, _Last, _Pred);  // 划分点
    _Ideal = (_Ideal >> 1) + (_Ideal >> 2);                          // 乘 0.75
    if (_Mid.first - _First < _Last - _Mid.second) {  // 数据量多的部分
      _Sort_unchecked(_First, _Mid.first, _Ideal, _Pred);
      _First = _Mid.second;
    } else {  // 数据量少的部分
      _Sort_unchecked(_Mid.second, _Last, _Ideal, _Pred);
      _Last = _Mid.first;
    }
  }

  // ISORT_MAX >= _Last - _First，则元素数过少，直接使用插入排序
  // _Ideal 为 0，则已达到初始设置的最大划分次数上限，不进行上述划分
  if (_ISORT_MAX < _Count) {  // _ISORT_MAX < _Last - _First
    // 划分次数过多会导致复杂度退化，此时使用复杂度稳定为 O(n log n) 的堆排序
    _Make_heap_unchecked(_First, _Last, _Pred);
    _Sort_heap_unchecked(_First, _Last, _Pred);
  } else if (2 <= _Count) {  // 如果数据量少于 32 但不少于 2，则使用插入排序
    _Insertion_sort_unchecked(_First, _Last, _Pred);
  }
}