lzm

who dare win.

posts - 14, comments - 29, trackbacks - 0, articles - 0

Quicksort 快速排序

Posted on 2009-04-03 09:53 lzmagic 閱讀(1653) 評論(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]);也類似。

實際運行時會增加很多不必要的交換，且導致此算法變成不穩定算法。
效率會降低很多。

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: Floyd_Warshall算法 Kruskal算法 Prim算法 Critical Path 關鍵路徑 Bellman_Ford算法 SPFA算法 Dijkstra算法 USP 無權最短路徑算法 Topsort 拓撲排序 (正則表達式)是否匹配(字符串) Quicksort 快速排序

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

lzm

導航

常用鏈接

留言簿(2)

隨筆分類(13)

隨筆檔案(14)

收藏夾(4)

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

Quicksort 快速排序

Feedback

# re: [排序算法] QUICKSORT 快速排序回復 更多評論

# re: [排序算法] QUICKSORT 快速排序回復 更多評論

# re: Quicksort 快速排序回復 更多評論

# re: Quicksort 快速排序 回復 更多評論

lzm

導航

常用鏈接

留言簿(2)

隨筆分類(13)

隨筆檔案(14)

收藏夾(4)

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

Quicksort 快速排序

Feedback

# re: [排序算法] QUICKSORT 快速排序 回復 更多評論

# re: [排序算法] QUICKSORT 快速排序 回復 更多評論

# re: Quicksort 快速排序 回復 更多評論

# re: Quicksort 快速排序 回復 更多評論

# re: [排序算法] QUICKSORT 快速排序回復更多評論

# re: [排序算法] QUICKSORT 快速排序回復更多評論

# re: Quicksort 快速排序回復更多評論

# re: Quicksort 快速排序回復更多評論