频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
数据结构之快排(递归版)
2012-06-27 08:44:37      个评论      
收藏   我要投稿

大学毕业了,之前说把数据结构书里的算法都写一遍,最后也不了了之。。
   从学会用STL中的sort的后,再也没有写过快排。在以后的时间中想慢慢的去把这些再写写。。一步一步慢慢的走下去。
#include<cstdio>

/*快速排序采用分治思想,设两个指针left和right,
 * 一个从左往右扫描,一个从右往左扫描;
 * 对于左指针,如果左指针所指的元素的值小于或者等于基准值,
 * 那么指针往右移一位,如果大于基准值,则和基准值交换;
 * 同理,对于右指针,如果右指针所指的元素的值大于或者等于基准值,
 * 那么指针往左移一位,如果小于基准值,则和基准值交换。*/

//对序列进行分区
int Part(int array[],int left,int right)
{
    int flag = array[left];  //基准
    while(right > left)
    {
        while(right > left && array[right] >= flag)
        {
            right--;
        }
        array[left] = array[right];
        while(right > left && array[left] <= flag)
        {
            left++;
        }
        array[right] = array[left];
    }   
    array[left] = flag;
    return left;
}

//运用递归进行排序
int quicksort(int array[],int low,int high)
{
    int flag;
    if (low < high)
    {
        flag = Part(array,low,high);
        quicksort(array,low,flag - 1);
        quicksort(array,flag + 1,high);
    }
}


作者:sunrise
点击复制链接 与好友分享!回本站首页
相关TAG标签 递归 数据结构
上一篇:C++编写学生成绩管理系统
下一篇:使用wxWidget中遇到的图片存储问题一二
相关文章
图文推荐
点击排行

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

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