经典排序算法的c++实现

堆排序-heapsort

利用最大堆实现。
最大堆:最大堆性质是除了根结点意外的所有结点 i 都要满足A[parent[i]] >= A[i]
需要利用到的一个性质:当用数组表示存储n个元素的堆时,叶结点的下标分别是n/2, n/2+1, n/2 + 2, ……,n - 1. (下标从0开始)
需要用到的函数有:
void max_heapify(int a, int i) //通过让a[i]的值在最大堆中“逐级下降”,从而使得以下标i为根结点的字数重新遵循最大堆的性质。O(lgn)
void build_max_heap(int
a) //对树中非叶结点都调用一次max_heapify(a, i)。 O(n)
void heapsort(int *a, int n) //对长度为n的数组a调用堆排序。 O(nlgn)

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
32
33
34
35
36
37
38
39
//heapsort.cpp
inline void swap(int &a, int &b) { int t = a; a = b; b = t; }
inline int parent(int i) { return (i-1) >> 1; } //下标都是从0开始,与算导上不一样
inline int left(int i) { return (i << 1) + 1; }
inline int right(int i) { return (i << 1) + 2; }
int heap_size, heap_length; //heap_length是数组元素个数,heap_size是有多少个元素存储在数组中。0<=heap_size<=heap_length
void max_heapify(int *a, int i)
{ //O(lgn), 维护heap的性质,使得以下标i为根结点的子树重新遵循最大堆的性质
int l = left(i), r = right(i);
int largest = 0;
if (l < heap_size && a[l] > a[i])
largest = l;
else
largest = i;
if (r < heap_size && a[r] > a[largest])
largest = r;
if (largest != i) {
swap(a[i], a[largest]);
max_heapify(a, largest);
}
}
void build_max_heap(int *a) { //O(n), 对树中非叶结点都调用一次 max_heapify
heap_size = heap_length;
for (int i = heap_length/2 - 1; i >= 0; --i) //可以证明下标为n/2-1到0的结点为非叶结点
max_heapify(a, i); //i逆序递减的原因:任何时候对结点i调用max_heapify,该i的两个子树都是最大堆
}
void heapsort(int *a, int n) { //O(nlgn),调用heapsort(a, n)对数组a排序
heap_length = n;
build_max_heap(a);
for (int i = heap_length - 1; i >= 1; --i) {
swap(a[0], a[i]);
--heap_size;
max_heapify(a, 0);
}
}


归并排序-mergesort

mergesort:分治法,三步骤:
分解:分解待排序的n个元素的序列各具n/2个元素的子序列。
解决:使用归并排序递归地排序两个子序列。
合并:合并两个已排序的子序列以产生已排序的答案。
时间复杂度:T(n) = 2T(n/2) + O(n),由主定理可得分治法的时间复杂度O(nlgn).

算法导论上的下标是从1开始的,但是为了和c++ STL的设计思想一致,所有函数的实现统一用左闭右开区间.中间修改了很多次,因为下标修改不是很容易就改掉的,需要始终维持循环不变式,稍微一个步骤出错就会使结果有些错误。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
void merge(int *A, int p, int q, int r) //merge [p, r),左闭右开区间,时间复杂度O(n)
{
int n1 = q - p, n2 = r - q; //注意数量的变化与书上的不同,使用左闭右开区间的优势就是统一数量的形式表示
int *L = new int[n1], *R = new int[n2];
for (int i = 0; i < n1; ++i) //L[0, n1) <== A[p, q)
L[i] = A[p+i];
for (int i = 0; i < n2; ++i) //R[0, n2) <== A[q, r)
R[i] = A[q+i]; //此处不是q+i+1
int i = 0, j = 0;
int k = p;
while (i < n1 && j < n2) {
if (L[i] <= R[j])
A[k++] = L[i++];
else
A[k++] = R[j++];
}
while (i < n1) //由于没有了哨兵,需要添加多余元素
A[k++] = L[i++];
while (j < n2)
A[k++] = R[j++];
delete [] L;
delete [] R;
}
void merge_sort(int *a, int p, int r) //调用接口 merge_sort(a, 0, len), 不是(a, 0, len-1)了
{
if (p < r - 1) { //此时不是p < r了,左闭右开区间当p>=r-1时子数组最多一个元素
int q = p + (r - p)/2;
merge_sort(a, p, q);
merge_sort(a, q, r); //注意接口统一了,这个不是(a, q+1, r)而是(a, q, r)了,左闭右开的好处
merge(a, p, q, r);
}
}
int main()
{
srand(time(NULL));
int n;
while (cin >> n) {
int a[n];
for (int i = 0; i < n; ++i)
a[i] = rand() % n;
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
merge_sort(a, 0, n);
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
}
}

最后用了几万组测试数据,得出的结果均与stl里的sort结果一样, 基本说明这个代码是正确的。


快速排序-quicksort

quicksort:分治思想。
分解:数组A[p, r)被划分成两个子数组A[p..q) 和 A[q+1, r),使得A[p..q)中的每个元素小于等于A[q], A[q]也小于A[q+1..r)中的每个元素。q是划分过程要返回的结果。
解决:递归调用quicksort,对子数组A[p..q) 和 A[q+1, r)进行排序。
合并:因为子数组都是原址排序的,所以不需要合并操作:A[p..r)已经有序。

代码数组下标从0开始,并且所有函数使用左闭右开区间。与算法导论第三版书上的伪代码不同的部分在注释标出。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <ctime>
#include <cstdlib>
inline void swap(int &a, int &b)
{ int t = a; a = b; b = t; }
int partition(int *a, int p, int r) //对 a[p, r) 原址重排
{
int x = a[r-1]; //a[r] ==> a[r-1]
int i = p - 1;
for (int j = p; j < r - 1; ++j)
if (a[j] <= x) {
++i;
swap(a[i], a[j]);
}
swap(a[i+1], a[r-1]);
return i + 1;
}
void quicksort(int *a, int p, int r) //调用quicksort(a, 0, n),不是(a, 0, n-1),区间a[0, n)
{
if (p < r - 1) { //(p < r) ==> (p < r - 1)
int q = partition(a, p, r);
quicksort(a, p, q); //(a, p, q-1) ==> (a, p, q)
quicksort(a, q+1, r);
}
}
int main()
{
srand(time(NULL));
int n;
while (scanf("%d", &n)) {
int a[n];
for (int i = 0; i < n; ++i)
a[i] = rand() % n;
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
quicksort(a, 0, n);
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
}
}

随机测试几万组数据与stl 的sort产生结果一致。但是这个没有优化的版本与SGI的stl版本的sort效率相差比较大。当排序生成的一千万个随机数时,stl版本的sort平均3秒多,这个没有任何优化过的quicksort需要20多秒,差别还是非常大的。stl源码使用了很多优化技术,像是三位取中选pivot,分段递归后数据量小于某个阈值后会使用insrttionSort,递归层次过深还会改用heapsort。确实像侯捷说的,99.99%的程序猿写的程序,在SGI STL面前都是三流水准。所以追求效率还是使用stl的sort版本,一般会比自己写的快。

泛型程序代码:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<typename RandomAccessIterator>
RandomAccessIterator
partition(RandomAccessIterator p, RandomAccessIterator r) {
RandomAccessIterator x = r - 1, i = p - 1;
for (RandomAccessIterator j = p; j < r - 1; ++j) {
if (*j <= *x) {
++i;
iter_swap(i, j);
}
}
iter_swap(i+1, r-1);
return i + 1;
}
template<typename RandomAccessIterator>
void quicksort(RandomAccessIterator p, RandomAccessIterator r) {
if (p < r - 1) {
RandomAccessIterator q = partition(p, r);
quicksort(p, q);
quicksort(q+1, r);
}
}
template<typename InputIterator>
void print(InputIterator beg, size_t size) {
while (size--) {
cout << *beg++ << " ";
}
cout << endl;
}
int main()
{
const int n = 10;
int a[n];
vector<int> ivec;
for (int i = 0; i < n; ++i) {
a[i] = n - i;
ivec.push_back(n-i);
}
print(a, n);
quicksort(a, a + n);
print(a, n);
print(ivec.begin(), ivec.size());
quicksort(ivec.begin(), ivec.end());
print(ivec.begin(), ivec.size());
return 0;
}