G&R Blog Release Regulation

快速排序

1.快速排序, 是一种基于 divide-and-conquer 思想下的排序算法, 核心实现是借助于 partition 算法
2.我们已知 partition 算法可以支持对数组中的任意一个元素, 放到属于它在排序之后正确的位置之上; 延续 partition 的这种功能, 快速排序递归地对安排好当前位置的元素的两边递归地进行 partition, 直到所有的元素都被 partition 完毕, 数组最终得到排序之后的结果, 快速排序的框架如下:

void quickSort(vector<int>& nums, int low, int high) {
  if (low >= high) {
    return;
  }
  int pos = partition(nums, low, high);
  quickSort(nums, low, pos-1);
  quickSort(nums, pos+1, high);
  return;
}

3.对于随机分布的数据而言, 快速排序略快于 mergeSort 和 heapSort; 平均的时间复杂度为 O(nlogn), 最坏情况下 O(n^2)
4.快速排序的优化
(i). 切入到插入排序: 在排序数组长度比较小的情况下, 用插入排序更快, 通常长度为 5-15 这样一个排序长度下, 插入排序更快
(ii). 三向切分排序: 在实际应用中, 我们待排序的数组通常都大概率有很多重复元素, 例如按照男女性别排序; 如果处理这种存在大量重复元素的情况, 一个元素重复的部分我们不要去排序, 一个典型的思路是采用三分的思路, 将数组切分成 < target, == target, > target 的三部分, 然后只对 < target 和 > target 这两部分进行递归, 思路如下:

void quickSort(vector<int>& nums, int l, int r) {
  if (l >= r) {
    return;
  }
  int pivotPos = partition(nums, l, r);
  int lPivot = pivotPos - 1;
  int rPivot = pivotPos + 1;
  while (lPivot >= l && nums[lPivot] == nums[pivotPos]) {
    --lPivot;
  }
  while (rPivot <= r && nums[rPivot] == nums[pivotPos]) {
    ++rPivot;
  }
  quickSort(nums, l, lPivot);
  quickSort(nums, rPivot, r); 
}

5.我们写一个双指针 partition 且交换版本

912.排序数组

class Solution {
 public:
  int partition(vector<int>& arr, int left, int right) {
    int pivotIdx = left;
    int l = left + 1;
    int r = right;
    while (l <= r) {
      while (l <= r && arr[l] < arr[pivotIdx]) {
        ++l;
      }
      while (l <= r && arr[r] > arr[pivotIdx]) {
        --r;
      }
      if (l <= r) {
        swap(arr[l], arr[r]);
        ++l;
        --r;
      }
    }
    swap(arr[pivotIdx], arr[r]);
    return r;
  }
  void quickSort(vector<int>& nums, int l, int r){
    if (l < r) {
      swap(nums[l + rand() % (r - l + 1)], nums[l]);
      int mid = partition(nums, l, r);
      quickSort(nums, l, mid-1);
      quickSort(nums, mid+1, r);
    }
  }
  vector<int> sortArray(vector<int>& nums) {
    quickSort(nums, 0, nums.size()-1);
    return nums;
  }
};

再补充一个双指针 partition 覆盖实现版本

class Solution {
 public:
  int partition(vector<int>& nums, int left, int right) {
    int randIdx = left + rand() % (right - left + 1);
    swap(nums[randIdx], nums[right]);
    int pivot = nums[right];
    int l = left;
    int r = right;
    while (l < r) {
      while (l < r && nums[l] <= pivot) {
        ++l;
      }
      nums[r] = nums[l];
      while (l < r && nums[r] >= pivot) {
        --r;
      }
      nums[l] = nums[r];

    }
    nums[l] = pivot;
    return l;
  }
  void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) {
      return;
    }
    int pivotPos = partition(nums, l, r);
    int lPivot = pivotPos - 1;
    int rPivot = pivotPos + 1;
    while (lPivot >= l && nums[lPivot] == nums[pivotPos]) {
      --lPivot;
    }
    while (rPivot <= r && nums[rPivot] == nums[pivotPos]) {
      ++rPivot;
    }
    quickSort(nums, l, lPivot);
    quickSort(nums, rPivot, r); 
  }
  vector<int> sortArray(vector<int>& nums) {
    quickSort(nums, 0, nums.size()-1);
    return nums;
  }
};

215.数组中的第K个最大的元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1: 输入: [3,2,1,5,6,4], k = 2 输出: 5

示例 2: 输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4

分析:
1.原始数组长度为 len, 找第 k 大的元素, 也就是找排序后 index = len-k 位置的元素
2.我们对数组采用 partition 算法, 可以实现检索 len - k 位置元素的二分思想, 因为 partition 算法每次可以使得左边一半小于右边一半元素, 然后实现只在一半元素里面搜索
3.对我们随机找的第 1 个枢轴, 例如最左侧端点位置, 还原位置为 pos; 然后判断 pos 和 len-k 的关系
(i). pos == len - k, 那么就是 pos 元素就是我们要的数
(ii). pos < len - k, 那么就去以 pos 作为分界点的右侧区间找, l = pos + 1
(iii). pos > len - k, 那么就去以 pos 作为分界点的左侧区间找, r = pos - 1
4.另外我们可以引入 threeWayPartition 的思想, 额外处理一下相同的元素不进入 partition, 时间复杂度搞到线性
(i). pos < len - k, l 可以持续向右比较, 如果当前元素和左侧相邻元素相同, 那么 ++l
(ii). pos > len - k, r 可以持续向左比较, 如果当前元素和右侧相邻元素相同, 那么 —r

class Solution {
 public:
  int partition(int l, int r, vector<int>& nums) {
    int pivot = nums[l];
    while (l < r) {
      while (l < r && nums[r] >= pivot) {
        --r;
      }
      nums[l] = nums[r];
      while (l < r && nums[l] <= pivot) {
        ++l;
      }
      nums[r] = nums[l];
    }
    nums[l] = pivot;
    return l;
  }
  int findKthLargest(vector<int>& nums, int k) {
    int len = nums.size();
    int l = 0;
    int r = len - 1;
    int pos;
    k = len - k;
    while (l <= r) {
      pos = partition(l, r, nums);
      if (pos == k) {
        return nums[pos];
      } else if (pos < k) {
        l = pos + 1;
        while (l < k && nums[l] == nums[l-1]) {
          ++l;
        }
      } else if (pos > k) {
        r = pos - 1;
        while (r > k && nums[r] == nums[r+1]) {
          --r;
        }
      }
    }
    return 0;
  }
};

Reference

[1]. 算法 第四版.

---

转载请注明来源, from goldandrabbit.github.io