1. 快速排序的流程

1. 首先設(shè)定一個(gè)分界值，通過(guò)該分界值將數(shù)組分成左右兩部分。
2. 將大于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊，而等于分分界值的部分放在相對(duì)中間的部分。此時(shí)，左邊部分中各元素都小于分界值，而右邊部分中各元素都大于分界值，相對(duì)中間的部分的的數(shù)據(jù)等于分界值。
3. 然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類(lèi)似處理。
4. 重復(fù)上述過(guò)程，可以看出，這是一個(gè)遞歸定義。通過(guò)遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當(dāng)左、右兩個(gè)部分各數(shù)據(jù)排序完成后，整個(gè)數(shù)組的排序也就完成了。

2. 快速排序的實(shí)現(xiàn)

原始的快速排序相對(duì)來(lái)說(shuō)會(huì)比較熟悉點(diǎn)，大致的部分流程圖如圖所示：

直接上代碼：

#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];//基準(zhǔn)值
	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);//存儲(chǔ)下次排序的左右邊界，
	return p;
}
void Quick_sort(vector<int>& vec, int L, int R)
{
	if (L >= R)return;//遞歸結(jié)束的標(biāo)志
	pair<int, int> p = Quick(vec, L, R);
	Quick_sort(vec, L, p.first);//將數(shù)組的左部分進(jìn)行排序
	Quick_sort(vec, p.second, R);//將數(shù)組的右部分進(jìn)行排序
}
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;
}

時(shí)間復(fù)雜度計(jì)算

快速排序的最優(yōu)的情況時(shí)的時(shí)間復(fù)雜度為O(N*logN) 因?yàn)樽顑?yōu)解在排序過(guò)程中每次都利用遞歸將數(shù)組不斷二分，并且不斷二分過(guò)程次相當(dāng)于二分法，而二分的時(shí)間復(fù)雜度為logN（這里的log是以2為底的），每次二分的各個(gè)子數(shù)組的和均為n個(gè)元素，在排序過(guò)程中所有元素在不同的遞歸過(guò)程中均會(huì)被遍歷比較，所以每次都會(huì)有N個(gè)元素會(huì)被遍歷，即時(shí)間復(fù)雜度為：O(N*logN) 最壞的情況時(shí)的時(shí)間復(fù)雜度為O(N^2) 這種情況是當(dāng)數(shù)組有序的情況下，每次基準(zhǔn)值都是取了數(shù)組中的最小值或最大值，而且每次遞歸都只是排除了基準(zhǔn)值那個(gè)元素，這里就很像冒泡排序不斷將子數(shù)組中最值排除掉，而冒泡排序的時(shí)間復(fù)雜度為O（N^2）。 因此最壞情況下的時(shí)間復(fù)雜度為O（N^2）。

3. 快速排序優(yōu)化

3.1 隨機(jī)獲取基準(zhǔn)值進(jìn)行優(yōu)化

上一節(jié)我們自己動(dòng)手寫(xiě)的一個(gè)快速排序的算法，在進(jìn)行毫無(wú)規(guī)則的數(shù)組排序過(guò)程中表現(xiàn)得非常好，但是，當(dāng)我們?nèi)グ偃f(wàn)，十萬(wàn)級(jí)別量的數(shù)據(jù)進(jìn)行排序并且高度的有序化時(shí)，我們會(huì)發(fā)現(xiàn)此時(shí)程序運(yùn)行的過(guò)程中，發(fā)現(xiàn)快速排序的效率變得異常的低下，會(huì)比相同數(shù)據(jù)量的數(shù)組中的數(shù)據(jù)是毫無(wú)規(guī)則時(shí)效率低得多了，近似退回了O（n^2）的復(fù)雜度，而此時(shí)程序則需要等待非常長(zhǎng)的時(shí)間才能執(zhí)行完全。 在編寫(xiě)快排代碼的過(guò)程中，我們是利用遞歸來(lái)對(duì)數(shù)組進(jìn)行劃分的，這和歸并排序里面的利用遞歸使得不斷的二分才能達(dá)到O（n*logn）的時(shí)間復(fù)雜度相似，在快速排序中最好的情況就是如同歸并一樣，每次都是二分，這種情況的時(shí)間復(fù)雜度是最佳的時(shí)間復(fù)雜度O（n*logn）。如圖：

但是當(dāng)數(shù)組高度有序化或者數(shù)組本來(lái)就是有序的時(shí)候，這個(gè)時(shí)候數(shù)組數(shù)據(jù)呈現(xiàn)出一邊倒的趨勢(shì)此時(shí)快速排序的時(shí)間復(fù)雜度達(dá)到最壞的情況逼近O（n^2） 甚至達(dá)到為O（n^2），這樣的快速排序遠(yuǎn)遠(yuǎn)達(dá)不到我們的需求，如圖：

在這種情況下我們可以通過(guò)隨機(jī)獲取每次排序的基準(zhǔn)值來(lái)進(jìn)行優(yōu)化int temp = vec[rand()%(R-L+1)+L];，同時(shí)通過(guò)百萬(wàn)、十萬(wàn)級(jí)別量的數(shù)據(jù)量來(lái)計(jì)算程序運(yùn)行的時(shí)間比較時(shí)間復(fù)雜度。

計(jì)算時(shí)間的代碼如下：

clock_t startime, endtime;
	startime = clock();
    ....//中間代碼
	endtime = clock();
	cout << (double)(endtime - startime)/ CLOCKS_PER_SEC << endl;

通過(guò)隨機(jī)獲取基準(zhǔn)值優(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];//隨機(jī)獲取基準(zhǔn)值進(jìn)行優(yōu)化
	//int temp = vec[L];//沒(méi)有獲取隨機(jī)基準(zhǔn)值
	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);//存儲(chǔ)下次排序的左右邊界，
	return p;
}
void Quick_sort(vector<int>& vec, int L, int R)
{
	if (L >= R)return;//遞歸結(jié)束的標(biāo)志
	pair<int, int> p = Quick(vec, L, R);
	Quick_sort(vec, L, p.first);//將數(shù)組的左部分進(jìn)行排序
	Quick_sort(vec, p.second, R);//將數(shù)組的右部分進(jìn)行排序
}
int main()
{
	clock_t startime, endtime;
	startime = clock();//開(kāi)始時(shí)間
	vector<int> vec;
	for (int i = 0; i < 100000; i++) {
	//(在這里使用十萬(wàn)級(jí)別的數(shù)據(jù)量 完全有序的數(shù)組進(jìn)行計(jì)算時(shí)間復(fù)雜度 百萬(wàn)級(jí)別的數(shù)據(jù)量由于程序執(zhí)行時(shí)間太長(zhǎng) 不例舉)
		vec.push_back(i);
	}
	Quick_sort(vec, 0, vec.size() - 1);
	/*for (auto it : vec)//在這里不進(jìn)行輸出，數(shù)據(jù)量太大
	{
		cout << it << " ";
	}*/
	endtime = clock();//結(jié)束時(shí)間
	cout << (double)(endtime - startime)/ CLOCKS_PER_SEC << endl;
	//在這里沒(méi)有定義單位，只通過(guò)數(shù)值進(jìn)行比較來(lái)判斷
	return 0;
}

此時(shí)沒(méi)有經(jīng)過(guò)優(yōu)化的代碼執(zhí)行時(shí)間如圖：

經(jīng)過(guò)優(yōu)化的代碼執(zhí)行時(shí)間如圖：

兩者相對(duì)比較而言進(jìn)行優(yōu)化的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)小于未經(jīng)過(guò)優(yōu)化的。但是在數(shù)組里面的數(shù)據(jù)是亂序的情況下，經(jīng)過(guò)優(yōu)化的時(shí)間復(fù)雜度會(huì)偶爾出現(xiàn)略高于未經(jīng)過(guò)優(yōu)化的情況，但影響并不是很大。

3.2二路快速排序

接著前面所介紹來(lái)說(shuō)，當(dāng)我們排序的是一個(gè)近乎有序的序列時(shí)，快速排序會(huì)退化到一個(gè)O(n^2) 級(jí)別的排序算法，而我們對(duì)此的就是引入了隨機(jī)化快速排序算法；但是問(wèn)題又來(lái)了，當(dāng)我們排序的數(shù)據(jù)是一個(gè)數(shù)值重復(fù)率非常高的序列時(shí)，或者是輸入的數(shù)據(jù)完全相同的情況時(shí)，此時(shí)隨機(jī)化快速排序算法就不再起作用了，而將會(huì)再次退化為一個(gè)O(n^2) 級(jí)別的排序算法。 在這種情況下不管是>=temp還是<=temp，當(dāng)我們的序列中存在大量重復(fù)的元素時(shí)，排序完成之后就會(huì)將整個(gè)數(shù)組序列分成兩個(gè)極度不平衡的部分,甚至更惡劣的情況是所有數(shù)據(jù)均一樣而出現(xiàn)一邊倒的趨勢(shì)，所以又退化到了O(n^2) 級(jí)別的時(shí)間復(fù)雜度，這是因?yàn)閷?duì)于每一個(gè)"基準(zhǔn)"元素來(lái)說(shuō)，重復(fù)的元素太多了，如果我們選的"基準(zhǔn)"元素稍微有一點(diǎn)的不平衡，那么就會(huì)導(dǎo)致兩部分的差距非常大；即時(shí)我們的"基準(zhǔn)"元素選在了一個(gè)平衡的位置，但是由于等于"基準(zhǔn)"元素的元素也非常多，也會(huì)使得序列被分成兩個(gè)及其不平衡的部分，那么在這種情況下快速排序就又會(huì)退化成O(n^2) 級(jí)別的排序算法。 在這里我們可以使用二路快速排序進(jìn)行優(yōu)化。

原理：

前面所敘述的快速排序算法是將>temp和<temp兩個(gè)部分元素都放在索引值i所指向的位置的左邊部分，而雙路快速排序則是使用兩個(gè)索引值（i、j）用來(lái)遍歷我們的序列，將<temp的元素放在索引 i 所指向位置的左邊，而將>temp的元素放在索引j所指向位置的右邊。

思想：

1、首先從左邊的i索引往右邊遍歷，如果i指向的元素<temp，那直接將i++移動(dòng)到下一個(gè)位置，直道i指向的元素>=temp則停止。

2、然后使用j索引從右邊開(kāi)始往左邊遍歷，如果j指向的元素>temp，那直接將j–移動(dòng)到下一個(gè)位置，直道j指向的元素<=temp則停止

3、此時(shí)i之前的元素都已經(jīng)歸并為<temp的部分了，而j之后的元素也都已經(jīng)歸并為>temp的部分了，此時(shí)只需要將vec[i]和vec[j]交換位置即可。這樣就可以避免出現(xiàn)=temp的元素全部集中在某一個(gè)部分，這正是雙路排序算法的一個(gè)核心。但是當(dāng)需要排序的數(shù)據(jù)長(zhǎng)度比較小時(shí)，此時(shí)使用插入排序的性能比較好，所以我們結(jié)合快速排序和插入排序進(jìn)行一個(gè)優(yōu)化快速排序。

具體實(shí)現(xiàn)代碼：

#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來(lái)記錄無(wú)序表的第一個(gè)值的下標(biāo)
        int j = i - 1;//用來(lái)記錄前面有序列的最后一個(gè)值的下標(biāo)
        int temp = vec[i];//記錄無(wú)序列的第一個(gè)值的值
        for (; j >= 0; j--) {
            if (vec[j] > temp) {
                vec[j + 1] = vec[j];//將有序表中的元素后移。
            }
            else {
                break;//當(dāng)無(wú)序表中的第一個(gè)值不比有序表中的最后一個(gè)值小時(shí)，跳出循環(huán)
            }
        }
        vec[j + 1] = temp;//將后移后的空值補(bǔ)上無(wú)序表中的第一個(gè)值。
    }
}
int qucikSort(vector<int>& vec, int L, int R)
{
    swap(vec[L], vec[rand() % (R - L + 1) + L]);// 隨機(jī)產(chǎn)生"基準(zhǔn)"元素所在位置，并與第一個(gè)元素交換位置
    int temp = vec[L]; // 將第一個(gè)元素作為"基準(zhǔn)"元素
    // 使用i索引從左到右遍歷，使用j索引從右到左遍歷
    int i = L + 1;// 索引值i初始化為第二個(gè)元素位置
    int j = R;// 索引值j初始化為最后一個(gè)元素位置
    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]);// 最后將"基準(zhǔn)"元素temp放置到合適的位置
    return j;
}
void quick(vector<int>& vec, int L, int R)
{
    if (R - L <= 40) {//當(dāng)數(shù)據(jù)量比較小時(shí)我們采用插入排序進(jìn)行
        Insert_sort(vec, L, R);
        return;
    }
    int p = qucikSort(vec, L, R);// 對(duì)vec[left...right]區(qū)間元素進(jìn)行排序操作，找到"基準(zhǔn)"元素
    quick(vec, L, p - 1);// 對(duì)基準(zhǔn)元素之前的序列遞歸
    quick(vec, p + 1, R);// 對(duì)基準(zhǔn)元素之后的序列遞歸
}
int main()
{
    clock_t startime, endtime;
    startime = clock();//開(kāi)始時(shí)間
    vector<int> vec;
    srand(time(0));
    for (int i = 0; i < 100000; i++) {
    //(在這里使用十萬(wàn)級(jí)別的數(shù)據(jù)量，完全有序的數(shù)組進(jìn)行計(jì)算時(shí)間復(fù)雜度
    // 百萬(wàn)級(jí)別的數(shù)據(jù)量由于程序執(zhí)行時(shí)間太長(zhǎng)，不例舉)
        vec.push_back(rand()%100);
    }
    quick(vec, 0, vec.size() - 1);
    //for (auto it : vec)//在這里不進(jìn)行輸出，數(shù)據(jù)量太大
    //{
    //    cout << it << " ";
    //}
    endtime = clock();//結(jié)束時(shí)間
    cout << (double)(endtime - startime) / CLOCKS_PER_SEC << endl;
    //在這里沒(méi)有定義單位，只通過(guò)數(shù)值進(jìn)行比較來(lái)判斷
    return 0;
}

在這里隨機(jī)數(shù)產(chǎn)生的數(shù)據(jù)進(jìn)行性能分析，如圖第一個(gè)數(shù)據(jù)是未經(jīng)過(guò)優(yōu)化的時(shí)執(zhí)行一個(gè)利用隨機(jī)生成數(shù)亂序并且重復(fù)率較高的執(zhí)行時(shí)間，第二個(gè)數(shù)據(jù)是二路快速排序的執(zhí)行時(shí)間。在這里執(zhí)行時(shí)間相差不多是因?yàn)檫@里我們難以得到一個(gè)重復(fù)率非常高的一組數(shù)據(jù)，但是實(shí)際上雙路快速排序優(yōu)化的結(jié)果還是比較理想的。

4. 總結(jié)

在上述優(yōu)化的過(guò)程中， 對(duì)于原始的快排來(lái)說(shuō)，當(dāng)重復(fù)率低，并且數(shù)組的有序化低是具有很好的效率，但是在應(yīng)對(duì)大量的規(guī)則性比較強(qiáng)的數(shù)據(jù)時(shí)，效率是跟不上。而隨機(jī)快速排序只是獲取了一個(gè)隨機(jī)基準(zhǔn)值來(lái)應(yīng)對(duì)數(shù)據(jù)有序化程度比較高的情況下來(lái)進(jìn)行優(yōu)化。但是二路快速排序結(jié)合了隨機(jī)快排和插入排序來(lái)應(yīng)對(duì)能夠出現(xiàn)的所有情況來(lái) 達(dá)到比較好的效果。

到此這篇關(guān)于C++快速排序及優(yōu)化方案詳解的文章就介紹到這了,更多相關(guān)C++快速排序及優(yōu)化內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論