排序嘛之前也不是没写过，就在刚刚水了1000字的时候，我一个ctrl+z按过火了导致不小心没有保存的源文件付诸东流，太草率了，现在说起来心情就有点低落，罢了罢了，我的心情真的平复下来了。话说之前也草草的整理过两篇排序的文章，不过现在在看向曾经整理的东西，啊太幼稚了

性能对比

类别排序方法时间复杂度空间复杂度稳定性
最好情况最坏情况平均情况辅助储存
插入排序直接插入排序O(n)O(n^2)O(n^2)O(1)不稳定
希尔排序O(n)O(n^2)~O(n^1.3)O(1)不稳定
交换排序冒泡排序O(n)O(n^2)O(n^2)O(1)不稳定
快速排序O(nlogn)O(n^2)O(nlogn)O(nlogn)不稳定
选择排序直接选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定
堆排序O(nlogn)O(nlogn)O(nlogn)O(n^2)不稳定
归并排序O(nlogn)O(nlogn)O(nlogn)O(n)不稳定
基数排序K:代排元素的维数，m为基数个数O(m+n)O(k*(n+m))O(k*(n+m))O(m+n)稳定

pssss：makedown语法并没有合并单元格的功能，利用支持html语法的特性纯手撸，嗯看起来果然有点丑

排序有以下几类

种类 方式1 方式2
按储存介质分 内部排序 外部排序
按比较器个个数分 串行排序：单处理器 并行排序：多处理器
按主要操作分 比较排序 基数排序
按辅助空间分 原理排序 非原地排序
按稳定性分 稳定排序：eg插入排序 非稳定排序：eg选择排序
按自然性分 自然排序 非自然排序

插入排序

直接插入排序

插入排序是应该是最简单的排序算法之一了，不过排序算法也没几个。插入排序又N-1趟排序组成，对于P=1到P=N-1趟，插入排序利用了这样的事实；其实从0到位置P上的元素为以排序状态。插入排序利用了这样的事实。0到P-1的元素是已经排过序的。大致过程入下

不难知道，插入排序是将待插入元素一个个的插入到已有序的过程中，插入位置遵循了使用插入仍然保持有序的原则，具体做法是从后往前枚举已有的部分来确定插入位置。具体实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
void insertsort(int a[],int n){
        for(int i=1;i<n;i++){
            int temp=a[i];int j=i;
            while (j>0&&temp<a[j-1])
            {
                a[j]=a[j-1];
                j--;
            }
           a[j]=temp; 
        }
}
int main(){
int a[]={9,8,5,2,3,1,4,7,6};
insertsort(a,9);
for(int i=0;i<9;i++){
    cout << a[i];
}
    system("pause");
    return 0;
}

选择排序

直接选择排序

选择排序也算是最简单的排序算法之一了。没错又是之一（滑稽。甚至我用的这本教程已经自动省略了这个排序算法。这样大概就可以冠以最简单的排序算法之名了吧（雾。简单选择排序是指对于一个序列A[1]~A[n],令i从1到n枚举，进行n糖操作，每趟从待排序[i,n]中选择最小元素。令其与待排序部分的第一个元素A[i]进行交换，这样子的话元素A[i]就会与当前的有序区间[1,i-1]，形成新的有序区间[1,i]，于是在进行n趟排序后，元素就会是有序的。

实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include &lt;bits/stdc++.h&gt;
using namespace std;
void selectsort(int a[], int n)
{
    for(int i=0;i<n-1;i++){
        int k=i;
        for(int j=i;j<n;j++){
            if(a[k]>a[j])
            k=j;
        }
        swap(a[i],a[k]);
    }
}
int main()
{
    int a[]={1,2,3,5,4,7,8,9,6};
    selectsort(a,9);
    for(int i=0;i<9;i++){
        cout << a[i];
    }
    system("pause");
    return 0;
}

选择排序虽然很简单不错啦，但是由于时间复杂度为O(n2)的原因其实大部分情况都不能处理，大概只能处理105这个范围只能的数据。所以在使用的时候要记住上限条件。

kaguyasama哇哇哇哇哇哇哇！！！！！！！

我已经鸽了好久了！！jojo！！！我不写博客啦！！

堆排序

大概简介上只有那么短短三句话，

  • 对所有记录建 堆 。
  • 依次取出堆顶元素，就可以得到排好序的序列。
  • 时间复杂度为O(nlogn) 。

堆即是一个可以看作为完全二叉树的数组。《算法导论》第三版这样定义：

*The(binary) heap data structure is an array object that we can view
as a nearly completely binary tree.

只要一个序列可以看作为一个完全二叉树，它又满足堆的性质，那么它就可以称
之为一个堆。——一个数组可以这样看成一个完全二叉树，将第一个数看作根结点，
第二和第三个数看作第一个数的左孩子和右孩子，…，将第2n和第2n+1数看作
是第n个数的两个孩子。

堆可以分为大堆和小堆，所谓堆属性是指结点应总是大于它的孩子，此为大堆属性。
对于小堆来讲则反之。也就是说堆的根结点总是存储着最大或最小的数，当一个完
全二叉树中所有的结点都满足堆属性时此完全二叉树就可以看作为一个堆。

总的来讲，堆排序的要诀在于堆的一个特性——堆的根结点总是存储着最大或最小的
数。假使我们能将一组数建堆，那么只需要不断的在取出根结点和维持堆属性这两
步中不断循环就可以完成排序了

以下是c++实现代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>
 
using namespace std;
 
void HeapAdjust(vector<int> &list, int parent, int length){
    int temp = list[parent];                    // temp保存当前父节点
    int child = 2 * parent + 1;                    // 先获得左孩子
 
    while (child < length){
        // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
        if (child + 1 < length && list[child] < list[child + 1]){
            child++;
        }
 
        // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
        if (temp >= list[child]){
            break;
        }
 
        // 把孩子结点的值赋给父结点
        list[parent] = list[child];
 
        // 选取孩子结点的左孩子结点,继续向下筛选
        parent = child;
        child = 2 * parent + 1;
    }
    list[parent] = temp;
}
 
vector<int> HeadSort(vector<int> list){
    int length = list.size();
    // 循环建立初始堆
    for (int i = length / 2 - 1; i >= 0; i--){
        HeapAdjust(list, i, length);
    }
 
    // 进行n-1次循环，完成排序
    for (int i = length - 1; i > 0; i--){
        // 最后一个元素和第一元素进行交换
        int temp = list[i];
        list[i] = list[0];
        list[0] = temp;
        
 
        // 筛选 R[0] 结点，得到i-1个结点的堆
        HeapAdjust(list, 0, i);
        cout << "第" << length - i << "趟排序:";
        for (int i = 0; i < list.size(); i++){
            cout << list[i] << " ";
        }
        cout << endl;
    }
    return list;
}
 
int main(){
    int arr[] = { 5, 4, 6, 7, 2, 3, 1 };
    vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
    cout << "排序前:";
    for (int i = 0; i < test.size(); i++){
        cout << test[i] << " ";
    }
    cout << endl;
    vector<int> result;
    result = HeadSort(test);
    cout << "排序后:";
    for (int i = 0; i < result.size(); i++){
        cout << result[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}

交换排序

冒泡排序

冒泡排序原理实现很简单，要想轻松简单的理解的理解冒泡排序，可以吧数组理解成一个垂直猪蹄，其中最小的元素在顶部，最大的元素在底部。数组从底部往上扫描。就像水的冒泡原理一样，气泡是从底部一点点的往上冒的。如果相邻的两个元素逆序。则交换两者的位置，

首先

比较data[n-1]和data[n-2]之间的大小，如果逆序则互换，接着比较data[n-2]和data[n-3]。有需要时就改变他们的顺序，就这样一直一直的比较到data[1]到data[0]；就这样最小的元素就移动到了顶部。

然而，这只是完成了第一步。我们需要再次对数组进行扫描，比较剩下来的数据项。当有需要的时候需要交换位置。然后就这样哈一直一直的比下去，最后一项比较的是data[1]和data[0];由于data[0]在第一次一定完成后已经是最小的了。也就是位置0，然而第二次冒泡最小的元素会放在第二个位置上也就是1！！！！！然后第三次第四次依次按照同样的方法就行了。到最后一步只需要比较**data[n-1]和data[n-2]**之间的大小就好了。

下面写上伪代码

1
2
3
4
bubblesort(data[],n)
    for i到n-2
        for j=n-1到i+1
            如果两者逆序，交换j和j-1位置的元素

具体实现

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
#include <bits/stdc++.h>
using namespace std;
void bubblesort(int data[], int n)//代码就不解释啦八
{
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = n - 1; j > i; --j)
        {
            if (data[j] < data[j - 1])
            {
                swap(data[j], data[j - 1]);
            }
        }
    }
}
int main()
{
    int n;
    cin >> n;
    int a[n];
    for (size_t i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    bubblesort(a, n);
    for (size_t i = 0; i < n; i++)
    {
        cout << a[i]<<" ";
    }
    system("pause");
    return 0;
}

快速排序

快速排序(quicksort)是在实践中中目前最快的已知算法，平均运行为O(nlogn)，该算法超级快，主要是由于非常精炼和高度优化的内部循环，虽然他最坏的情况能达到O(n^2)，但只要稍加努力就能避免这种情况。

其核心思想是分治：选择数组中某个数作为基数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数都比基数小，另外一部分的所有数都都比基数大，然后再按此方法对这两部分数据分别进行快速排序，循环递归，最终使整个数组变成有序。

大概可以总结为一下三个过程

  1. 将数列划分为两部分（不是直接分，要求保证相对大小关系）
  2. 递归到两个子序列中分别进行快速排序
  3. 不用合并，因为此时数列已经完全有序

和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。怎么操作呢？

为了保证平均时间复杂度，一般是随机选择一个数 m 来当做两个子数列的分界。之后，维护一前一后两个指针 p 和 q，依次考虑当前的数是否放在了应该放的位置（前还是后），当前位置放对了之后，再移动指针继续处理，直到两个指针相遇。如果当前的数没放对呢？比如说如果后面的指针 q 遇到了一个比 m 小的数，那么可以交换 p 和 q 位置上的数，再把 p 向后移一位。其实，快速排序没有指定应如何具体实现第一步，不论是选择 m 的过程还是划分的过程，都不是只有一种实现方法。

一般我们说的快速排序的时间复杂度是平均为 O(nlogn)，最坏是 O(n^2)，实践中几乎不可能达到最坏情况。且因为快速排序的内存访问遵循局部性原理，多数情况下快速排序的表现大幅优于堆排序等其他复杂度为O(nlogn) 的排序算法。

其实，在选择 m 的过程中使用 Median of Medians 算法，就可以保证最坏时间复杂度为 O(nlogn)，但是由于其过于复杂，实践中一般不使用。

具体实现

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
#include<bits/stdc++.h>
using namespace std;
int partition(int a[],int left,int right){
    int temp=a[left];
    while (left<right)
    {
    
    while(left<right&&a[right]>temp)right--;
    a[left]=a[right];
    while(left<right&&a[left]<temp)left++;
    a[right]=a[left];
}
a[left]=temp;
return left;
}
void quicksort(int a[],int left,int right){
    if(left<right){
    int post=partition(a,left,right);
    quicksort(a,left,post-1);
    quicksort(a,post+1,right);
}}
int main(){
int a[]={7,5,6,3,2,4,1,8,9};
quicksort(a,0,8);
for(int i=0;i<9;i++)
cout << a[i];
    system("pause");
    return 0;
}

希尔排序

选择排序也是一种插入排序

说起希尔排序当然是和他的发明者希尔有关系啦（雾，该算法算是最早的一批冲破二次屏障的算法的前辈了。过了若干年后才证明了他的亚二次界，原理是通过比较相距一定间隔的元素来工作；各趟比较所用的距离随着算法的进行而减小，直到比较相邻元素的最后一趟排序为止，所以希尔排序有时也被叫做缩小增量排序(diminishing increment sort)

大概实现图解

重点来啦！！！

Shell 排序是以它的发明者命名的（废话，也称为缩小增量排序法。Shell 排序对不相邻的记录进行比较和移动：

  1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）
  2. 对这些子序列进行插入排序
  3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1

Shell 排序的复杂度和间距序列的选取（就是间距如何减小到 1）有关，比如“间距每次除以 3”的 Shell 排序的复杂度是 O(n^2/3)。

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include&lt;bits/stdc++.h&gt;
using namespace std;
void shellsort(int a[],int n){
    int i,j,Increment;
    int temp;
    for(Increment=n/2;Increment>0;Increment/=2){
        for(i=Increment;i<n;i++){
            temp=a[i];
            for(j=i;j>=Increment;j-=Increment)
            if(temp<a[j-Increment])
            a[j]=a[j-Increment];
            else break;
            a[j]=temp;
        }
    }
}
int main(){
    int a[]={4,3,2,7,1,6,8,2,9,5};
    shellsort(a,10);
    for(int i=0;i<10;i++)
    cout<<a[i]<<" ";
    system("pause");
    return 0;
}

归并排序

归并排序是一种采用了 分治 思想的排序算法。

归并排序分为三个过程：

  1. 将数列划分为两部分（在均匀划分时时间复杂度为 O（nlogn）；
  2. 递归地分别对两个子序列进行归并排序；
  3. 合并两个子序列。

不难发现，归并排序的核心是如何合并两个子序列，前两步都很好实现。直接撂代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
void merge(int A[], int L1, int R1, int L2, int R2)
{
    int i = L1, j = L2;
    int temp[maxn], index = 0;//temp临时储存变量
    while (i <= R1 && j <= R2)
    {
        if (A[i] <= A[j])
        {
            temp[index++] = A[i++];//如果满足条件将A[i]加入temp
        }
        else
        {
            temp[index++] = A[j++];//否则加入A[j]
        }
    }
    while (i <= R1)
        temp[index++] = A[i++];//加入剩余元素
    while (j <= R2)
        temp[index++] = A[j++];
    for (i = 0; i < index; i++)
    {
        A[L1 + i] = temp[i];//合并或的序列赋值回数组A
    }
}
void mergeSort(int A[], int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        mergeSort(A, left, mid);
        mergeSort(A, mid + 1, right);
        merge(A,left,mid,mid+1,right);
    }
}
int main()
{
    int A[] = {1, 5, 4, 7, 3, 6, 8, 2, 9};
    mergeSort(A, 0, 8);
    for (int i = 0; i < 9; i++)
    {
        cout << A[i];
    }
    system("pause");
    return 0;
}

啊，对了加上非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
void mergeSort(int A[])
{
    for (int step = 2; step / 2 < n; step *= 2)
    {
        for (int i = 1; i <= n; i += step)
        {
            int mid = i + step / 2 - 1;
            if (mid + 1 <= n)
                merge(A, i, mid, mid + 1, min(i + step - 1, n));
        }
    }
}

如果想观察每一次排序后的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
void merge(int a[])
{
    for (int step = 2; step / 2 < 9; step *= 2)
    {
        for (int i = 0; i < 9; i += step)
        {
            sort(a + i, a + min(i + step, 10));
        }
        for (int i = 0; i < 9; i++)
            cout << a[i] << " ";
        cout << "\n";
    }
}

基数排序

首先，我们要有十个桶，和一个大桶（桶里的数根据先到先出的顺序，是一个队列，下文不作说明了）

第一步，把数组里的数依次放到桶里；

第二步，把倒数第i位（i从1开始）为k的数放到第k个桶里；

第三步，从第一个桶开始，把所有数放到大桶里；

第四步，重复第二、三步，直到所有数中的最大数倒数第i位是0；

排序完成

例如对{41, 467, 334, 500, 169, 724, 478, 358, 962, 464}进行基数排序。

1、–> {500}, {41}, {962}, {334, 464}, {467}, {478, 358}, {169}

2、–> {500, 41, 962, 334, 464, 467, 478, 358, 169}

3、–> {500}, {724}, {334}, {41}, {358}, {962, 467, 169}, {478}

4、–> {500, 724, 334, 41, 358, 962, 467, 169, 478}

5、–> {041}, {169}, {334, 358}, {464, 467, 478}, {500}, {724}, {962}

6、–> {041, 169, 334, 358, 464, 467, 478, 500, 724, 962}

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
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
#include<bits/stdc++.h>

using namespace std;

// 求出数组中最大数的位数的函数
int MaxBit(vector<int> input)
{
    // 数组最大值
    int max_data = input[0];
    for (int i = 1; i < input.size(); i++)
    {
        if (input[i] > max_data)
        {
            max_data = input[i];
        }
    }

    // 数组最大值的位数
    int bits_num = 0;
    while (max_data)
    {
        bits_num++;
        max_data /= 10;
    }

    return bits_num;
}

// 取数xxx上的第d位数字
int digit(int num, int d)
{
    int pow = 1;
    while (--d > 0)
    {
        pow *= 10;
    }
    return num / pow % 10;
}

// 基数排序
vector<int> RadixSort(vector<int> input, int n)
{
    // 临时数组，用来存放排序过程中的数据
    vector<int> bucket(n);
    // 位记数器，从第0个元素到第9个元素依次用来记录当前比较位是0的有多少个...是9的有多少个数
    vector<int> count(10);
    // 从低位往高位循环
    for (int d = 1; d <= MaxBit(input); d++)
    {
        // 计数器清0
        for (int i = 0; i < 10; i++)
        {
            count[i] = 0;
        }

        // 统计各个桶中的个数
        for (int i = 0; i < n; i++)
        {
            count[digit(input[i], d)]++;
        }

        /*
        * 比如某次经过上面统计后结果为：[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]则经过下面计算后 结果为： [0, 2,
        * 5, 8, 8, 8, 8, 8, 8, 8]但实质上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中
        * 非零数才用到，因为其他位不存在，它们分别表示如下：2表示比较位为1的元素可以存放在索引为1、0的
        * 位置，5表示比较位为2的元素可以存放在4、3、2三个(5-2=3)位置，8表示比较位为3的元素可以存放在
        * 7、6、5三个(8-5=3)位置
        */
        for (int i = 1; i < 10; i++)
        {
            count[i] += count[i - 1];
        }

        /*
        * 注，这里只能从数组后往前循环，因为排序时还需保持以前的已排序好的顺序，不应该打
        * 乱原来已排好的序，如果从前往后处理，则会把原来在前面会摆到后面去，因为在处理某个
        * 元素的位置时，位记数器是从大到到小（count[digit(arr[i], d)]--）的方式来处
        * 理的，即先存放索引大的元素，再存放索引小的元素，所以需从最后一个元素开始处理。
        * 如有这样的一个序列[212,213,312]，如果按照从第一个元素开始循环的话，经过第一轮
        * 后（个位）排序后，得到这样一个序列[312,212,213]，第一次好像没什么问题，但问题会
        * 从第二轮开始出现，第二轮排序后，会得到[213,212,312]，这样个位为3的元素本应该
        * 放在最后，但经过第二轮后却排在了前面了，所以出现了问题
        */
        for (int i = n - 1; i >= 0; i--)
        {
            int k = digit(input[i], d);
            bucket[count[k] - 1] = input[i];
            count[k]--;
        }

        // 临时数组复制到 input 中
        for (int i = 0; i < n; i++)
        {
            input[i] = bucket[i];
        }
    }

    return input;
}

int main()
{
    int arr[] = {50, 123, 543, 187, 49, 30, 0, 2, 11, 100};
    vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
    cout << "排序前:";
    for (int i = 0; i < test.size(); i++)
    {
        cout << test[i] << " ";
    }
    cout << endl;

    vector<int> result = test;
    result = RadixSort(result, result.size());
    cout << "排序后:";
    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}

传统艺能

最后给你们整个绝活，咕咕咕咕咕咕，这篇排序前前后后鸽了快一个月才写完，也参考了几篇文章。之所以为什么要鸽一个月嘛…因为当鸽子是真的爽。