STL六大組件中算法模塊sort為啥采用快速排序作為底層思想

森明幫大於黑虎幫 2021-09-20 04:51:45 阅读数:493

stl 六大 算法 sort 采用

一、面試官發問sort底層采用什麼排序

當你第一眼看到這道面試題是不是心裏在暗喜,一問算法題就比問排序算法,一問排序算法就問快速排序。

如果你回答:

STL裏的sort算法肯定用的是快速排序啊?難不成還是冒泡排序麼?

如果你只是回答快速排序,那麼恭喜你只答對了33.333%,離正確答案還差一大截。

回答完,接著會引來一堆問題轟炸:

  • 數據量大和數據量小都適合用快速排序嗎?
  • 快速排序的時間複雜度不是穩定的nlogn,最壞情况會變成n^2,怎麼解决複雜度惡化問題?
  • 快速排序遞歸實現時,怎麼解决遞歸層次過深的問題?
  • 遞歸過深會引發什麼問題?
  • 怎麼控制遞歸深度?如果達到遞歸深度了還沒排完序怎麼辦?

首先,回答用到哪種排序算法,正確答案是:

毫無疑問是用到了快速排序,但不僅僅只用了快速排序,還結合了插入排序和堆排序。

是不是很驚喜,很意外?

為什麼?直接看STL源碼實現,來源於侯捷大佬翻譯的鼎鼎大名的《STL源碼剖析》關於sort算法實現的細節,實現細節有很多精彩的地方。

並非所有容器都使用sort算法:

既然問的是STL的sort算法實現,那麼先確認一個問題,哪些STL容器需要用到sort算法?

首先:關系型容器擁有自動排序功能,因為底層采用RB-Tree,所以不需要用到sort算法。
其次:序列式容器中的stack、queue和priority-queue都有特定的出入口,不允許用戶對元素排序。
最後: 剩下的vector、deque,適用sort算法。

實現邏輯:

STL的sort算法,數據量大時采用QuickSort快排算法,分段歸並排序。一旦分段後的數據量小於某個門檻(16),為避免QuickSort快排的遞歸調用帶來過大的額外負荷,就改用Insertion Sort插入排序。如果遞歸層次過深,還會改用HeapSort堆排序。
在這裏插入圖片描述
結合快速排序-插入排序-堆排序 三種排序算法。

思考:

1.為什麼對於區間小於16的采用插入排序,如果遞歸深度惡化改用堆排序?

插入排序對於基本有序或數據較少的序列很高效。

堆排序的時間複雜度固定為O(nlogn),不需要再遞歸下去了。

2.那堆排序既然也是O(nlogn)直接用堆排序實現sort不行嗎?為啥用快速排序實現?

第一點:堆排序數據訪問的方式沒有快速排序友好。對於快速排序來說,數據是順序訪問的。而對於堆排序來說,數據是跳著訪問的。 比如,堆排序中,最重要的一個操作就是數據的堆化。比如下面這個例子,對堆頂節點進行堆化,會依次訪問數組下標是 1,2,4,8 的元素,而不是像快速排序那樣,局部順序訪問,所以,這樣對 CPU 緩存是不友好的。

第二點:對於同樣的數據,在排序過程中,堆排序算法的數據交換次數要多於快速排序。我們在講排序的時候,提過兩個概念,有序度和逆序度。對於基於比較的排序算法來說,整個排序過程就是由兩個基本的操作組成的,比較和交換(或移動)。快速排序數據交換的次數不會比逆序度多。

二、三種遞歸實現和非遞歸實現代碼如下:

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
int QuickSort1(int* arr, int begin, int end) //左右指針法
{

if (begin >= end)
{

return arr[begin];
}
int key = arr[begin];
int left = begin;
int right = end;
while (left < right)
{

while (left < right&&arr[right] >= key)
{

right--;
}
while (left < right&&arr[left] <= key)
{

left++;
}
std::swap(arr[left], arr[right]);
}
int meet = left;
return meet;
}
int QucikSort2(int* arr, int begin, int end) //挖坑法
{

if (begin >= end)
{

return arr[begin];
}
int key = arr[begin];
int left = begin;
int right = end;
while (left < right)
{

while (left < right&&arr[right] >= key)
{

right--;
}
arr[left] = arr[right];
while (left < right&&arr[left] <= key)
{

left++;
}
arr[right] = arr[left];
}
int meet = left;
arr[meet] = key ;
return meet;
}
int QuickSort3(int* arr, int begin, int end)
{

if (begin >= end)
{

return arr[begin];
}
int prev = begin;
int cur = begin + 1;
int key = arr[begin];
while (cur <= end)
{

if (arr[cur] < key && (++prev) != cur)
{

std::swap(arr[cur], arr[prev]);
}
cur++;
}
int meet = prev;
std::swap(arr[prev], key);
return meet;
}
int PartSort(int* arr, int begin, int end)
{

if (begin >= end)
{

return arr[begin];
}
int meet = QuickSort1(arr, begin, end);
PartSort(arr, begin, meet - 1);
PartSort(arr, meet + 1, end);
}
void QucikSortNonR(int* arr, int begin, int end)
{

stack<int> st;
st.push(begin);
st.push(end);
while (!st.empty())
{

int left = 0;
int right = 0;
right = st.top();
st.pop();
left = st.top();
st.pop();
int key = QuickSort1(arr, begin, end);
if (left < key - 1)
{

st.push(left);
st.push(key - 1);
}
if (key + 1 < right)
{

st.push(key);
st.push(right);
}
}
}

三、快速排序的優化方法之三數取中

三數取中。在最左端、最右端和中間三個數中選取中數作為key值,這樣key值比特於較為中間的值的可能性就大大提高。
在這裏插入圖片描述
在這裏插入圖片描述

//三數取中
int getMid(int *arr, int left, int right)
{

int mid = left + (right - left) / 2;
if (arr[mid] > arr[left])
{

if (arr[mid] < arr[right])
{

return mid;
}
else if (arr[left]>arr[right])
{

return left;
}
else
{

return right;
}
}
else
{

if (arr[mid] > arr[right])
{

return mid;
}
else if (arr[left] < arr[right])
{

return left;
}
else
{

return right;
}
}
}

四、快速排序的時間和空間複雜度

在這裏插入圖片描述

版权声明:本文为[森明幫大於黑虎幫]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210920045145183p.html