首页 > 编程语言 > 详细

快速排序

时间:2018-02-15 00:15:52      阅读:99      评论:0      收藏:0      [点我收藏+]

标签:只需要   bsp   大于   get   pos   amp   过程   quick   swap   

"快速排序"的思想很简单,整个排序过程只需要三步:

  (1)在数据集之中,选择一个元素作为"基准"(pivot)。
  (2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。
  (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
 
对于基准的选取,可以采用“三位取中”的做法,C++代码如下:
int GetPivot(std::vector<int> & a, int left, int right)
{
    int center = (left+right)/2;
    if(a[left] > a[center])
        std::swap(a[left],a[center]);
    if(a[left] > a[right])
        std::swap(a[left],a[right]);
    if(a[center] > a[right])
        std::swap(a[center],a[right]);
    //下面这个交换一定要做!!!
    if(a[center] != a[right-1])
        std::swap(a[center],a[right-1]);
    return a[right-1];
}

void quicksort(std::vector<int> & a, int left, int right)
{
    static int count_quick = 1;
    if(left < right)
    {
        std::cout<<"进行第 "<<count_quick++<<" 次快速排序\n";
     //取 { a[left]、a[right]、a[(left+right)/2] } 三数中,中间那个数作为基准
        int pivot = GetPivot(a,left,right);  
        int i = left;
    //真正的基准值放在right-1的位置,即rigt-1不用比较,直接从right-2向右比较
        int j = right-1;
    //比枢纽大的在右边,比枢纽小的在左边
        while(i<j)
        {
            while(a[++i] < pivot);
            while(a[--j] > pivot);
            if(i<j)
                std::swap(a[i],a[j]);
        }
     //此时i一定比基准值大,将其与基准值调换位置
        std::swap(a[i],a[right-1]);
     //分治思想:递归枢纽的左边数组和右边数组
        quicksort(a,left,i-1);
        quicksort(a,i+1,right);
    }
}

void QuickSort(std::vector<int> & a)
{
    quicksort(a,0,a.size()-1);
}

 

快速排序

标签:只需要   bsp   大于   get   pos   amp   过程   quick   swap   

原文:https://www.cnblogs.com/ladawn/p/8449127.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号