排序.
快速排序
算法流程:
.选定枢轴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
6using namespace std;
7
8//******************辅助函数*****************//
9template <class T>
10vector <T> & operator<<(vector <T> &v, T const & d)
11
{
12
v.push_back(d);
13 return v;
14
}
15
16template <class T>
17void replace(T *a, T *b)
18{
19 T t = *a;
20 *a = *b;
21 *b = t;
22}
23
24//******************快速排序*****************//
25
26template <class T>
27int 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
41template <class T>
42void 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做调整
55template <class T>
56void HeapAdjust(T *data, int low, int high)
57{
58
59Next:
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
71template <class T>
72void 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]合成一个排好序的
87template <class T>
88void 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
109template <class T>
110void 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
124template <class T>
125void MergeSort(T *data, int n)
126{
127 //vector <T> dataT(n);
128 MergeSortImpl(&data[0], &data[0], 0, n-1);
129}
130
131void 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}
#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
else99
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
else115
{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
}- 上一篇 最长公共子序列, 最长递增子序列.
- 下一篇 C++箴言：争取异常安全的代码.