排序算法

基于比较的排序

介绍

下面所介绍的几种算法都是基于比较的排序，所谓基于比较的排序，就是通过比较大小来决定位置，可以通过决策树来分析这个过程。

时间下界证明

对于任意的一颗决策树，叶子节点代表一次排序，故n个元素应该有n!个排序，即叶子节点为n!个，假设决策树高度为h，而对于一颗二叉树，节点树最多为2^h，故2^h >= n!，可以得出h >= lg(n!) = Ω(nlgn)。

插入排序

介绍

插入排序如同摸牌的过程，每次得到一个元素时现有的队列是已经有序的，因此，插入排序就是将待排序的元素一个个和有序的进行比较，找到自己合适的位置然后插入，形成一个有序的排列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insert_sort(vector<int>& vec)
{
    int size = vec.size();
    int tmp, j;
    for (int i = 1; i < size; ++i) //从第二个元素开始
    {
        tmp = vec[i];
        j = i;
        while(j > 0 && vec[j - 1] > tmp)
        {
            vec[j] = vec[j - 1]; //将大的值移动到后面来
            --j;
        }
        vec[j] = tmp; //找到合适位置j，插入
    }
}

冒泡排序

介绍

冒牌排序是一种流行但低效的排序，它是基于交换相邻逆序对来实现，每次冒泡排序将找出最大的数放到末尾，重复这一过程直至结束。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubble_sort(vector<int>& vec)
{
    int size = vec.size();
     //每次找出这一趟最大的数放到末尾
    for(int i = size - 1; i > 0; --i) 
    {
        for (int j = 0; j < i; ++j)
        {
            if(vec[j] > vec[j+1])
            {
                swap(vec[j], vec[j+1]);
            }
        }
    }
}

选择排序

介绍

每一趟找出数组中最大的值的下标，并记录，与最后一个元素交换，得到最大值，每一趟都会得出一个最大值，n-1趟之后排序完成。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void select_sort(vector<int>& vec)
{
    int size = vec.size();
    int max_pos = 0;
    for (int i = size - 1; i > 0; --i)
    {
        max_pos = i;
        for (int j = i - 1; j >= 0; --j)
        {
            if(vec[j] > vec[max_pos])
            {
                max_pos = j;
            }
        }

        swap(vec[max_pos], vec[i]);
    }
}

堆排序

介绍

堆排序的过程主要是依靠build_heap和delete_min两个操作完成的。首先将一个数组构建成一个最大堆，所谓最大堆就是一个父节点比两个子节点都大的完全二叉树，这样构建完成之后最大的数总是位于堆顶，每次得到最大值，然后重新调整堆，得到新的最大堆，不断重复此过程，得到排序的数组。时间复杂度是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
40
void perc_down(vector<int>& vec, int pos, int size)
{
    int child;
    int tmp = vec[pos];
    while(pos < size / 2) // size/2就是第一个叶子节点的位置
    {
        child = 2 * pos + 1;
        if (child != size - 1 && vec[child] < vec[child+1])
        {
            ++child;
        }
        if (vec[child] > tmp)
        {
            vec[pos] = vec[child];
            pos = child;
        }
        else
        {
            break;
        }

    }
    vec[pos] = tmp;
}


void heap_sort(vector<int>& vec)
{
    //从不是叶子节点的位置开始
    for (int i = vec.size() / 2 - 1; i >= 0 ; --i) 
    {
        perc_down(vec, i, vec.size()); //建堆
    }
    for (int j = vec.size() - 1; j > 0; --j)
    {
        swap(vec[0], vec[j]); //将最大值交换到最后一个存储
        perc_down(vec, 0, j); //调整堆，此时size用减小后的
    }

}

归并排序

介绍

归并排序是分治法的一种运用，这个算法的基本操作就是合并已经排序的两个表，而这两个表又都是通过归并排序得到的。时间复杂度推算为：T(n)=2T(n/2) + θ(n)，可以得到T(n) = θ(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
40
41
42
43
44
void merge(vector<int>& vec, vector<int>& tmp, int left_beg, int left_end, int right_end) //合并操作
{
    int right_beg = left_end + 1;
    int tmp_pos = left_beg;
    int size = right_end - left_beg + 1;

    while(left_beg <= left_end && right_beg <= right_end)
    {
        if(vec[left_beg] < vec[right_beg])
            tmp[tmp_pos++] = vec[left_beg++];
        else
            tmp[tmp_pos++] = vec[right_beg++];
    }

    while (left_beg <= left_end)
        tmp[tmp_pos++] = vec[left_beg++];

    while (right_beg <= right_end)
        tmp[tmp_pos++] = vec[right_beg++];

    //将该区间排好序的值放回原数组
    for (int i = 0; i < size; ++i, --right_end)
    {
        vec[right_end] = tmp[right_end]; 
    }
}

void merge_sort(vector<int>& vec, vector<int>& tmp, int left, int right)
{
    if(left < right) //重要判断
    {
        int mid = ( left + right ) / 2;
        merge_sort(vec, tmp, left, mid);
        merge_sort(vec, tmp, mid+1, right);
        merge(vec, tmp, left, mid, right);
    }
}

void merge_sort(vector<int>& vec) //入口
{
    int size = vec.size();
    vector<int> tmp(vec.size());
    merge_sort(vec, tmp, 0, size - 1);
}

快速排序

介绍

快速排序是实践中最快的已知排序算法，它的平均运行时间是O(NlgN)，最坏情况是O(n^2)，最关键的步骤就是如何选取枢纽元使排列能够均匀划分，错误的做法是直接选取第一个或者最后一个，因为实践中输入的数据可能是预排序的，这将产生不均匀的划分，另一种做法是随机产生一个枢纽元，但是随机数的生成是昂贵的。下面的这种做法是取最左边，右边，和中间的中值作为枢纽元。

代码

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
56
57
const int& partition(vector<int>& vec, int left, int right)
{
    int mid = ( left + right ) / 2;
    if(vec[mid] < vec[left])
        swap(vec[left], vec[mid]);
    if(vec[right] < vec[left])
        swap(vec[right], vec[left]);
    if(vec[right] < vec[mid])
        swap(vec[mid], vec[right]);
        
    /*
    上述步骤将3数中最大的放在右边，最小的左边，枢纽在中间
    */
        
    swap(vec[mid], vec[right-1]);
    //枢纽移动到right-1处
    return vec[right-1];
}
void quick_sort(vector<int>& vec, int left, int right)
{
    /*
    下面可做优化，对于少于10个数字的排列，用插入排序会更加迅速快捷
    if(left + 10 < right)
    {
        
    }
    else
    {
        //此处插入排序
    }
    
    */
    if(left < right) 
    {
        const int& pivot = partition(vec, left, right);
        int i = left, j = right - 1;
        while(1)
        {
            while(vec[++i] < pivot)
                ;
            while(vec[--j] > pivot)
                ;
            if(i < j)
                swap(vec[i], vec[j]);
            else
                break;
        }
        swap(vec[i], vec[right-1]);
        quick_sort(vec, left, i-1);
        quick_sort(vec, i+1, right);
    }
}

void quick_sort(vector<int>& vec)
{
    quick_sort(vec, 0, vec.size()-1);
}

基于非比较的排序

计数排序

介绍

计数排序是个非基于比较的排序，是一个稳定的算法，一般运行时间是theta(n)，但是这个排序对对空间有需求。

代码

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
void counting_sort(vector<int>& vec)
{
    /*
    tmp1是临时数组，存放排序的数值，tmp2是一个统计vec中各值多少的一个数组，比如tmp2[4]代表vec中小于等于4的元素个数
    */
    int size = vec.size();
    vector<int> tmp1(size);
    vector<int> tmp2(10); //此处不对，不好确定

    for (int i = 0; i < size; ++i)
    {
        ++tmp2[vec[i]];
    }

    for (int j = 1; j < size; ++j)
    {
        tmp2[j] += tmp2[j-1];
    }

    /*
    tmp2[vec[k]]代表比小于等于vec[k]的个数，比如tmp[vec[8]]=8，则代表vec[8]是在数组的第8个位置，tmp2[vec[k]]-1代表是在数组中，将其插入到tmp1里面。
    */
    for (int k = size - 1; k >= 0; --k)
    {
        tmp1[tmp2[vec[k]]-1] = vec[k];
        --tmp2[vec[k]];
    }

    vec.swap(tmp1); //  交换回vec中
}