C++快速排序及優(yōu)化方案詳解
1. 快速排序的流程
- 首先設定一個分界值，通過該分界值將數組分成左右兩部分。
- 將大于分界值的數據集中到數組右邊，小于分界值的數據集中到數組的左邊，而等于分分界值的部分放在相對中間的部分。此時，左邊部分中各元素都小于分界值，而右邊部分中各元素都大于分界值，相對中間的部分的的數據等于分界值。
- 然后，左邊和右邊的數據可以獨立排序。對于左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。
- 重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序后，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成后，整個數組的排序也就完成了。
2. 快速排序的實現
原始的快速排序相對來說會比較熟悉點，大致的部分流程圖如圖所示：
直接上代碼：
#include<iostream>
#include<string>
#include<vector>
#include<time.h>
using namespace std;
//三色旗原理代碼部分
pair<int, int> Quick(vector<int>& vec, int L, int R)
{
int temp = vec[L];//基準值
int i = L - 1;//左邊界
int j = R + 1;//右邊界
int index = L;//交換變量
while (index < j)
{
if (vec[index] < temp)
{
swap(vec[index++], vec[++i]);
}
else if (vec[index] > temp)
{
swap(vec[index], vec[--j]);
}
else
{
index++;
}
}
pair<int, int> p = make_pair(i, j);//存儲下次排序的左右邊界，
return p;
}
void Quick_sort(vector<int>& vec, int L, int R)
{
if (L >= R)return;//遞歸結束的標志
pair<int, int> p = Quick(vec, L, R);
Quick_sort(vec, L, p.first);//將數組的左部分進行排序
Quick_sort(vec, p.second, R);//將數組的右部分進行排序
}
int main()
{
vector<int> vec = { 5,6,3,7,2,8 };
Quick_sort(vec, 0, vec.size() - 1);
for (auto it : vec)
{
cout << it << " ";
}
return 0;
}時間復雜度計算
快速排序的最優(yōu)的情況時的時間復雜度為O(N*logN) 因為最優(yōu)解在排序過程中每次都利用遞歸將數組不斷二分，并且不斷二分過程次相當于二分法，而二分的時間復雜度為logN（這里的log是以2為底的），每次二分的各個子數組的和均為n個元素，在排序過程中所有元素在不同的遞歸過程中均會被遍歷比較，所以每次都會有N個元素會被遍歷，即時間復雜度為：O(N*logN) 最壞的情況時的時間復雜度為O(N^2) 這種情況是當數組有序的情況下，每次基準值都是取了數組中的最小值或最大值，而且每次遞歸都只是排除了基準值那個元素，這里就很像冒泡排序不斷將子數組中最值排除掉，而冒泡排序的時間復雜度為O（N^2）。 因此最壞情況下的時間復雜度為O（N^2）。
3. 快速排序優(yōu)化
3.1 隨機獲取基準值進行優(yōu)化
上一節(jié)我們自己動手寫的一個快速排序的算法，在進行毫無規(guī)則的數組排序過程中表現得非常好，但是，當我們去百萬，十萬級別量的數據進行排序并且高度的有序化時，我們會發(fā)現此時程序運行的過程中，發(fā)現快速排序的效率變得異常的低下，會比相同數據量的數組中的數據是毫無規(guī)則時效率低得多了，近似退回了O（n^2）的復雜度，而此時程序則需要等待非常長的時間才能執(zhí)行完全。 在編寫快排代碼的過程中，我們是利用遞歸來對數組進行劃分的，這和歸并排序里面的利用遞歸使得不斷的二分才能達到O（n*logn）的時間復雜度相似，在快速排序中最好的情況就是如同歸并一樣，每次都是二分，這種情況的時間復雜度是最佳的時間復雜度O（n*logn）。如圖：
但是當數組高度有序化或者數組本來就是有序的時候，這個時候數組數據呈現出一邊倒的趨勢此時快速排序的時間復雜度達到最壞的情況逼近O（n^2） 甚至達到為O（n^2），這樣的快速排序遠遠達不到我們的需求，如圖：
在這種情況下我們可以通過隨機獲取每次排序的基準值來進行優(yōu)化int temp = vec[rand()%(R-L+1)+L];，同時通過百萬、十萬級別量的數據量來計算程序運行的時間比較時間復雜度。
計算時間的代碼如下：
clock_t startime, endtime;
startime = clock();
....//中間代碼
endtime = clock();
cout << (double)(endtime - startime)/ CLOCKS_PER_SEC << endl;
通過隨機獲取基準值優(yōu)化代碼如下：
#include<iostream>
#include<string>
#include<vector>
#include<time.h>
using namespace std;
//三色旗原理代碼部分
pair<int, int> Quick(vector<int>& vec, int L, int R)
{
int temp = vec[rand()%(R-L+1)+L];//隨機獲取基準值進行優(yōu)化
//int temp = vec[L];//沒有獲取隨機基準值
int i = L - 1;//左邊界
int j = R + 1;//右邊界
int index = L;//交換變量
while (index < j)
{
if (vec[index] < temp)
{
swap(vec[index++], vec[++i]);
}
else if (vec[index] > temp)
{
swap(vec[index], vec[--j]);
}
else
{
index++;
}
}
pair<int, int> p = make_pair(i, j);//存儲下次排序的左右邊界，
return p;
}
void Quick_sort(vector<int>& vec, int L, int R)
{
if (L >= R)return;//遞歸結束的標志
pair<int, int> p = Quick(vec, L, R);
Quick_sort(vec, L, p.first);//將數組的左部分進行排序
Quick_sort(vec, p.second, R);//將數組的右部分進行排序
}
int main()
{
clock_t startime, endtime;
startime = clock();//開始時間
vector<int> vec;
for (int i = 0; i < 100000; i++) {
//(在這里使用十萬級別的數據量 完全有序的數組進行計算時間復雜度 百萬級別的數據量由于程序執(zhí)行時間太長 不例舉)
vec.push_back(i);
}
Quick_sort(vec, 0, vec.size() - 1);
/*for (auto it : vec)//在這里不進行輸出，數據量太大
{
cout << it << " ";
}*/
endtime = clock();//結束時間
cout << (double)(endtime - startime)/ CLOCKS_PER_SEC << endl;
//在這里沒有定義單位，只通過數值進行比較來判斷
return 0;
}此時沒有經過優(yōu)化的代碼執(zhí)行時間如圖：
經過優(yōu)化的代碼執(zhí)行時間如圖：
兩者相對比較而言進行優(yōu)化的時間復雜度遠遠小于未經過優(yōu)化的。但是在數組里面的數據是亂序的情況下，經過優(yōu)化的時間復雜度會偶爾出現略高于未經過優(yōu)化的情況，但影響并不是很大。
3.2二路快速排序
接著前面所介紹來說，當我們排序的是一個近乎有序的序列時，快速排序會退化到一個O(n^2) 級別的排序算法，而我們對此的就是引入了隨機化快速排序算法；但是問題又來了，當我們排序的數據是一個數值重復率非常高的序列時，或者是輸入的數據完全相同的情況時，此時隨機化快速排序算法就不再起作用了，而將會再次退化為一個O(n^2) 級別的排序算法。 在這種情況下不管是>=temp還是<=temp，當我們的序列中存在大量重復的元素時，排序完成之后就會將整個數組序列分成兩個極度不平衡的部分,甚至更惡劣的情況是所有數據均一樣而出現一邊倒的趨勢，所以又退化到了O(n^2) 級別的時間復雜度，這是因為對于每一個"基準"元素來說，重復的元素太多了，如果我們選的"基準"元素稍微有一點的不平衡，那么就會導致兩部分的差距非常大；即時我們的"基準"元素選在了一個平衡的位置，但是由于等于"基準"元素的元素也非常多，也會使得序列被分成兩個及其不平衡的部分，那么在這種情況下快速排序就又會退化成O(n^2) 級別的排序算法。 在這里我們可以使用二路快速排序進行優(yōu)化。
原理：
前面所敘述的快速排序算法是將>temp和<temp兩個部分元素都放在索引值i所指向的位置的左邊部分，而雙路快速排序則是使用兩個索引值（i、j）用來遍歷我們的序列，將<temp的元素放在索引 i 所指向位置的左邊，而將>temp的元素放在索引j所指向位置的右邊。
思想：
1、首先從左邊的i索引往右邊遍歷，如果i指向的元素<temp，那直接將i++移動到下一個位置，直道i指向的元素>=temp則停止。
2、然后使用j索引從右邊開始往左邊遍歷，如果j指向的元素>temp，那直接將j–移動到下一個位置，直道j指向的元素<=temp則停止
3、此時i之前的元素都已經歸并為<temp的部分了，而j之后的元素也都已經歸并為>temp的部分了，此時只需要將vec[i]和vec[j]交換位置即可。這樣就可以避免出現=temp的元素全部集中在某一個部分，這正是雙路排序算法的一個核心。但是當需要排序的數據長度比較小時，此時使用插入排序的性能比較好，所以我們結合快速排序和插入排序進行一個優(yōu)化快速排序。
具體實現代碼：
#include<iostream>
#include<vector>
#include<time.h>
using namespace std;
void Insert_sort(vector<int>& vec,int L,int R) {
for (int i = L+1; i < R; i++) {//用i來記錄無序表的第一個值的下標
int j = i - 1;//用來記錄前面有序列的最后一個值的下標
int temp = vec[i];//記錄無序列的第一個值的值
for (; j >= 0; j--) {
if (vec[j] > temp) {
vec[j + 1] = vec[j];//將有序表中的元素后移。
}
else {
break;//當無序表中的第一個值不比有序表中的最后一個值小時，跳出循環(huán)
}
}
vec[j + 1] = temp;//將后移后的空值補上無序表中的第一個值。
}
}
int qucikSort(vector<int>& vec, int L, int R)
{
swap(vec[L], vec[rand() % (R - L + 1) + L]);// 隨機產生"基準"元素所在位置，并與第一個元素交換位置
int temp = vec[L]; // 將第一個元素作為"基準"元素
// 使用i索引從左到右遍歷，使用j索引從右到左遍歷
int i = L + 1;// 索引值i初始化為第二個元素位置
int j = R;// 索引值j初始化為最后一個元素位置
while (true) {
while ((i < R) && (vec[i] < temp)) i++;// 使用索引i從左往右遍歷直到 vec[i] < temp
while ((j > L + 1) && (vec[j] > temp)) j--;// 使用索引j從右往左遍歷直到 vec[j] > temp
if (i >= j) break;// 退出循環(huán)的條件
swap(vec[i], vec[j]);// 將 vec[i] 與 vec[j] 交換位置
i++;
j--;
}
swap(vec[L], vec[j]);// 最后將"基準"元素temp放置到合適的位置
return j;
}
void quick(vector<int>& vec, int L, int R)
{
if (R - L <= 40) {//當數據量比較小時我們采用插入排序進行
Insert_sort(vec, L, R);
return;
}
int p = qucikSort(vec, L, R);// 對vec[left...right]區(qū)間元素進行排序操作，找到"基準"元素
quick(vec, L, p - 1);// 對基準元素之前的序列遞歸
quick(vec, p + 1, R);// 對基準元素之后的序列遞歸
}
int main()
{
clock_t startime, endtime;
startime = clock();//開始時間
vector<int> vec;
srand(time(0));
for (int i = 0; i < 100000; i++) {
//(在這里使用十萬級別的數據量，完全有序的數組進行計算時間復雜度
// 百萬級別的數據量由于程序執(zhí)行時間太長，不例舉)
vec.push_back(rand()%100);
}
quick(vec, 0, vec.size() - 1);
//for (auto it : vec)//在這里不進行輸出，數據量太大
//{
// cout << it << " ";
//}
endtime = clock();//結束時間
cout << (double)(endtime - startime) / CLOCKS_PER_SEC << endl;
//在這里沒有定義單位，只通過數值進行比較來判斷
return 0;
}在這里隨機數產生的數據進行性能分析，如圖第一個數據是未經過優(yōu)化的時執(zhí)行一個利用隨機生成數亂序并且重復率較高的執(zhí)行時間，第二個數據是二路快速排序的執(zhí)行時間。在這里執(zhí)行時間相差不多是因為這里我們難以得到一個重復率非常高的一組數據，但是實際上雙路快速排序優(yōu)化的結果還是比較理想的。
4. 總結
在上述優(yōu)化的過程中， 對于原始的快排來說，當重復率低，并且數組的有序化低是具有很好的效率，但是在應對大量的規(guī)則性比較強的數據時，效率是跟不上。而隨機快速排序只是獲取了一個隨機基準值來應對數據有序化程度比較高的情況下來進行優(yōu)化。但是二路快速排序結合了隨機快排和插入排序來應對能夠出現的所有情況來 達到比較好的效果。
到此這篇關于C++快速排序及優(yōu)化方案詳解的文章就介紹到這了,更多相關C++快速排序及優(yōu)化內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了C語言實現通訊錄，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
今天小編就為大家分享一篇關于C語言中函數指針與軟件設計經驗總結，小編覺得內容挺不錯的，現在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要介紹了VSCode插件開發(fā)全攻略之命令、菜單、快捷鍵,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-05-05
這篇文章主要為大家詳細介紹了C語言實現最全自動售貨機，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
這篇文章主要介紹了linux中查詢dns示例,需要的朋友可以參考下2014-04-04
本篇文章是對C++全局變量的聲明與定義進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要為大家詳細介紹了linux環(huán)境下C++實現俄羅斯方塊，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-06-06
如何使用visual studio2019創(chuàng)建簡單的MFC窗口(使用C++)
這篇文章主要介紹了如何使用visual studio2019創(chuàng)建簡單的MFC窗口(使用C++)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-03-03
這篇文章主要為大家總結了C++中輸入輸出流及文件流操作,具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-10-10
本篇文章是對C語言的指令進行了詳細的分析與介紹，需要的朋友參考下2013-05-05