sunrise

每天不断学习,才能不断提升自己。

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  64 随笔 :: 0 文章 :: 92 评论 :: 0 Trackbacks
   大学毕业了,之前说把数据结构书里的算法都写一遍,最后也不了了之。。
   从学会用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);
    }
}
posted on 2012-06-26 17:23 SunRise_at 阅读(1463) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理