排序算法快速排序_快速排序稳定吗

目录

排序算法

十大排序算法总览

快速排序（重点）

基本思路

• 快速排序每一次都排定一个元素（这个元素被放在了它最终应该呆的位置） ， 然后递归地去排它左边的部分和右边的部分。 依次进行下去， 知道数组有序。
• 算法思想： 分治思想。 和【归并排序】不同， 快排在【分】这个事情上不像【归并排序】一样一分为二， 而是利用partition的方法， 因此就没有【合】的过程。
• 实现细节（如果是顺序数组或者逆序数组）一定要随机化选择切分元素， 否则在输入数组是有序数组或者是逆序数组的时候， 快速排序就会变得非常慢。

经典题目

数组中的第k个最大元素

颜色分类

快排的基本做法

#include<iostream> using namespace std; // 选择基准 int partition(int array[], int low, int high){ 
    while(low < high){ 
    // low 位置为bound， low 右边的不小于low左边的 // 从右往左找一个小于6的数， 再从左往右找一个大于6的数 while(low < high && array[low] <= array[high]){ 
    high--; } int tmp = array[low]; array[low] = array[high]; array[high] = temp; while(low < high && array[low] <= array[high]){ 
    low++; } tmp = array[low]; array[low] = array[high]; array[high] = temp; } return low; } void quickSortHelp(int array[], int low , int high) { 
    if(low < high) { 
    int location = parition(array, low, high); quickSortHelp(array, low,location - 1); quickSortHelp(array, location + 1, high); } } void quickSort(int array[], int n){ 
    qickSortHelp(array, 0, n-1); } 

快排的随机化版本

通过随机化选择基准数， 避免出现O(n^2)的情况。 当然也可以使用STL的三点中值， 取整个序列的头、尾、中央三个位置的元素， 以其中值（median）作为基准数。 这个就是median-of-three partition

class solution{ 
    public: vector<int> sorrArray(vector<int>& nums){ 
    srand(time(0)); quicksort(nums, 0, nums.size()); return nums; } inline int partition(vector<int>& nums, int left, int right){ 
    int x = nums[right], i = left - 1; for(int j = left;j < right;++j){ 
    if(nums[j] <= x){ 
    swap(nums[++i], nums[j]); } } swap(nums[i+1], nums[right]); return i+1; } inline int randomParition(vector<int>& nums, int left, int right){ 
    int i = rand() % (right - left + 1) + left; swap(nums[i], nums[right]); return partition(nums, left , right); } void quicksort(vector<int>& nums, int left, int right) { 
    if(left < right) { 
    int location = randomPartition(nums, left, right); quicksort(nums, left, location-1); quicksort(nums, location+1, right); } } } 

如果随机化版本也是O(n^2)

在原始快排中， 如果输入的序列是正序的或者是逆序的， 那么它就会到达O(n^2)的时间复杂度， 于是我们是用来随机化算法， 来生成基准数。 但是即便是引入了随机化算法， 依旧有可能会到达O(n^2)。 这时候可以通过检查递归深度， 将之转换为堆排序。

根据数据量大小来使用快排

在STL中的sort算法， 数据量大是采用快速排序 ，分段递归排序；

一旦分段后的数据量小于某个门槛， 为避免快排的递归调用带来过大的额外负荷(会有额外空间消耗）， 就改用插入排序；

如果递归层次过深， 还会改用堆排序， 因为快排不稳定， 在数据量大的时候很有可能退化成O(n^2)的复杂度。

怎么看这个递归深度（怎么自我检测）

在SGI中， 是通过IntroSort来实现。 而Introsort可以通过判断递归深度来决定转化为堆排序

template <class RandomAccessIterator, class T, class Size> void __introsort_loop(RandomAccessIterator first, RandomAccessIterator last, T*, Size depth_limit) { 
    while(last - first > __stl_threshold) { 
    if(depth_limit == 0) //这时候， 可用的递归深度已经被用完了 { 
    partial_sort(first, last, last); return ; } --depth_limit; // 接下来是 median-of-3 partition ， 选择一个够好的枢轴并决定分裂点 RandomAccessIterator cut = __upguarded_partition(first, last, T(__median(*first, *(first + (last - first)/2), *(last- 1)))); // 对右半边递归进行sort __introsort_loop(cut, last, value_type(first), depth_limit); last = cut; //回到while循环， 准备对左半段递归进行sort } } // 其中的depth_limit的参数 template<class RandomAccessIterator> inline void sort(RandomAccessIterator first, RandomAccessIterator last) { 
    if(first != last) { 
    __introsort_loop(first, last, value_type(first), __lg(last-first)*2); __final_insertion_sort(first, last); } } 

其中控制分割恶化情况的就是

template <class Size> inline Size __lg(Size n) { 
    Size k; for(k = 0;n > 1;n >>= 1) ++k; return k; } // 当Size 为40， 2^5 <= 40; 所以当数据量为40的时候， 递归深度不能够超过5*2 = 10; 

多小的数据量使用插入排序

在STL中，其实5-20的区间内差别不大。 通常在这个区间内转化位插入排序

而插入排序在小数据量的时候相比于快排

• 没有额外的内存的申请和释放开销
• 没有递归栈的开销

为什么快排是不稳定的

稳定性指的是：两个值相同的元素在排序前后是否有位置变化。 如果前后位置变化， 排序算法是不稳定的， 否则是稳定的。

那为什么快排不稳定？为什么相同数值的元素会发送前后位置的变化。

原因：

1、 如果我们设置到bound（选定号的基数）它有相同的数值。 这就可以打乱顺序if(nums[i] <= x)。 但是并不是以相同的数值直接交换， 而是和比它大的值交换swap(nums[i+1], nums[rihgt]) 。而这个bound放到了相同数值的最后面。 (如果不使用随机化便可以避免这个问题)

2、 即便我们不是设置的bound没有相同的数值。 |lower|higher|unvisted| bound。 也就是说待排序的范围为(|lower|higher|unvisted| ) lower就是比bound小的值， higher是比bound大的值。 ‘

实例： |3 1 2|9 7 8 9 | 4 6 3 | 5， 当这时候遍历到了4。 那么9和4会进行交换变为 |3 1 2|4 7 8 9 9| 6 3 | 5 。这时候就发生了交换（4和9）之间。

// 在随机化后的快排， 我们把选中的数字放到排序区间的外面， 待排序区间为[left, right) inline int partition(vector<int>& nums, int left, int right){ 
    int x = nums[right], i = left - 1; for(int j = left;j < right;++j){ 
    if(nums[j] <= x){ 
    swap(nums[++i], nums[j]); } } swap(nums[i+1], nums[right]); return i+1; } 

快排的稳定版本

常规的快速排序算法是一个不稳定的算法， 也就是两个相等的数排序之后的顺序可能在原序列中的顺序不同。 那要实现一个稳定版本的快速排序可能吗？

思路：

1. 第一遍先把小于pivot的元素按照先后顺序放在tmp中。 然后把pivot放到它的正确位置tmp[k]。
2. 第二遍把大于pivot的元素按先后顺序放到tmp里。 这样处理pivot以前的其他元素， 都保持了和原序列中一样的顺序。
3. 第三遍把tmp赋值给原数组A

int stable_partition(vector<int>& nums, int left, int right) { 
    vector<int> tmp(right - left + 1); int pivot = nums[left]; int index = 0; for(int i = left+1;i < right+1;++i) { 
    if(nums[i] < pivot) { 
    tmp[index] = nums[i]; index = index + 1; } } tmp[index] = pivot; int position = index + left; index = index + 1; for(int i = left+1;i<right+1;++i) { 
    if(nums[i] >= pivot){ 
    tmp[index] = nums[i]; index = index + 1; } } index = 0; for(int i = left;i < right+1;++i) { 
    nums[i] = tmp[index]; ++index; } return position; } void quickSort(vector<int>& nums, int left, int right) { 
    if(left < right){ 
    int location = stable_partition(nums, left, right); quickSort(nums, left, location-1); quickSort(nums, location+1, right); } } vector<int> sortArray(vector<int>& nums) { 
    quickSort(nums, 0, nums.size()-1); return nums; } int main() { 
    vector<int> arr = { 
   3,1,2,9,7,8,9,4,6,3,5}; cout << arr.size() << endl; sortArray(arr); for(int i = 0; i <arr.size();++i) { 
    cout << arr[i]; } cout << endl; } 

当数据较小， 却又有较多的重复元素

**面对有大量重复元素的场景， 使用原始的快速排序， 会让时间复杂度退化成O(n^2) 。不管是当条件是大于等于还是小于等于v，**当数组中重复元素非常多的时候，等于v的元素太多，那么就将数组分成了极度不平衡的两个部分，因为等于v的部分总是集中在数组的某一边。

一种优化方式就是双路快排

由代码可以得知， 当i的元素小于v的时候继续向后扫描， 直到碰到某个元素大于等于v。 同理， 直到碰到某个元素小于等于v。

而后，只要交换i和j的位置就可以了， 然后i++, j–就行了。

/* * @Date: 2021-12-07 17:24:33 * @LastEditors: kafier * @LastEditTime: 2021-12-07 17:46:26 */ #include<iostream> #include <algorithm> #include <vector> using namespace std; template<typename T> int partition(vector<T>& arr, int left, int right) { 
    T pivot = arr[left]; int i , j; i = left + 1, j = right; while(true) { 
    while(arr[i] < pivot && i <= right) ++i; while(j>=left+1 && arr[j] > pivot) --j; if(i > j) { 
    break; } swap(arr[i], arr[j]); ++i; --j; } swap(arr[left], arr[j]); return j; } template <typename T> void __quickSort2(vector<T>& arr, int left, int right) { 
    if(left >= right) { 
    return; } int position = partition(arr, left, right); __quickSort2(arr, left, position-1); __quickSort2(arr, position+1, right); } template<typename T> void quickSort(vector<T>& arr, int n) { 
    __quickSort2(arr, 0, n-1); } int main() { 
    vector<int> arr = { 
   3,1,2,9,7,8,9,4,6,3,5}; cout << arr.size() << endl; // sortArray(arr); quickSort(arr, arr.size()); for(int i = 0; i <arr.size();++i) { 
    cout << arr[i]; } cout << endl; } 

三路快排

双路快排讲整个数组分成了小于v， 大于v的两部分， 而三路快排则是将数组分成了小于v， 等于v，大于v的三个部分。 当递归处理的时候， 遇到等于v的元素直接不用管， 只需处理小于v， 大于v的元素就好了

#include<iostream> #include<algorithm> using namespace std; t 

归并排序（重点）

基本思路

借助额外空间，合并两个有序数组， 得到更长的有序数组。（怎么合并两个有序数组， 去看合并两个有序数组

而后利用递归逐渐分解这个问题。

常规代码

排序数组

class MergeSolution { 
    public: vector<int> tmp; // 需要一个额外的数组来存储原数组 vector<int> sortArray(vector<int>& nums) { 
    tmp.resize((int)nums.size(), 0); mergeSort(nums, 0, (int)nums.size() - 1); return nums; } void mergeSort(vector<int>& nums, int left, int right) { 
    if(left >= right){ 
    return ; } int mid = left + (right - left)/2; mergeSort(nums, left, mid); mergeSort(nums, mid+1, right); int i = left, j = mid + 1; int cnt = 0; while(i <= mid && j <= right) { 
    if(nums[i] <= nums[j]) { 
    tmp[cnt++] = nums[i++]; } else{ 
    tmp[cnt++] = nums[j++]; } } // 如果右边的区间先被放完了 while(i <= mid){ 
    tmp[cnt++] = nums[i++]; } // 如果是左边的区间先被放完了 while(j <= right) { 
    tmp[cnt++] = nums[j++]; } for(int i = 0;i < right - left + 1;++i){ 
    nums[i+left] = tmp[i]; } } }; 

#include<iostream> using namespace std; void Merge(int arr[], int l, int q, int r){ 
    int n=r-l+1;//临时数组存合并后的有序序列 int* tmp=new int[n]; int i=0; int left=l; int right=q+1; while(left<=q && right<=r) tmp[i++] = arr[left]<= arr[right]?arr[left++]:arr[right++]; while(left<=q) tmp[i++]=arr[left++]; while(right<=r) tmp[i++]=arr[right++]; for(int j=0;j<n;++j) arr[l+j]=tmp[j]; delete [] tmp;//删掉堆区的内存 } void MergeSort(int arr[], int l, int r){ 
    if(l==r) return; //递归基是让数组中的每个数单独成为长度为1的区间 int q = (l + r)/2; MergeSort(arr, l, q); MergeSort(arr, q + 1, r); Merge(arr, l, q, r); } int main(){ 
    int a[8] = { 
   3,1,2,4,5,8,7,6}; MergeSort(a,0,7); for(int i=0;i<8;++i) cout<<a[i]<<" "; } 

经典归并排序题目

合并两个有序数组 其实Merge这个函数所做之事（使用双指针）

数组中的逆序对

计算右侧小于当前元素的个数

数组中的逆序对

归并排序分为三个步骤

• 分解： 将待排序的区间为[l, r]， 令 m = [l+r/2], 我们把[l, r]分成[l, m]和[m+1, r]
• 解决： 使用归并排序递归地排序两个子序列
• 合并：把两个排好序的子序列[l, m]和[m+1, r]合并起来

逆序对和归并排序的关系

关键在于【归并】中的【并】的过程。

L = [8, 12, 16, 22, 100] R = [9, 26, 55, 64, 91] M = [8, 9] | | lPtr rPtr 

现在要考虑12这个lptr的贡献值。 因为之前的rptr(9)比12小， 所以12和9构成了逆序对。

这个贡献就是rptr相对R首位置的偏移(即右边只有一个数比12小， 所以只有它和12构成了逆序对）。

这种【算贡献】的思想在合并的过程中计算逆序对的数量的时候， 只能在lptr右移的时候计算。

是基于这样的事实 ： 当前lptr指向的数组比rptr小，但是比R中[0 ... rptr-1]的其他数字大， [0 .. rptr-1]的其他数字应该排在lptr对应数字的左边。但是比R中[0 ... rptr - 1]的其他数字大。 [0 .. rptr -1]的其他数字应该排在lptr对应的数字左边。 但是它排在了右边。 所以可以贡献rptr个逆序对

class Solution { 
    public: int reversePairs(vector<int>& nums) { 
    int n = nums.size(); vector<int> tmp(n); return mergeSort(nums, tmp, 0, n-1); } int mergeSort(vector<int>& nums, vector<int> &tmp, int left, int right) { 
    if(left >= right){ 
    return 0; } int mid = left + (right - left) / 2; int inv_cnt = mergeSort(nums, tmp, left, mid) + mergeSort(nums, tmp, mid+1, right); int i=left, j = mid+1, cnt = left; while(i <= mid && j<=right) { 
    if(nums[i] <= nums[j]) //这个是一个要格外注意的点。 即便是 nums[i] == nums[j]， 也可以进行清算 { 
    tmp[cnt++] = nums[i++]; inv_cnt += (j-(mid+1)); } else{ 
    tmp[cnt++] = nums[j++]; } } while(i <= mid) { 
    tmp[cnt++] = nums[i++]; inv_cnt += (j-(mid+1)); } while(j <= right) { 
    tmp[cnt++] = nums[j++]; } copy(tmp.begin() + left, tmp.begin() + right +1, nums.begin() + left); return inv_cnt; } }; 

堆排序

堆的定义

• 堆是一个完全二叉树， 因此堆也被称为二叉堆
• 堆中节点的值都大于等于其子节点的值（大顶堆） 或者小于等于其子节点的值（小顶堆）

堆的底层如何表示？

堆是一颗完全二叉树， 可以使用数组来表示。而完全二叉树除了叶子节点的部分， 就是满二叉树， 也就是只有叶子节点没必要是满的。

如果根节点为 i， 那么左节点为2i， 右节点为2i + 1（这是针对其实元素是从1开始的） ，如果是从0开始， 那么左节点为 2 * i +1, 右节点为2*i + 2。

删除堆顶元素可能会产生的问题（数组空洞）

假设操作的堆是大顶堆， 则删除堆顶元素， 要找到原堆中第二大的元素来填补堆顶元素， 第二大的元素无疑是在根节点中的左右节点当中， 假设是左节点， 则用左节点来填补堆顶元素， 左节点就空了， 之后的过程就是进行不断地循环。

但是在调整的过程中， 会产生数组空洞， 如图
解决方案： 用最后一个元素覆盖堆顶元素， 然后再自上而下调整堆， 让其满足大顶堆的要求， 就可以解决数组空洞的问题。
因为将堆顶元素和最后一个元素进行了交换。 再自上而下地去调整堆， 就可以避免数组空洞问题

堆排序思想

• 堆排序可以说是选择排序的优化， 选择排序需要在未排定的部分通过【打擂台】的方式选出最大的元素， 而【堆排序】将未排定的部分构建成了一个堆。 这样就可以以O(logN)的方式选出最大元素。
• 堆是建立在数组上的【树】结构。 其中有最大堆， 最小堆， 规则也很简单（最大堆， 父节点比子节点的值大）

class HeapSolution { 
    public: vector<int> sortArray(vector<int>& nums) { 
    heapSort(nums); return nums; } void maxHeapify(vector<int>& nums, int i, int len) { 
    // (i<<1) == i*2 while((i<<1)+1 <= len) { 
    int lson = (i<<1) + 1; int rson = (i<<1) + 2; int large; // 如果i的左子节点大于根节点 large = lson, 否则 large = i if(lson <= len && nums[lson] > nums[i]) { 
    large = lson; } else{ 
    large = i; } //如果右节点比现在（根节点和左节点）都要大， large = rson if(rson <= len && nums[rson] > nums[large]) { 
    large = rson; } // 根节点不大。  if(large != i) { 
    swap(nums[i], nums[large]); i = large; } else{ 
    break; } } } void buildMaxHeap(vector<int>& nums, int len) { 
    // 如果有n个节点， 由二叉树的性质。假设最后一层的节点的数量为k， 那么上层的节点为 k/2 + k/4+ .. + 1， 化为等差数列可以得到k-1 // 所以二叉树的一半 + 1就是叶子节点的数量 // 那么第一个非叶子节点的索引就是 (len - 1)/2; for(int i = len/2; i>=0;--i) { 
    maxHeapify(nums, i, len); } } void heapSort(vector<int>& nums) { 
    // 循环不变量：区间[0,i]堆有序 int len = (int)nums.size() - 1; buildMaxHeap(nums, len); // 把堆顶元素（当前最大）交换到数组末尾 for(int i = len;i >= 1;--i) { 
    swap(nums[i], nums[0]); // 减少堆有序的部分 len -=1; maxHeapify(nums, 0, len); } } }; 

堆的时间复杂度分析

堆的排序分为两步， 即初始化堆， 调整堆

两个步骤都需要调用一个调整节点顺序的函数NodeSort， 以大根堆为例。

1. 如果父亲节点num[a]， 和它的两个孩子节点nums[2a+1] , nums[2a+2]满足， nums[a] > max{nums[2a+1], nums[2a+2]} ， 那么返回
2. 如果不满足堆的性质， 那么将父亲节点nums[a] 和 较大孩子节点max{nums[2a+1], nums[2a+2]}交换。
3. 将原来较大节点的孩子节点作为父亲节点，重复上述操作， 知道孩子节点是叶子节点为止

初始化堆的时间复杂度分析

设元素个数为n， 堆的高度为 K = log(n + 1) = log(n)， 非 叶子节点的个数为 2^(k-1) -1

假设每个非叶子节点都需要调整， 第i层的非叶子节点 需要操作的次数为k – i

第i层共有 2^(i-1)个节点， 第i层的所有节点所做的操作为k* 2 ^ (i-1) - i*2^(i-1)， 总共k-1层非叶子节点， 总的操作次数为

$$\sum _{i=1}^{k-1}(k\ast 2^{i-1}-i\ast 2^{i-1})=\sum _{i=1}^{k-1}(k-i)(2^{i-1})=2^k-k+1$$

将k = log(n)代入， 那么得到$$n-log(n)+1$$

所以， 初始化堆的复杂度为O(n)

调整堆的时间复杂度分析

假设根节点和排到最后序号为m的叶子节点交换， 并进行调整， 那么调整的次数 = 原来m节点所在的层数 = 堆的高度

共n个节点。 调整的总次数为$$\sum _{m-1}^{n-1}log(m)$$

化简得到$$log(n-1)!=n\ast log(n)$$

所以调整堆的时间复杂度为 $$n\ast log(n)$$

今天的文章
排序算法快速排序_快速排序稳定吗分享到此就结束了，感谢您的阅读。