Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1659244
  • 博文数量: 695
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 4027
  • 用 户 组: 普通用户
  • 注册时间: 2013-11-20 21:22
文章分类

全部博文(695)

文章存档

2018年(18)

2017年(74)

2016年(170)

2015年(102)

2014年(276)

2013年(55)

分类: C/C++

2014-08-07 21:53:58

快速排序学习1

快速排序学习:

今 天我学习了快速排序,顾名思义,快速排序的速度是很快的,平均复杂度是nlogn,我也不知道是怎么算出来的,反正 T(n) = 2T(n/2) + o(n) 这样怎么怎么推到就成了nLogn了,呵呵,有空去学习一下。希望会的人可以教我,我数学太烂了。废话少 说,记录一下快速排序的思路:

1.分治的思想,把数组分成两份,两份分成4分,这样分到足够小,就能很好排序咯,然后把他们合起来,排序完成。

2.该分治思想和合并排序思想一样,但是处理上更搞一筹,他是把小的和大的分成两份,这样在最后合并的时候,就不会像合并排序那样还要检查,因为本来就是左边比右边小,所以可以做到原地排序(就是不用申请多余的空间)。

3.如何做好把小和大的分开时关键,我们做的就是以一个数位基准,然后找到这个数的位置。把比他小的放在他的左边,比他大的放在他的右边,这样不就分开了嘛。

4.具体怎么分时一个最关键的地方,本来想用图说明一下,但是自己不会画:作罢,试着语言整理一下,呵呵:

例如,开始把最后一个作为标准,用一个循环j = nBegin j < nEnd一一比较,这样就能判断到底谁比他大,谁比他小咯。

注意:为了能清楚知道区域,所以要用一个变量i来保存它的标志,i的左边是比他小的,i的右边是比他大的。有了这个标志我们就好处理了。比较就好处理咯。

遇到小的,要把他方在i的左边,所以我们把他和i+1的元素交换,因为i+1得元素是大于x的,交换之后i+1就小于x了,这样我们把i也加1,不就有保证了i的左边都比x小,右边都比x大了嘛。呵呵。

遇到大的,不用管他。I也不用变。

比较完了,这时情况就是i的左边都比x小,i的右边都比x大,x在最后面。怎么处理呢?还不简单,有重复一下i + 1与 x交换,这样处理之后,i + 1就是保存的x值,i + 1的右边都比x大,i+1的左边都比x小,哈哈,i+1就是分割点咯。搞定。。

找出分割点后还不分而治之。。分而治之的时候发现分割点是排好的,只需排序nBegin - 分割点-1, 分割点+1 - nEnd 就可以咯。

最后还是截张《算法导论》书中的图:

呵呵,我就是学的这本书。还不错啦。附上下载地址分享一下:

奉上自己的源代码:
#include <stdio.h>
#include 
<stdlib.h>

//化分区间,找到最后元素的排序位置。并返回分隔的点(即最后一数据排序的位置)。
//划分的区间是[nBegin, nEnd). pData是保存数据的指针
int Partition(int* pData, int nBeging, int nEnd)
{
    
int i = nBeging - 1;    //分隔符号,最后nD保存在这里
    --nEnd;
    
int nD = pData[nEnd]; //比较的数据。
    int nTemp; // 交换用的临时数据

    
//遍历数据比较,找到nD的位置,这里注意,比较结果是,
    
//如果i的左边是小于等于nD的,i的右边是大于nD的
    for (int j = nBeging; j < nEnd; ++j)
    
{
        
if (pData[j] <= nD)        //如果数据比要比较的小,则在该数据的左边,与i+1交换
        {
            
++i;                //小于nD的数据多一个,所以要加1,i的左边数据都比nD小
            nTemp = pData[i];    //交换数据
            pData[i] = pData[j];
            pData[j] 
= nTemp;
        }

    }


    
//最后不要忘了吧nD和i+1交换,因为这里就是nD的位置咯。
    ++i;
    pData[nEnd] 
= pData[i];
    pData[i] 
= nD;

    
return i;   //返回nD的位置,就是分割的位置。
}


//排序的递归调用。
int QuickSortRecursion(int* pData, int nBeging, int nEnd)
{
    
if (nBeging >= nEnd -1)        //如果区域不存在或只有一个数据则不递归排序
    {
        
return 1;
    }


    
//这里因为分割的时候,分割点处的数据就是排序中他的位置。
    
//也就是说他的左边的数据都小于等于他,他右边的数据都大于他。
    
//所以他不在递归调用的数据中。
    int i = Partition(pData, nBeging, nEnd);        //找到分割点
    QuickSortRecursion(pData, nBeging, i);            //递归左边的排序
    QuickSortRecursion(pData, i + 1, nEnd);            //递归右边的排序
    return 1;
}


//快速排序
int QuickSort(int* pData, int nLen)
{
    
//递归调用,快速排序。
    QuickSortRecursion(pData, 0, nLen);
    
return 1;
}

int main()
{
    
int nData[10= {5,9,3,2,1,6,20,45,88,75};        //测试数据
    QuickSort(nData, 10);            //调用快速排序
    for (int i = 0; i < 10++i)        //输出结果
    {
        printf(
"%d ", nData[i]);
    }

    printf(
"\n");
    system(
"pause");
    
return 0;
}
阅读(1066) | 评论(0) | 转发(0) |
0

上一篇:选择排序

下一篇:排序总结

给主人留下些什么吧!~~