liyuxia713

蹣跚前行者

留言簿(3)

隨筆分類

收藏夾

隨筆檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

隨筆 - 50
文章 - 0
評論 - 32
引用 - 0

Algorithms

lzmagic (rss)
正在更新數據結構中的一些經典算法
第四維空間
數據結構算法
極限定律
算法

C++

鷹之夢園
C++ Primer 學習筆記

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

快速排序:

1

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

Quick_sort.h
3

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

第二部分都比樞紐元大，然后對這兩個數組進行快速排序，是一種遞歸的方法
5

平均運行時間O(Nlog(N)),最壞運行時間O(N^2)
6

最壞情形：對于預排序的序列。
7

對與樞紐元相等的元素處理：
8

i,j都停止：會比較相等元素，但是可以劃分成長度相當的兩個子數組
9

i,j都不停止，不會比較相等元素，但是可能產生長度不平衡的兩個子數組(與樞紐元相等的元素較多時)
10

樞紐元的選取：
11

1. 選取第一個元素做樞紐元：對于（部分）預排序的序列運行時間O(N^2)
12

2. 隨機生成樞紐元：能避免上述問題，但是產生樞紐元的代價高
13

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

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

#ifndef QUICK_SORT_H
16

#define QUICK_SORT_H
17

18

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

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

21

/* 選取第一個元素做樞紐元的情形----返回樞紐元位置*/
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，下面循環還要給現在的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

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

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

{
43

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

//將三個位置的元素，按順序擺好，一會兒begin，end位置的元素就無需參加比較
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]); //將樞紐元放到倒數第二個位置
50

return a[end-1];
51

}
52

53

54

/*三數中值分割法----分割:返回樞紐元位置*/
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; //選取樞紐元時原begin位置的元素已設置成小于key的
60

end = end - 2; //原end位置值已設置成大于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); //三數中值割分法
77

//int k = Quick_sort_divide(a,begin,end); //選第一個元素做樞紐元
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) 當元素個數少時不必用快速插入法
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 幸運草閱讀(2911) 評論(8) 編輯收藏引用所屬分類: Algorithms

@Linsea
是以2為底的logN，我想有的時候沒寫是默認是2吧，因為二叉樹一般涉及的都是以2為底的指數函數，反過來也是以2為底的對數函數。

具體的解釋我放在原日志最下端了，因為我只能以圖片的格式插入數學公式，所以就沒有辦法放在回復里了，你看一下，有問題再聯系我回復更多評論

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

最近也在看快排，希望一起討論
http://php.oil58.com/ 回復更多評論

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

@我是大熊

去貴頁面瀏覽了下，文筆風格比較吸引人，但頁面排版看著有些亂回復更多評論

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

@liyuxia713
謝謝！！可能是瀏覽器兼容性的關系！不過在改進了!
回復更多評論

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

我寫的快排，簡單的理解，沒你的這么深。可以的話，幫我看看！
http://php.oil58.com/?p=206 回復更多評論

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

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

刷新評論列表

只有注冊用戶登錄后才能發表評論。


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

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

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

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

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