频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
排序算法之快速排序
2011-10-06 16:03:56           
收藏   我要投稿

快速排序基本思想:挖坑填数+分治法

 

快速排序的分治partition过程有两种方法,一种是上面所述的两个指针索引一前一后逐步向后扫描的方法(算法导论上采用的是这种方法),还有一种方法是两个指针从首位向中间扫描的方法(大多数的人和一般的教材采用的是这第二种首尾向中间扫描法)。本文采用第二种方法。

 

1,把第一个作为基准,

 

2,先从后向前找,找到小于的,放在第一个

 

3,再从前向后找,找到大于的,放在刚刚移过的坑中,然后重复

 

 

 

<pre name="code" class="cpp">#include<stdio.h> 

#include<time.h> 

#define Length 500 

 

//函数声明 

void QuickSort(long*,long,long); 

long  Partition(long*,long,long); 

void Swap(long*,long*); 

 

int main() 

    long L[Length]; 

    long i=0; 

    printf("请分别输入%d个整数:\n",Length); 

    for(i=0;i<Length;i++) 

    { 

        printf("\n请输入第%d个整数:",i+1); 

            scanf("%d",&L[i]); 

    } 

    printf("\n排序前:"); 

    for(i=0;i<Length;i++) 

    { 

        printf("%5d",L[i]); 

    } 

     

    QuickSort(L,0,Length-1); 

     

    printf("\n排序后:"); 

    for(i=0;i<Length;i++) 

    { 

        printf("%5d",L[i]); 

    } 

    printf("\n"); 

    getchar(); 

    getchar(); 

    getchar(); 

    return 0; 

//算法实现 

//快速排序算法是一种递归实现的算法,所以必然要使用额外在堆栈做为辅助空间,堆栈深度与N个结点的 

 

二叉树相同,约为O(logn) 

//快速排序算法的时间复杂度为O(nlogn),在平均性能方面目前公认为最好的算法 

void QuickSort(long*L,long low,long high) 

    long pivotloc; 

    if(low<high) 

    { 

        pivotloc=Partition(L,low,high); 

        QuickSort(L,low,pivotloc-1); 

        QuickSort(L,pivotloc+1,high); 

    } 

 

long Partition(long*L,long low,long high) 

    long pivotkey=L[low];  //把第低位做为枢轴位置 

     

    while(low<high) 

    { 

        //当枢轴右边元素都比枢轴大时,高位左移,直接所 

        while(low<high&&L[high]>=pivotkey) high--; 

        Swap(&L[low],&L[high]); 

        while(low<high&&L[low]<=pivotkey)  low++; 

        Swap(&L[low],&L[high]); 

    } 

    return low; 

 

//用于交换数据的函数 

void Swap(long* a,long* b) 

    long temp; 

    temp=*a; 

    *a=*b; 

    *b=temp; 

}   

 

creat by 张飞雪

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 算法
上一篇:排序算法之基数排序,随机数的产生和程序运行时间的计算
下一篇:排序算法之直接插入排序
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站