liyuxia713

蹣跚前行者

導(dǎo)航

<

2012年7月

>

日

一

二

三

四

五

六

24

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評(píng)論排行榜

常用鏈接

統(tǒng)計(jì)

隨筆 - 50
文章 - 0
評(píng)論 - 32
引用 - 0

Algorithms

lzmagic (rss)
正在更新數(shù)據(jù)結(jié)構(gòu)中的一些經(jīng)典算法
第四維空間
數(shù)據(jù)結(jié)構(gòu) 算法
極限定律
算法

C++

鷹之夢(mèng)園
C++ Primer 學(xué)習(xí)筆記

基本排序算法及分析（四）：快速排序

快速排序:

1

/*----------------------------------------------------------------------------------------------
2

Quick_sort.h
3

快速排序:確定一個(gè)樞紐元，一次遍歷后將數(shù)組劃分成兩個(gè)部分，第一部分均比樞紐元小
4

第二部分都比樞紐元大，然后對(duì)這兩個(gè)數(shù)組進(jìn)行快速排序，是一種遞歸的方法
5

平均運(yùn)行時(shí)間O(Nlog(N)),最壞運(yùn)行時(shí)間O(N^2)
6

最壞情形：對(duì)于預(yù)排序的序列。
7

對(duì)與樞紐元相等的元素處理：
8

i,j都停止：會(huì)比較相等元素，但是可以劃分成長(zhǎng)度相當(dāng)?shù)膬蓚€(gè)子數(shù)組
9

i,j都不停止，不會(huì)比較相等元素，但是可能產(chǎn)生長(zhǎng)度不平衡的兩個(gè)子數(shù)組(與樞紐元相等的元素較多時(shí))
10

樞紐元的選取：
11

1. 選取第一個(gè)元素做樞紐元：對(duì)于（部分）預(yù)排序的序列運(yùn)行時(shí)間O(N^2)
12

2. 隨機(jī)生成樞紐元：能避免上述問(wèn)題，但是產(chǎn)生樞紐元的代價(jià)高
13

3. 三數(shù)中值分割法：選取左端，右端，中間位置三個(gè)元素的中值
14

----------------------------------------------------------------------------------------------*/
15

#ifndef QUICK_SORT_H
16

#define QUICK_SORT_H
17

18

#include "typedef.h" /* typedef int T 待排序的元素類型只要在這個(gè)文件中控制即可. */
19

#include "swap.h" /*交換兩個(gè)元素值*/
20

21

/* 選取第一個(gè)元素做樞紐元的情形----返回樞紐元位置*/
22

int Quick_sort_divide(T*a, int begin, int end)
23

{
24

T key = a[begin];
25

26

while(begin < end)
27

{
28

while(begin < end && a[end] >= key) --end;
29

a[begin] = a[end]; //不能--end，下面循環(huán)還要給現(xiàn)在的end位置賦值呢！
30

//swap(a[begin],a[end]);
31

while(begin < end && a[begin] <= key) ++begin;
32

a[end] = a[begin];
33

//swap(a[begin],a[end]);
34

}
35

a[begin] = key;
36

37

return begin;
38

}
39

40

/*三數(shù)中值割分法----選取樞紐元*/
41

const int& median3(T*a, int begin, int end)
42

{
43

int mid = (begin + end)/2;
44

//將三個(gè)位置的元素，按順序擺好，一會(huì)兒begin，end位置的元素就無(wú)需參加比較
45

if(a[mid] < a[begin]) swap(a[mid],a[begin]);
46

if(a[end] < a[begin]) swap(a[end],a[begin]);
47

if(a[mid] > a[end]) swap(a[mid],a[end]);
48

49

swap(a[mid],a[end-1]); //將樞紐元放到倒數(shù)第二個(gè)位置
50

return a[end-1];
51

}
52

53

54

/*三數(shù)中值分割法----分割:返回樞紐元位置*/
55

int Quick_sort_divide_3v(T*a, int begin,int end)
56

{
57

T key = median3(a,begin,end);
58

int tag = end - 1;
59

begin = begin + 1; //選取樞紐元時(shí)原begin位置的元素已設(shè)置成小于key的
60

end = end - 2; //原end位置值已設(shè)置成大于key的，end-1位置為key，都不用考慮
61

while(begin < end)
62

{
63

while(a[begin] < key) ++begin;
64

while(a[end] > key) --end;
65

if(begin < end) swap(a[begin],a[end]);
66

}
67

swap(a[begin],a[tag]);
68

return begin;
69

}
70

71

/*一次分割*/
72

void Quick_sort_step(T*a, int begin, int end)
73

{
74

if(begin < end)
75

{
76

int k = Quick_sort_divide_3v(a,begin,end); //三數(shù)中值割分法
77

//int k = Quick_sort_divide(a,begin,end); //選第一個(gè)元素做樞紐元
78

Quick_sort_step(a,begin,k-1);
79

Quick_sort_step(a,k+1,end);
80

}
81

}
82

/*快速排序*/
83

void Quick_sort(T* a, int n)
84

{
85

//if(n > 10) 當(dāng)元素個(gè)數(shù)少時(shí)不必用快速插入法
86

Quick_sort_step(a,0,n-1);
87

//else Insertion_sort(a,n);
88

}
89

90

#endif

posted on 2009-04-22 16:56 幸運(yùn)草閱讀(2894) 評(píng)論(8) 編輯收藏引用所屬分類: Algorithms

評(píng)論

# re: 基本排序算法及分析（四）：快速排序 2009-04-28 21:27 shongbee2

哈哈，終于弄清楚了。謝謝您。。以后多交流哈。呵呵回復(fù) 更多評(píng)論

# re: 基本排序算法及分析（四）：快速排序 2009-10-10 15:30 Linsea

我想問(wèn)下那個(gè)logN對(duì)數(shù)都沒(méi)有底數(shù),那個(gè)底數(shù)是多少?2嗎?
我看嚴(yán)蔚敏的書上有的地方有底數(shù)2,有的地方?jīng)]有,是怎么回事,這個(gè)問(wèn)題困擾我好久了,望博主對(duì)回答,謝謝! 回復(fù) 更多評(píng)論

# re: 基本排序算法及分析（四）：快速排序 2009-10-17 10:19 幸運(yùn)草

@Linsea
是以2為底的logN，我想有的時(shí)候沒(méi)寫是默認(rèn)是2吧，因?yàn)槎鏄?shù)一般涉及的都是以2為底的指數(shù)函數(shù)，反過(guò)來(lái)也是以2為底的對(duì)數(shù)函數(shù)。

具體的解釋我放在原日志最下端了，因?yàn)槲抑荒芤詧D片的格式插入數(shù)學(xué)公式，所以就沒(méi)有辦法放在回復(fù)里了，你看一下，有問(wèn)題再聯(lián)系我回復(fù) 更多評(píng)論

# re: 基本排序算法及分析（四）：快速排序 2012-06-28 00:58 我是大熊

最近也在看快排，希望一起討論
http://php.oil58.com/ 回復(fù) 更多評(píng)論

# re: 基本排序算法及分析（四）：快速排序 2012-06-28 11:31 liyuxia713

@我是大熊

去貴頁(yè)面瀏覽了下，文筆風(fēng)格比較吸引人，但頁(yè)面排版看著有些亂回復(fù) 更多評(píng)論

# re: 基本排序算法及分析（四）：快速排序 2012-07-04 03:15 我是大熊

@liyuxia713
謝謝！！可能是瀏覽器兼容性的關(guān)系！不過(guò)在改進(jìn)了!
回復(fù) 更多評(píng)論

# re: 基本排序算法及分析（四）：快速排序 2012-07-04 03:39 我是大熊

我寫的快排，簡(jiǎn)單的理解，沒(méi)你的這么深。可以的話，幫我看看！
http://php.oil58.com/?p=206 回復(fù) 更多評(píng)論

# re: 基本排序算法及分析（四）：快速排序 2012-07-04 03:41 我是大熊

不支持這個(gè)鏈接，不好意思
http://php.oil58.com/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-c/ 回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 基本排序方法及分析（九）：Randomized-Quicksort快速排序的隨機(jī)化版本 Order Statistics 順序統(tǒng)計(jì)（找出第i小元素）基本排序方法及分析（八）：CoungtingSort 計(jì)數(shù)排序基本排序方法及分析（七）：HeapSort 堆排序同時(shí)求最大最小值基本排序算法及分析（六）：桶式排序基本排序算法及分析（五）：歸并排序基本排序算法及分析（四）：快速排序基本排序算法及分析（三）：shell排序基本排序算法及分析（二）：冒泡排序

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理