资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

Linux中如何实现静态链接库使用类模板的快速排序算法-创新互联

这篇文章给大家分享的是有关Linux中如何实现静态链接库使用类模板的快速排序算法的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。

宜昌网站建设公司创新互联公司,宜昌网站设计制作,有大型网站制作公司丰富经验。已为宜昌超过千家提供企业网站建设服务。企业网站搭建\成都外贸网站建设公司要多少钱,请找那个售后服务好的宜昌做网站的公司定做!

快速排序的本质是从数组中选一个参考值ref,比该参考值的大的,将其放在ref的右边,比ref小的放在左边,然后不断的对两边重复执行该动作

我们先列出来快速排序的步骤:

1.从数组中选一个参考值ref,比该参考值的大的,将其放在ref的右边,

上面的动作将数组划分为两部分:

A ref B

A是比ref小的数组元素集合,它仍然是数组,B是比ref大的元素集合,它也仍然是数组

2.在对ref左右两边的元素重复上述动作,直到A和B都只剩下一个元素,那么排序就算完成了。

重点是如何分别选出来两个集合A和B。算法导论里面把这个步骤叫做partition动作。

先把算法导论里面的伪代码贴出来,大家先看一下:

先看第一种ref的选择方法,即ref = a[r]

partition(a[], p, r)
{
i = p
j = p-1
ref = a[r]
for(; i

首先找一个参考值,ref = a[r],为了简单起见,这里取最后一个作为参考值,实际上可以去任意一个值作为参考值。这个我们一会再说。

然后找定义两个游标,分别是i 和j。i=p, j=p-1。为什么要这么定义呢?原因是我们既然选的是第一个,也就是a[p],同时表示是从数组的第一个元素开始遍历的。

选取j的目的是,我们要时刻知道当前最近一次比ref小的值的位置。由于我们选取的是a[r],作为参考值,且从第一个元素开始遍历,为了跟踪最近一次比ref小的数的游标,暂时j=p-1。大家可以仔细体会一下这个做的意义。

观察上述代码可以看到,j总是记录着最近一次比ref小的数的游标,因此最后return j+1,所有比ref小的数的游标均小于j+1,所有比ref大的数的游标均大于j+2。

总之我们执行partition的目的就是为了得到A,B,以及中间数的游标,这样我们就可以分别对A和B重复执行上述动作。

接下来我们考虑另外两种选取ref的方法。从上面选取最后一个值a[r],作为参考值,并且在最后,将a[r]和a[j+1]交换的动作可以知道,我们总是希望知道我们选取参考值在partition过程中的位置,以便我们可以在最后一步,将a[refId] 和 a[j+1]的值交换。这里的refId表示选取ref值在a[]中的游标。

如果我们选取ref为最后一个值,那么在所有的partition过程中,这个值的位置是固定的。但是,假如我们选取的ref的refId是p到r范围内的一个随机数呢?

显然,假如我们随机选取ref的值,那么在partition过程中,refId对于的ref就有可能和其他值交换。这时候我们就需要更新ref对应的游标。

这样一来,思路就很清晰了。

先给出partition的伪代码:

partition(a[], p, r){
refId = random(p,r)
i = p
j = p-1
for(; i<=r; i++)
{
if(a[i]

从三种选择ref的方法可以看到本质上都是一样的,都为用一个游标j记录最近一次遍历到的比ref小的数据的游标,然后将ref和a[j+1]交换,返回j+1。

下面给出C++的代码实现

#include 
#include 
#include"stdlib.h"
#include 

using namespace std;
template
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
void SORT::exchange(T a[], int i, int j)
{
T temp = a[i];
a[i] = a[j];
a[j] = temp;
return;
}
template
int SORT::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<
void SORT::myQsort(T a[],int p,int r)
{
int q = 0;
if(p
void SORT::myQsortNoRecur(T a[], int p, int r)
{
int start = p;
int end = r;
int mid = 0;
std::stack 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::myQsort(a,0, 9);

SORT::myQsortNoRecur(b,0, 9);

for(int i=0; i<10; i++)
{
cout<

上面的代码我直接给出了快速排序的递归和非递归实现。
递归的实现方式很好理解,但是加入别人正在面试你快速排序算法的时候,多半会让你用非递归的方式实现给他看。下面我们就讨论一下。

先观察一下递归算法的运行过程,即每次都去对一段更小的范围去调用partition函数。所以我们需要知道每一次调用partition函数的start和end游标,同时,每一次partition调用都会产生新的start和end游标。

template
void SORT::myQsort(T a[],int p,int r)
{
int q = 0;
if(p

这样的话,我们就可以用一个通用容器去存放每次调用partition生成的start和end游标。知道虽有的合法的start和end游标都作为参数调用了partition函数。所谓合法的start和end就是start < end。。。。。

关于递归算法的非递归实现,第一个想到的数据结构肯定是栈。其实别的数据结构,例如队列,也是可以实现。这里给出基于stl内的stack的实现方法。代码如下

template
void SORT::myQsortNoRecur(T a[], int p, int r)
{
int start = p;
int end = r;
int mid = 0;
std::stack 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);
}
}
}

感谢各位的阅读!关于“Linux中如何实现静态链接库使用类模板的快速排序算法”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!


网站名称:Linux中如何实现静态链接库使用类模板的快速排序算法-创新互联
路径分享:http://cdkjz.cn/article/dsisei.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220