lzm

who dare win.
posts - 14, comments - 29, trackbacks - 0, articles - 0

Quicksort 快速排序

Posted on 2009-04-03 09:53 lzmagic 阅读(1627) 评论(4)  编辑 收藏 引用 所属分类: Algorithm
/**
 * QUICKSORT : sort
 *        void sort(iterator beg, iterator end);
 *        void sort(iterator beg, iterator end, compare cmp);   <algorithm>
 */
#include <iostream>
#include <iterator>
#include <algorithm>
#include <numeric>
using namespace std;

int Partition(int *a, int lhs, int rhs)
{
       int key = a[rhs];
       int i = lhs - 1;
       for (int j = lhs; j < rhs; ++j)
             if (a[j] <= key) swap(a[++i], a[j]);
       swap(a[++i], a[rhs]);
       return i;
}

void QuickSort(int *a, int lhs, int rhs)
{
      if (lhs < rhs)
      {
             int mid = Partition(a, lhs, rhs);
             QuickSort(a, lhs, mid - 1);
             QuickSort(a, mid + 1, rhs);
      }
}

int main()
{
    int a[100];
    for (int i = 0; i < 100; ++i) a[i] = i;
    random_shuffle(a, a + 100);
    copy(a, a + 100, ostream_iterator<int>(cout, " ")); cout << endl << endl;
    
    QuickSort(a, 0, 99);
    copy(a, a + 100, ostream_iterator<int>(cout, " ")); cout << endl;
    
    system("pause");
    return 0;
}

Feedback

# re: [排序算法] QUICKSORT 快速排序  回复  更多评论   

2009-04-06 23:48 by 芦苇
想问下楼主 这个排版是怎么整的 太帅了！

# re: [排序算法] QUICKSORT 快速排序  回复  更多评论   

2009-04-07 01:01 by lzmagic
@芦苇
我是先学了些STL，然后根据MIT那本《算法导论》里的伪代码写的，谢谢评论，请多多指教。

# re: Quicksort 快速排序  回复  更多评论   

2009-04-15 14:58 by brightcoder
看了你写的好几篇文章，写的真挺帅气，有算法，又有STL，真爽

# re: Quicksort 快速排序  回复  更多评论   

2009-07-06 09:19 by xyy
版主的代码有问题
if (a[j] <= key) swap(a[++i], a[j]);
应该交换前先判断 i增1后,和j是否相等。如果相等也交换，
代码swap(a[++i], a[rhs]);也类似。

实际运行时会增加很多不必要的交换，且导致此算法变成不稳定算法。
效率会降低很多。


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