Linux靜態(tài)鏈接庫使用類模板的快速排序算法
快速排序的本質(zhì)是從數(shù)組中選一個參考值ref，比該參考值的大的，將其放在ref的右邊，比ref小的放在左邊，然后不斷的對兩邊重復(fù)執(zhí)行該動作
我們先列出來快速排序的步驟：
1.從數(shù)組中選一個參考值ref，比該參考值的大的，將其放在ref的右邊，
上面的動作將數(shù)組劃分為兩部分:
A ref B
A是比ref小的數(shù)組元素集合，它仍然是數(shù)組，B是比ref大的元素集合，它也仍然是數(shù)組
2.在對ref左右兩邊的元素重復(fù)上述動作，直到A和B都只剩下一個元素，那么排序就算完成了。
重點(diǎn)是如何分別選出來兩個集合A和B。算法導(dǎo)論里面把這個步驟叫做partition動作。
先把算法導(dǎo)論里面的偽代碼貼出來，大家先看一下：
先看第一種ref的選擇方法，即ref = a[r]
partition(a[], p, r)
{
i = p
j = p-1
ref = a[r]
for(; i<r; i++)
{
if(a[i]<ref)
{
j++
exchange(a[i], a[j])
}
}
exchange(a[r], a[j+1])
return j+1;
}
首先找一個參考值，ref = a[r]，為了簡單起見，這里取最后一個作為參考值，實(shí)際上可以去任意一個值作為參考值。這個我們一會再說。
然后找定義兩個游標(biāo)，分別是i 和j。i=p， j=p-1。為什么要這么定義呢？原因是我們既然選的是第一個，也就是a[p]，同時表示是從數(shù)組的第一個元素開始遍歷的。
選取j的目的是，我們要時刻知道當(dāng)前最近一次比ref小的值的位置。由于我們選取的是a[r]，作為參考值，且從第一個元素開始遍歷，為了跟蹤最近一次比ref小的數(shù)的游標(biāo)，暫時j=p-1。大家可以仔細(xì)體會一下這個做的意義。
觀察上述代碼可以看到，j總是記錄著最近一次比ref小的數(shù)的游標(biāo)，因此最后return j+1，所有比ref小的數(shù)的游標(biāo)均小于j+1，所有比ref大的數(shù)的游標(biāo)均大于j+2。
總之我們執(zhí)行partition的目的就是為了得到A，B，以及中間數(shù)的游標(biāo)，這樣我們就可以分別對A和B重復(fù)執(zhí)行上述動作。
接下來我們考慮另外兩種選取ref的方法。從上面選取最后一個值a[r]，作為參考值，并且在最后，將a[r]和a[j+1]交換的動作可以知道，我們總是希望知道我們選取參考值在partition過程中的位置，以便我們可以在最后一步，將a[refId] 和 a[j+1]的值交換。這里的refId表示選取ref值在a[]中的游標(biāo)。
如果我們選取ref為最后一個值，那么在所有的partition過程中，這個值的位置是固定的。但是，假如我們選取的ref的refId是p到r范圍內(nèi)的一個隨機(jī)數(shù)呢？
顯然，假如我們隨機(jī)選取ref的值，那么在partition過程中，refId對于的ref就有可能和其他值交換。這時候我們就需要更新ref對應(yīng)的游標(biāo)。
這樣一來，思路就很清晰了。
先給出partition的偽代碼：
partition(a[], p, r){
refId = random(p,r)
i = p
j = p-1
for(; i<=r; i++)
{
if(a[i]<ref)
{
j++ if(j == refId)//此時j剛好等refId，并且要和a[i]交換，則更新refId { refId = i }
exchange(a[i], a[j])
}
}
exchange(a[j+1], a[refId])
return j+1
}
從三種選擇ref的方法可以看到本質(zhì)上都是一樣的，都為用一個游標(biāo)j記錄最近一次遍歷到的比ref小的數(shù)據(jù)的游標(biāo)，然后將ref和a[j+1]交換，返回j+1。
下面給出C++的代碼實(shí)現(xiàn)
#include <iostream>
#include <stack>
#include"stdlib.h"
#include <time.h>
using namespace std;
template<class T>
class SORT
{
public:
static void myQsort(T a[], int p, int r);
static void myQsortNoRecur(T a[], int p, int r);
private:
static int partition(T a[], int p, int r);
static void exchange(T a[], int i, int j);
};
template<class T>
void SORT<T>::exchange(T a[], int i, int j)
{
T temp = a[i];
a[i] = a[j];
a[j] = temp;
return;
}
template<class T>
int SORT<T>::partition(T a[],int p,int r)
{
int i = p;
int j = p-1;
T ref = a[p];
int refId = p;
srand((unsigned)time(NULL));
refId = (rand() % (r-p+1))+ p;
//cout<<refId<<endl;
ref = a[refId];
for(; i<=r; i++)
{
if(a[i] < ref)
{
j++;
exchange(a, i, j);
if(j == refId)
{
refId = i;
}
}
}
exchange(a, j+1, refId);
return j+1;
}
template<class T>
void SORT<T>::myQsort(T a[],int p,int r)
{
int q = 0;
if(p<r)
{
q = partition(a, p, r);
myQsort(a, p, q-1);
myQsort(a, p+1, r);
}
return;
}
template<class T>
void SORT<T>::myQsortNoRecur(T a[], int p, int r)
{
int start = p;
int end = r;
int mid = 0;
std::stack<int> sortStk;
sortStk.push(p);
sortStk.push(r);
while(!sortStk.empty())
{
end = sortStk.top();
sortStk.pop();
start = sortStk.top();
sortStk.pop();
if(start < end)
{
mid = partition(a, start, end);
sortStk.push(start);
sortStk.push(mid -1);
sortStk.push(mid + 1);
sortStk.push(end);
}
}
}
int main(int argc, char** argv)
{
int a[10];
int b[10];
srand((unsigned)time(NULL));
for(int i=0; i<9; i++)
{
a[i] = rand();
}
srand((unsigned)time(NULL));
for(int i=0; i<9; i++)
{
b[i] = rand();
}
SORT<int>::myQsort(a,0, 9);
SORT<int>::myQsortNoRecur(b,0, 9);
for(int i=0; i<10; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
for(int i=0; i<10; i++)
{
cout<<b[i]<<" ";
}
return 0;
}
上面的代碼我直接給出了快速排序的遞歸和非遞歸實(shí)現(xiàn)。
遞歸的實(shí)現(xiàn)方式很好理解，但是加入別人正在面試你快速排序算法的時候，多半會讓你用非遞歸的方式實(shí)現(xiàn)給他看。下面我們就討論一下。
先觀察一下遞歸算法的運(yùn)行過程，即每次都去對一段更小的范圍去調(diào)用partition函數(shù)。所以我們需要知道每一次調(diào)用partition函數(shù)的start和end游標(biāo)，同時，每一次partition調(diào)用都會產(chǎn)生新的start和end游標(biāo)。
template<class T>
void SORT<T>::myQsort(T a[],int p,int r)
{
int q = 0;
if(p<r)
{
q = partition(a, p, r);
myQsort(a, p, q-1);
myQsort(a, p+1, r);
}
return;
}
這樣的話，我們就可以用一個通用容器去存放每次調(diào)用partition生成的start和end游標(biāo)。知道雖有的合法的start和end游標(biāo)都作為參數(shù)調(diào)用了partition函數(shù)。所謂合法的start和end就是start < end。。。。。
關(guān)于遞歸算法的非遞歸實(shí)現(xiàn)，第一個想到的數(shù)據(jù)結(jié)構(gòu)肯定是棧。其實(shí)別的數(shù)據(jù)結(jié)構(gòu)，例如隊(duì)列，也是可以實(shí)現(xiàn)。這里給出基于stl內(nèi)的stack的實(shí)現(xiàn)方法。代碼如下
template<class T>
void SORT<T>::myQsortNoRecur(T a[], int p, int r)
{
int start = p;
int end = r;
int mid = 0;
std::stack<int> sortStk;
sortStk.push(p);
sortStk.push(r);
while(!sortStk.empty())
{
end = sortStk.top();
sortStk.pop();
start = sortStk.top();
sortStk.pop();
if(start < end)
{
mid = partition(a, start, end);
sortStk.push(start);
sortStk.push(mid -1);
sortStk.push(mid + 1);
sortStk.push(end);
}
}
}
上面代碼的運(yùn)行過程就是每次循環(huán)，從容器內(nèi)拿一個start和end，如果是合法的，就依次將他們再次放入容易，知道這個容器為空未知。
給個運(yùn)行實(shí)例吧，我在代碼里面實(shí)現(xiàn)的是實(shí)現(xiàn)隨機(jī)數(shù)排序，ref采用隨機(jī)選取的方式。
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了CentOS Yum編譯安裝MySQL 5.6，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-08-08
Linux 啟動停止SpringBoot jar 程序部署Shell 腳本的方法
這篇文章主要介紹了Linux 啟動停止SpringBoot jar 程序部署Shell 腳本的方法，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值,需要的朋友可以參考下2019-04-04
Service Temporarily Unavailable的503錯誤是怎么回事？
一般來說，出現(xiàn)Service Temporarily Unavailable錯誤多半是因?yàn)榫W(wǎng)站訪問量大，造成了流量超限或者并發(fā)數(shù)大引起的資源超限出現(xiàn)的錯誤2013-05-05
詳解怎樣在Linux中配置靜態(tài)網(wǎng)絡(luò)連接
這篇文章主要介紹了詳解怎樣在Linux中配置靜態(tài)網(wǎng)絡(luò)連接，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-05-05
rsync中文手冊之使用rsync實(shí)現(xiàn)網(wǎng)站鏡像和備份linux
用rsync實(shí)現(xiàn)網(wǎng)站鏡像和備份 雖然是linux下的操作，但原理和windows下類似2008-09-09
在本篇文章里小編給大家分享了關(guān)于linux crm部署流程代碼，需要的朋友們可以學(xué)習(xí)下。2020-01-01
這篇文章主要介紹了Linux安裝MongoDB啟動及問題解決,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-08-08
linux如何實(shí)現(xiàn)一鍵部署nfs過程圖解
這篇文章主要介紹了linux如何實(shí)現(xiàn)一鍵部署nfs過程圖解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-07-07
這篇文章主要介紹了centos 7 源碼安裝openssh的方法，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-06-06
CentOS7使用yum安裝PostgreSQL和PostGIS的方法
這篇文章主要介紹了CentOS7使用yum安裝PostgreSQL和PostGIS的方法，非常不錯，具有一定的參考借鑒價值,需要的朋友可以參考下2019-09-09