排序.
快速排序
算法流程:
.选定枢轴pivot, 将所有小于他的放到左边,大于他的放到右边 (称作一趟排序)
.对左右两边分别做上面的操作
每一趟排序的方法:
确定最低关键字索引low, 最高关键字索引high, 枢轴索引pivot
从high向低处走,直到发现第一个小于pivot值的, 将pivot的值和high的值交换
从low向高处走,直到发现第一个大于pivot值的, 将pivot的值和low的值交换
这样就将原来的low-high之间的分成了两组 low~pivot, pivot~high
程序:
主函数为Qsort
堆排序
算法流程:
.建堆: 将顺序表当成完全二叉树, 从第一个非叶子节点(length-1位置)开始做堆调整
.排序: 依次 输出根节点(最小的数), 再将最后那个结点填到根节点, 从根向下做堆调整. 输出的所有的元素就是从小到大排好顺序的了
堆调整方法:
. 将根节点作为当前节点
. 将当前节点和他的两个子结点中的较小的比较, 如果大于, 就交换当前节点和这个较小的子结点, 然后将当前节点设为这个小结点, 并且接着这一步做, 否则结束
.
归并排序
算法流程:
. 将输入分为两半, 对这两半分别递归做归并排序
. 将排好序的左右两边merge成一个排好序的
1
#include <stdio.h>
2
#include <assert.h>
3
#include <vector>
4
#include <iostream>
5
6
using namespace std;
7
8
//******************辅助函数*****************//
9
template <class T>
10
vector <T> & operator<<(vector <T> &v, T const & d)
11
{
12
v.push_back(d);
13
return v;
14
}
15
16
template <class T>
17
void replace(T *a, T *b)
18
{
19
T t = *a;
20
*a = *b;
21
*b = t;
22
}
23
24
//******************快速排序*****************//
25
26
template <class T>
27
int Partition(T *data, int low, int high)
28
{
29
T pivot = data[low];
30
while(low<high)
31
{
32
for(; low<high && data[high]>=pivot; high--);
33
replace(&data[low],&data[high]);
34
for(; low<high && data[low]<=pivot; low++);
35
replace(&data[low],&data[high]);
36
}
37
38
return low;
39
}
40
41
template <class T>
42
void QSort(T *data, int low, int high)
43
{
44
if(low<high)
45
{
46
int pivotIdx = Partition(data, low, high);
47
QSort(data, low, pivotIdx-1);
48
QSort(data, pivotIdx+1, high);
49
}
50
}
51
52
//******************堆排序*****************//
53
54
//从low向high做调整
55
template <class T>
56
void HeapAdjust(T *data, int low, int high)
57
{
58
59
Next:
60
int minIdx = 2 * low + 1;
61
if(minIdx + 1<high && data[minIdx+1]>data[minIdx])
62
minIdx ++;
63
if(minIdx <high && data[minIdx]>data[low])
64
{
65
replace(&data[minIdx], &data[low]);
66
low = minIdx;
67
goto Next;
68
}
69
}
70
71
template <class T>
72
void HeapSort(T *data, int n)
73
{
74
for(int i=n/2; i>=0; i--)
75
HeapAdjust(data, i, n);
76
77
for(int i=n-1; i>=0; i--)
78
{
79
replace(&data[0], &data[i]);
80
HeapAdjust(data, 0, i);
81
}
82
}
83
84
//******************归并排序*****************//
85
86
//将data[low:mid] 和 data[mid+1:high]合成一个排好序的
87
template <class T>
88
void Merge(T *data, T *dataOut, int low, int mid, int high)
89
{
90
int i=low;
91
int j=mid+1;
92
int k=low;
93
94
for(; i<=mid && j<=high; )
95
{
96
if(data[i]<data[j])
97
dataOut[k++] = data[i++];
98
else
99
dataOut[k++] = data[j++];
100
}
101
102
while(i<=mid)
103
dataOut[k++] = data[i++];
104
105
while(j<=high)
106
dataOut[k++] = data[j++];
107
}
108
109
template <class T>
110
void MergeSortImpl(T *data, T *dataOut, int low, int high)
111
{
112
if(low == high )
113
dataOut[low] = data[low];
114
else
115
{
116
int mid = (low+high)/2;
117
vector <T> dataT(high+1);
118
MergeSortImpl(data, &dataT[0], low, mid);
119
MergeSortImpl(data, &dataT[0], mid+1, high);
120
Merge(&dataT[0], dataOut, low, mid, high);
121
}
122
}
123
124
template <class T>
125
void MergeSort(T *data, int n)
126
{
127
//vector <T> dataT(n);
128
MergeSortImpl(&data[0], &data[0], 0, n-1);
129
}
130
131
void main()
132
{
133
vector <int> vD;
134
int i;
135
136
if(1)
137
{
138
cout<<("Input data, 0 for end\n");
139
for(i; cin>>i;)
140
vD<<i;
141
}
142
143
//vD<<93<<1<<2;
144
145
//QSort(&vD[0], 0, vD.size()-1);
146
//HeapSort(&vD[0], vD.size());
147
MergeSort(&vD[0], vD.size());
148
149
for(i=0; i<vD.size(); i++)
150
cout<<vD[i]<<" ";
151
}

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

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

- 上一篇 最长公共子序列, 最长递增子序列.
- 下一篇 C++箴言:争取异常安全的代码.