lzm

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

Quicksort 快速排序

Posted on 2009-04-03 09:53 lzmagic 阅读(1608) 评论(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, 
099);
    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   知识库   博问   管理