您当前位置:设计在线网 >> verilog >> 浏览文章

快速排序算法基本思想介绍

分享到:
本文章讲述了快速排序算法基本思想介绍.

快速排

序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序。一躺快速排序的算法是:

   1)、设置两个变量I、J,排序开始的时候I:=1,J:=N;

   2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];

   3)、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;

   4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;

   5)、重复第3、4步,直到I=J;

   例如:待排序的数组A的值分别是:(初始关键数据X:=49)

                   A[1]     A[2]     A[3]     A[4]     A[5]      A[6]     A[7]:

                     49        38       65       97       76       13        27

进行第一次交换后:   27        38       65       97       76       13        49

                   ( 按照算法的第三步从后面开始找

进行第二次交换后:   27        38       49       97       76       13        65

                  ( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时I:=3 )

进行第三次交换后:   27        38       13       97       76       49        65

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后:   27        38       13       49       76       97        65

( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时J:=4 )

      此时再执行第三不的时候就发现I=J,从而结束一躺快速排序,那么经过一躺快速排序之后的结果是:27        38       13       49       76       97        65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。

      快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:

初始状态                        {49     38     65     97     76     13     27}  

进行一次快速排序之后划分为      {27     38     13}     49   {76     97     65}

分别对前后两部分进行快速排序    {13}    27    {38}

                                结束         结束    {49    65}    76    {97}

                                                    49   {65}         结束

                                                        结束

                          图6    快速排序全过程


1)、设有N(假设N=10)个数,存放在S数组中;

2)、在S[1。。N]中任取一个元素作为比较基准,例如取T=S[1],起目的就是在定出T应在排序结果中的位置K,这个K的位置在:S[1。。K-1]<=S[K]<=S[K+1..N],即在S[K]以前的数都小于S[K],在S[K]以后的数都大于S[K];

3)、利用分治思想(即大化小的策略)可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。

如具体数据如下,那么第一躺快速排序的过程是:

数组下标: 1      2      3      4      5      6      7      8      9      10

           45     36     18     53     72     30     48     93     15      36

      I                                                                   J

(1)      36     36     18     53     72     30     48     93     15      45

      

(2)      36     36     18     45     72     30     48     93     15      53

(3)      36     36     18     15     72     30     48     93     45      53

(4)      36     36     18     15     45     30     48     93     72      53

(5)      36     36     18     15     30     45     48     93     72      53

通过一躺排序将45放到应该放的位置K,这里K=6,那么再对S[1。。5]和S[6。。10]分别进行快速排序。


一般来说,冒泡法是程序员最先接触的排序方法,它的优点是原理简单,编程实现容易,但它的缺点就是--程序的大忌--速度太慢。下面我介绍一个理解上简单但编程实现上不是太容易的排序方法,我不知道它是不是现有排序方法中最快的,但它是我见过的最快的。排序同样的数组,它所需的时间只有冒泡法的 4% 左右。我暂时称它为“快速排序法”。

     “快速排序法”使用的是递归原理,下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53,12,98,63,18,72,80,46, 32,21},先找到第一个数--53,把它作为中间值,也就是说,要把53放在一个位置,使得它左边的值比它小,右边的值比它大。{21,12,32, 46,18,53,80,72,63,98},这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组,而这两个数组继续用同样的方式继续下去,一直到顺序完全正确。

     我这样讲你们是不是很胡涂,不要紧,我下面给出实现的两个函数:

/*
n就是需要排序的数组,left和right是你需要排序的左界和右界,
如果要排序上面那个数组,那么left和right分别是0和9
*/

void quicksort(int n[], int left,int right)
{
int dp;
if (left<right) {

     /*
     这就是下面要讲到的函数,按照上面所说的,就是把所有小于53的数放
     到它的左边,大的放在右边,然后返回53在整理过的数组中的位置。
     */
     dp=partition(n,left,right);

     quicksort(n,left,dp-1);

     quicksort(n,dp+1,right); //这两个就是递归调用,分别整理53左边的数组和右边的数组
}
}

     我们上面提到先定位第一个数,然后整理这个数组,把比这个数小的放到它的左边,大的放右边,然后

返回这中间值的位置,下面这函数就是做这个的。
int partition(int n[],int left,int right)
{
int lo,hi,pivot,t;

pivot=n[left];
lo=left-1;
hi=right+1;

while(lo+1!=hi) {
     if(n[lo+1]<=pivot)
       lo++;
     else if(n[hi-1]>pivot)
       hi--;
     else {
       t=n[lo+1];
       n[++lo]=n[hi-1];
       n[--hi]=t;
     }
}

n[left]=n[lo];
n[lo]=pivot;
return lo;
}

     这段程序并不难,应该很好看懂,我把过程大致讲一下,首先你的脑子里先浮现一个数组和三个指针,第一个指针称为p指针,在整个过程结束之前它牢牢的指向第一个数,第二个指针和第三个指针分别为lo指针和hi指针,分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近,在逼近的过程中不停的与p指针的值比较,如果lo指针的值比p指针的值小,lo++,还小还++,再小再++,直到碰到一个大于p指针的值,这时视线转移到hi指针,如果 hi指针的值比p指针的值大,hi--,还大还--,再大再--,直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面,这时把p指针的值和碰面的值做一个调换,然后返回p指针新的位置。

 

推荐阅读:
A01-Altera FPGA设计应用班课程
用Verilog语言实现奇数倍分频电路 3分频 5分频 7分频(2011-03-24 13:01:41)
16位乘法器芯片设计工程实验

相关文章:

推荐文章  
赞助商链接  
热门排行  
主题推广  
中国设计在线网 All Rights Reserved. 互联网违法和不良信息举报
信息产业部备案号:湘ICP备09001063号