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

algorithm
algorithm, 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;
}