随笔-15  评论-10  文章-1  trackbacks-0
快速排序的实现思想其实很简单,可以简单的描述成下面的递归形式,

qsort(array)
        设置分界点;
        把所有小于分界点的值作为左子列;
        把所有大于分界点的值作为右子列;
        qsort(左子列);
        qsort(有子列);
}


但是,实际用c/c++实现起来,就不见得一下可以写出来了,

以下是我的实现

#define SWAP(p1, p2) do { \
        int tmp = *(p1); \
        *(p1) = *(p2); \
        *(p2) = tmp; \
} while (0)


//====================================================
// 划分数组,并返回分界点
//====================================================
int partition(int array[], int left, int right)
{
        int l=left, r=right-1; /*用数组的最后1个元素分区*/

        while (l < r) {
                /*查找交换元素*/
                if (array[l] < array[right]) {
                        l++;
                        continue;
                }

                if (array[r] > array[right]) {
                        r--;
                        continue;
                }

                /*交换元素,调整索引*/
                SWAP(array+l, array+r);
                l++;
                r--;
        }

        /*此时数组l,r索引已经相遇,即l==r*/
        if (array[l] < array[right]) l++;
        SWAP(array+l, array+right);

        return l;
}


//快速排序
void qsort(int array[], int left, int right)
{
        if (left >= right) return;

        int pos = partition(array, left, right);
        if (pos == -1) return;

        qsort(array, left, pos-1);
        qsort(array, pos+1, right);
}


我认为快速排序中主要的东西就是partition方法,如果把partition
提取出来实现,则快速排序算法也就比较简单了。网上有qsort比较简
洁的c++实现,即没有把partition方法分离出来,但是一步到位的做法
比较难,我还是更喜欢先实现,再优化的方式。。。

posted on 2006-09-11 22:25 hzb 阅读(1102) 评论(0)  编辑 收藏 引用

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