从头再来

QuickSort

复习 快排



    int buf[1024] = {0};

    int partition(int first, int last)
    {
        int stand = buf[last];
        int i =0, j=0;
        //int e = last -1;
        for (;j <  last  ; j++ )
        {
            if (buf[j] <= stand )
            {
                int temp = buf[j];
                buf[j] = buf[i];
                buf[i] = temp;
                i++;
            }
        }
        int temp = buf[last];
        buf[last] = buf[i];
        buf[i] = temp;
        return i;
    }


    void myQuickSort(int begin, int end)
    {
        if (begin < end)
        {
            int pivot ;
            pivot = partition(begin, end);
            myQuickSort(begin, pivot -1 );
            myQuickSort(pivot+1, end);
        }
    }

int main()
{
    srand(time(0));
    for (int i = 0; i < 1000; i++)
    {
        buf[i] = rand()  * 2342111134 % 6589453 ;
    }
    myQuickSort(0,1023);
    return 0;
}


在本实现 里面, 直接使用了最后一个元素作为基准。

在选择基准时其实是有多种方式的。1)选第一个,不推荐。2)算最后一个,不推荐。3)选首、尾、中的中间值。4)随机选择。

选择后将跑一趟比较,结果是左侧为小的数,右侧为大的数,原理是i,j   当数小于基准是则与左右的i 对换,这样保证了i左侧小于p   i 到j 之间是大小p 的。

对于p 无需再排了。




需要特别注意的是partition 里面的元素位置与quicksort 分段是有关系的。 如果在partition 里面处理了last 那么 在分段时其实last 就不用了。 

posted on 2015-05-30 23:22 易宝@byhh 阅读(158) 评论(0)  编辑 收藏 引用


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