LeetCode刷题笔记(四): 排序

排序算法：包括快排，归并排序，桶排序，哈希排序等。

一、快排

• 算法介绍：对于当前一个未排序片段，我们先随机选择一个位置当作中枢点，然后通过遍历操作，将所有比中枢点小的数字移动到其左侧，再将所有比中枢点大的数字移动到其右侧。操作完成后，我们再次对中枢点左右侧的片段再次进行快速排序即可。可证明，如果中枢点选取是随机的，那么该算法的平均复杂度可以达到O(nlogn)，最差情况下复杂度则为O(n^2)。

• 代码：

  void quickSort(vector<int> &nums, int l, int r) {
    if (l >= r) return;
    int pivot = l + (rand() % (r - l + 1));
    int pivot_val = nums[pivot];
    swap(nums[l], nums[pivot]);
    int i = l + 1, j = r;
    while (true) {
        while (i < j && nums[j] >= pivot_val) --j;
        while (i < j && nums[i] <= pivot_val) ++i;
        if (i == j) break;
        swap(nums[i], nums[j]);
    }
    int new_pivot = nums[i] <= nums[l] ? i : i - 1;
    swap(nums[l], nums[new_pivot]);
    quickSort(nums, l, new_pivot - 1);
    quickSort(nums, new_pivot + 1, r);
  }

• 补充：枢纽pivot的选择有三点平均法，末尾法，首值法，但是随机取的效率貌似是最好的，所以快排又叫做随机排序法(不稳定的排序)。

二、归并排序

• 算法介绍：主要用到分治的思想，对于一个未排序片段，我们可以先分别排序其左半侧和右半侧，然后将两侧重新组合（“治”）；排序每个半侧时可以通过递归再次把它切分成两侧（“分”）。

• 代码：

  void mergeSort(vector<int> &nums, vector<int> &cache, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(nums, cache, l, mid);
    mergeSort(nums, cache, mid + 1, r);
    int i = l, j = mid + 1;
    for (int pos = l; pos <= r; ++pos) {
        if (j > r || (i <= mid && nums[i] <= nums[j])) {
            cache[pos] = nums[i++];
        } else {
            cache[pos] = nums[j++];
        }
    }
    for (int pos = l; pos <= r; ++pos) {
        nums[pos] = cache[pos];
    }
  }

• 补充：归并排序是稳定的排序，复杂度也是O(nlogn)，但是实际速度不如快排。

三、快速选择

• 题目：数组中的第K个最大元素
  在一个未排序的数组中，找到第k大的数字。

  解答：

  class Solution {
  public:
      int findKthLargest(vector<int>& nums, int k) {
          int len = nums.size();
          int pivot = rand() % len;
          vector<int> larger;
          vector<int> smaller;
          vector<int> equal;
          for (int i = 0; i < len; ++i) {
              if (nums[i] > nums[pivot]) 
                  larger.push_back(nums[i]);
              else if (nums[i] == nums[pivot])
                  equal.push_back(nums[i]);
              else
                  smaller.push_back(nums[i]);
          }
          int largerLen = larger.size();
          int smallerLen = smaller.size();
          int equalLen = equal.size();
          if (largerLen == k - 1 || (largerLen < k && equalLen + largerLen >= k))
              return nums[pivot];
          else if (largerLen >= k)
              return findKthLargest(larger, k);
          else
              return findKthLargest(smaller, k - largerLen - equalLen);
      }
  };

  提示：利用快排的思想，只需要找到某个pivot即可。

四、桶排序

• 题目：前k个高频元素
  给你一个整数数组nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。

  解答：

  class Solution {
  public:
      vector<int> topKFrequent(vector<int>& nums, int k) {
          unordered_map<int, int> map;
          for (int num : nums) {
              ++map[num];
          }
          unordered_map<int, vector<int>> reMap;
          for (auto [key, val] : map) {
              reMap[val].push_back(key);
          }
          vector<int> res;
          for (int i = nums.size(); i >= 0 && k > 0; --i) {
              if (reMap[i].size() > 0) {
                  for (int j = 0; j < reMap[i].size() && k > 0; ++j) {
                      res.push_back(reMap[i][j]);
                      --k;
                  }
              }
          }
          return res;
      }
  };

  提示：使用hashMap可以减少存储空间。

五、练习

• 题目一：根据字符出现频率排序
  给定一个字符串s，根据字符出现的频率对其进行降序排序。一个字符出现的频率是它出现在字符串中的次数。返回已排序的字符串。如果有多个答案，返回其中任何一个。

  解答：

  class Solution {
  public:
      string frequencySort(string s) {
          unordered_map<char, int> map;
          for (char c : s) {
              ++map[c];
          }
          unordered_map<int, vector<char>> reMap;
          for (auto [key, val] : map) {
              reMap[val].push_back(key);
          }
          string res = "";
          for (int i = s.length(); i > 0; --i) {
              if (reMap[i].size() > 0) {
                  for (char c : reMap[i]) {
                      string tmp(i, c);
                      res += tmp;
                  }
              }
          }
          return res;
      }
  };

  提示：桶排序的变式。

• 题目二：颜色排序
  给定一个包含红色、白色和蓝色、共n个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数0、1和2分别表示红色、白色和蓝色。

  解答：

  class Solution {
  public:
      void sortColors(vector<int>& nums) {
          int ptr0 = 0, ptr1 = 0;
          for (int i = 0; i < nums.size(); i ++) {
              if (nums[i] == 1) {
                  swap(nums[i], nums[ptr1]);
                  ++ptr1;
              } else if (nums[i] == 0) {
                  swap(nums[i], nums[ptr0]);
                  if (ptr0 < ptr1) swap(nums[i], nums[ptr1]);
                  ++ptr0;
                  ++ptr1;
              }
          }
      }
  };

  提示：更像双指针的题目，只需要把0和1排好即可把2排好。