1. 常见的内部排序算法汇总-C++描述
排序：将无序的元素序列，通过一定的方法按照关键字顺序排列的过程。排序分为内部排序和外部排序：
- 内部排序：整个排序过程不需要访问外存便能完成。
- 外部排序：整个序列的排序过程不可能在内存中完成，需要借助外存才能完成，通常参加排序的数据量很大。
若经过排序，元素之间的相对次序保持不变，则称这种排序算法是稳定的，否则称为不稳定的。
本文是对内部排序算法的总结。
下表给出了常见的排序算法的性能：
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 希尔排序 | $O(nlogn)$~$O(n^2)$ | $O(n^{1.3})$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 堆排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(1)$ | 不稳定 |
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 快速排序 | $O(nlogn)$ | $O(nlogn)$ | $O(n^2)$ | $O(logn)$~$O(n)$ | 不稳定 |
| 归并排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ | 稳定 |
| 计数排序 | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | 稳定 |
注：本文的实现都是从小到大排序。如果要看直观的动态排序图，参考参考资料中对应的链接。
1.1. 插入排序（Insertion Sort）
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到$O(1)$的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
算法步骤：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
时间复杂度：
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| $O(n^2)$ | $O(n)$ | $O(n^2)$ |
空间复杂度：总共$O(n)$，需要辅助空间$O(1)$。
稳定性：稳定
优化：如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的次数，称为二分插入排序（代码略，以后补充）。
代码：
1 | /* |
代码输出：1
0 1 2 3 4 5 6 7 8 9
1.2. 希尔排序（Shell Sort）
希尔排序（Shell Sort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
算法步骤：
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。
例如，假设有这样一组数${\lbrace}13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10{\rbrace}$，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：
1 | 13 14 94 33 82 |
然后我们对每列进行排序：
1 | 10 14 73 25 23 |
将上述四行数字，依序接在一起时我们得到：${\lbrace}10, 14, 73, 25, 23, 13, 27, 94, 33, 39, 25, 59, 94, 65, 82, 45{\rbrace}$.这时10已经移至正确位置了，然后再以3为步长进行排序：
1 | 10 14 73 |
排序之后变为：
1 | 10 14 13 |
最后以1步长进行排序（此时就是简单的插入排序了）。
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。
Donald Shell最初建议步长选择为$n/2$，并且对步长取半直到步长达到1。（本文如下代码既是采用这种方法实现）
时间复杂度：
最好的时间复杂度为$O(n)$，而最坏时间复杂度和平均时间复杂度都要根据步长序列的不同而不同。
空间复杂度：$O(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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/*
* 内部排序算法：希尔排序
*/
using namespace std;
/*
* @function: 重载<<操作符
* @param: out: 输出流
* @parma: vec: 待输出的向量
* @return: 输出流
*/
template<typename T>
ostream& operator<<(ostream& out, vector<T>& vec){
for (int i = 0; i < vec.size(); ++i)
out << vec[i] << ' ';
return out;
}
/*
* @function: 希尔排序，实现从小到大排序
* @parma: vec: 待排序的序列，类型T必须定义（重载）了关系运算符('<'或'>')
*/
template<typename T>
void shellSort(vector<T>& vec){
size_t n = vec.size();
T temp;
for (int step = n >> 1; step > 0; step >>= 1){
for (int i = step; i < n; ++i){
T temp = vec[i];
int j = i - step;
for (; j >= 0; j -= step){
if (vec[j] > temp) vec[j+step] = vec[j];
else break;
}
vec[j+step] = temp;
}
}
}
int main(int argc, char** argv){
int arr[] = {8, 6, 9, 2, 4, 1, 3, 0, 7, 5};
int n = sizeof(arr)/sizeof(int);
vector<int> vec(arr, arr+n);
shellSort(vec);
cout << vec << endl;
return 1;
}
代码输出：1
0 1 2 3 4 5 6 7 8 9
1.3. 选择排序（Selection Sort）
选择排序（Selection sort）是一种简单直观的排序算法。
算法步骤：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
时间复杂度：
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| $O(n^2)$ | $O(n^2)$ | $O(n^2)$ |
空间复杂度：总共$O(n)$，需要辅助空间$O(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
33
34
35
36
37
38
39
40
41
42
43
44
45/*
* 内部排序算法：选择排序
*/
using namespace std;
/*
* @function: 重载<<操作符
* @param: out: 输出流
* @parma: vec: 待输出的向量
* @return: 输出流
*/
template<typename T>
ostream& operator<<(ostream& out, vector<T>& vec){
for (int i = 0; i < vec.size(); ++i)
out << vec[i] << ' ';
return out;
}
/*
* @function: 选择排序，实现从小到大排序
* @parma: vec: 待排序的序列，类型T必须定义（重载）了关系运算符('<'或'>')
*/
template<typename T>
void selectSort(vector<T>& vec){
size_t n = vec.size();
for (int i = 0; i < n; ++i){
int min = i;
for (int j = i + 1; j < n; ++j){
if (vec[j] < vec[min]) min = j;
}
if (min != i) swap(vec[i], vec[min]);
}
}
int main(int argc, char** argv){
int arr[] = {8, 6, 9, 2, 4, 1, 3, 0, 7, 5};
int n = sizeof(arr)/sizeof(int);
vector<int> vec(arr, arr+n);
selectSort(vec);
cout << vec << endl;
return 1;
}
代码输出：1
0 1 2 3 4 5 6 7 8 9
1.4. 堆排序（Heap Sort）
堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆节点的访问：
通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：
- 父节点$i$的左子节点在位置$2*i+1$;
- 父节点$i$的右子节点在位置$2*i+2$;
- 子节点$i$的父节点在位置${\lfloor}(i-1)/2{\rfloor}$;
堆的操作：
在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：
- 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点；
- 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序；
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。
算法步骤：
- 创建一个最大堆heap[0:n-1]；
- 把堆首（最大值）和堆尾互换；
- 把堆的尺寸缩小1，并从根开始重新调整，使其成为一个堆；
- 重复步骤2~3，直到堆的尺寸为1。
时间复杂度：
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ |
空间复杂度：总共$O(n)$，需要辅助空间$O(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
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/*
* 内部排序算法：堆排序
*/
using namespace std;
/*
* @function: 重载<<操作符
* @param: out: 输出流
* @parma: vec: 待输出的向量
* @return: 输出流
*/
template<typename T>
ostream& operator<<(ostream& out, vector<T>& vec){
for (int i = 0; i < vec.size(); ++i)
out << vec[i] << ' ';
return out;
}
/*
* @function: 在vec中调整以root为根的子树
* @param: vec: 待排序的序列，类型T必须定义（重载）了关系运算符('<'或'>')
* @param: root: 调整以节点root为根的子树
* @param: n: 调整的的节点索引要小于n，即能调整到的最大编号
*/
template<typename T>
void adjustHeap(vector<T>& vec, int root, int n){
if (root >= n) return;
while (2*root+1 < n){ // 左孩子存在
int child = 2*root+1; // 左孩子
if (2*root+2 < n && vec[2*root+2] > vec[child])
child = 2*root+2; // 取以 root 节点为根的左右孩子值较大的那个
if (vec[child] > vec[root]) // 如果孩子较大的那个比根还大，则交换它们
swap(vec[root], vec[child]);
root = child; // 根元素的下沉过程
}
}
/*
* @function: 堆排序，实现从小到大排序，构建最大堆
* @parma: vec: 待排序的序列，类型T必须定义（重载）了关系运算符('<'或'>')
*/
template<typename T>
void heapSort(vector<T>& vec){
size_t n = vec.size();
for (int i = (n>>1)-1; i >= 0; --i) // 将待排序序列先调整为一个最大堆
adjustHeap(vec, i, n);
for (int i = n-1; i > 0; --i){
swap(vec[0], vec[i]); // 将根元素与最后一个未排序的元素交换
adjustHeap(vec, 0, i); // // 重新调整以根结点的堆，调整的长度为未排序的长度
}
}
int main(int argc, char** argv){
int arr[] = {8, 6, 9, 2, 4, 1, 3, 0, 7, 5};
int n = sizeof(arr)/sizeof(int);
vector<int> vec(arr, arr+n);
heapSort(vec);
cout << vec << endl;
return 1;
}
代码输出：1
0 1 2 3 4 5 6 7 8 9
1.5. 冒泡排序（Bubble Sort）
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法步骤：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
时间复杂度：
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| $O(n^2)$ | $O(n)$ | $O(n^2)$ |
空间复杂度：总共$O(n)$，需要辅助空间$O(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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/*
* 内部排序算法：冒泡排序
*/
using namespace std;
/*
* @function: 重载<<操作符
* @param: out: 输出流
* @parma: vec: 待输出的向量
* @return: 输出流
*/
template<typename T>
ostream& operator<<(ostream& out, vector<T>& vec){
for (int i = 0; i < vec.size(); ++i)
out << vec[i] << ' ';
return out;
}
/*
* @function: 冒泡排序，实现从小到大排序
* @parma: vec: 待排序的序列，类型T必须定义（重载）了关系运算符('<'或'>')
*/
template<typename T>
void bubbleSort(vector<T>& vec){
size_t n = vec.size();
for (int i = 0; i < n-1; ++i){
bool flag = false; // 标志位，判断一次冒泡中是否有交换
for (int j = 0; j < n-i-1; ++j){
if (vec[j] > vec[j+1]){
swap(vec[j], vec[j+1]); // 冒泡
flag = true; // 有交换，置flag为true
}
}
if (!flag) break; // 如果没有交换，则说明剩下的元素已经是有序的，此时可直接退出循环
}
}
int main(int argc, char** argv){
int arr[] = {8, 6, 9, 2, 4, 1, 3, 0, 7, 5};
int n = sizeof(arr)/sizeof(int);
vector<int> vec(arr, arr+n);
bubbleSort(vec);
cout << vec << endl;
return 1;
}
代码输出：1
0 1 2 3 4 5 6 7 8 9
1.6. 快速排序（Quick Sort）
快速排序（Quicksort），又称划分交换排序（partition-exchange sort），是一种排序算法，它使用分治法策略来把一个序列分为两个子序列。它通常明显比其他$O(nlogn)$算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
算法步骤：
- 从数列中挑出一个元素，称为
基准（pivot）； - 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
【注】：基准的选择可以选择数列的第一个元素或者最后一个元素或者中间的元素，更好的是选择这三个特殊元素按大小排列后，位于中间的那个元素。
时间复杂度：
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| $O(nlogn)$ | $O(nlogn)$ | $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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74/*
* 内部排序算法：快速排序
*/
using namespace std;
/*
* @function: 重载<<操作符
* @param: out: 输出流
* @parma: vec: 待输出的向量
* @return: 输出流
*/
template<typename T>
ostream& operator<<(ostream& out, vector<T>& vec){
for (int i = 0; i < vec.size(); ++i)
out << vec[i] << ' ';
return out;
}
/*
* @function: 将vec按照vec[low]元素的值分为左右两部分，左边的元素值都比vec[low]小，右边的元素值都比vec[high]大
* @param: vec: 待排序的序列
* @param: low: 待排序序列的最左端的索引
* @param: high: 待排序序列的最右端的索引
* @return: 基准值所在的索引
*/
template<typename T>
int partition(vector<T>& vec, int low, int high){
int pivotKey = vec[low];
while (low < high){
while (low < high && vec[high] >= pivotKey)
--high;
swap(vec[low], vec[high]);
while (low < high && vec[low] <= pivotKey)
++low;
swap(vec[low], vec[high]);
}
return low;
}
/*
* @function: 用快速排序算法将vec序列中从low到high的子序列排序
* @param: vec: 待排序的序列
* @param: low: 待排序序列的最左端的索引
* @param: high: 待排序序列的最右端的索引
*/
template<typename T>
void qSort(vector<T>& vec, int low, int high){
if (low < high){
int pivot = partition(vec, low, high);
qSort(vec, low, pivot-1);
qSort(vec, pivot+1, high);
}
}
/*
* @function: 快速排序，实现从小到大排序
* @parma: vec: 待排序的序列，类型T必须定义（重载）了关系运算符('<'或'>')
*/
template<typename T>
void quickSort(vector<T>& vec){
qSort(vec, 0, vec.size()-1);
}
int main(int argc, char** argv){
int arr[] = {8, 6, 9, 2, 4, 1, 3, 0, 7, 5};
int n = sizeof(arr)/sizeof(int);
vector<int> vec(arr, arr+n);
quickSort(vec);
cout << vec << endl;
return 1;
}
代码输出：1
0 1 2 3 4 5 6 7 8 9
1.7. 归并排序（Merge Sort）
归并排序（Merge Sort），是创建在归并操作上的一种有效的排序算法，效率为$O(nlogn)$。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法的一个非常典型的应用，且各层分治递归可以同时进行。
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
该算法可通过迭代法和递归法两种方法实现。
递归法步骤：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤3直到某一指针到达序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
迭代法步骤：
- 将序列每相邻两个数字进行归并操作，形成${\lceil}n/2{\rceil}$个序列，排序后每个序列包含两个元素；
- 将上述序列再次归并，形成${\lceil}n/4{\rceil}$个序列，每个序列包含四个元素；
- 重复步骤2，直到所有元素排序完毕。
时间复杂度：
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| $O(nlogn)$ | $O(n)$ | $O(nlogn)$ |
空间复杂度：$O(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
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/*
* 内部排序算法：归并排序（递归实现）
*/
using namespace std;
/*
* @function: 重载<<操作符
* @param: out: 输出流
* @parma: vec: 待输出的向量
* @return: 输出流
*/
template<typename T>
ostream& operator<<(ostream& out, vector<T>& vec){
for (int i = 0; i < vec.size(); ++i)
out << vec[i] << ' ';
return out;
}
/*
* @function: 将vec[low:mid]和vec[mid+1:high]两部分合并为一个向量
* @param: vec: 待排序的序列
* @param: low: 第一个待排序序列的最左端的索引
* @param: mid: 第一个待排序序列的最右端的索引
* @param: high: 第二个待排序序列的最右端的索引
*/
template<typename T>
void merge(vector<T>& vec, int low, int mid, int high){
int i = low, m = mid;
int j = mid+1, n = high;
vector<T> tempVec(high-low+1);
int index = 0;
while (i <= m && j <= n){
tempVec[index++] = (vec[i]<=vec[j]) ? vec[i++] : vec[j++];
}
while (i <= m){
tempVec[index++] = vec[i++];
}
while (j <= n){
tempVec[index++] = vec[j++];
}
for (int k = 0; k < tempVec.size(); ++k)
vec[low++] = tempVec[k];
}
/*
* @function: 用归并排序算法将vec序列中从low到high的子序列排序
* @param: vec: 待排序的序列
* @param: low: 待排序序列的最左端的索引
* @param: high: 待排序序列的最右端的索引
*/
template<typename T>
void mSort(vector<T>& vec, int low, int high){
if (low < high){
int mid = low + (high-low)/2;
mSort(vec, low, mid);
mSort(vec, mid+1, high);
merge(vec, low, mid, high);
}
}
/*
* @function: 归并排序，实现从小到大排序
* @parma: vec: 待排序的序列，类型T必须定义（重载）了关系运算符('<'或'>')
*/
template<typename T>
void mergeSort(vector<T>& vec){
mSort(vec, 0, vec.size()-1);
}
int main(int argc, char** argv){
int arr[] = {8, 6, 9, 2, 4, 1, 3, 0, 7, 5};
int n = sizeof(arr)/sizeof(int);
vector<int> vec(arr, arr+n);
mergeSort(vec);
cout << vec << endl;
return 1;
}
代码输出：1
0 1 2 3 4 5 6 7 8 9
1.8. 计数排序（Counting Sort）
计数排序（Counting sort）是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。
计数排序不是比较排序，排序的速度快于任何比较排序算法。但是对于数据范围很大的数组，需要大量的时间和内存。
时间复杂度：
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| $O(n+k)$ | $O(n+k)$ | $O(n+k)$ |
空间复杂度：$O(n+k)$（k表示元素的范围大小，比如元素范围为i到i+k-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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/*
* 内部排序算法：计数排序
*/
using namespace std;
/*
* @function: 重载<<操作符
* @param: out: 输出流
* @parma: vec: 待输出的向量
* @return: 输出流
*/
template<typename T>
ostream& operator<<(ostream& out, vector<T>& vec){
for (int i = 0; i < vec.size(); ++i)
out << vec[i] << ' ';
return out;
}
/*
* @function: 计数排序，实现从小到大排序
* @parma: vec: 待排序的序列，类型T必须定义（重载）了关系运算符('<'或'>')
*/
template<typename T>
void countSort(vector<T>& vec){
if (vec.empty()) return;
int size = vec.size();
T minElement = vec[0], maxElement = vec[0];
for (int i = 1; i < size; ++i){
if (vec[i] < minElement) minElement = vec[i];
if (vec[i] > maxElement) maxElement = vec[i];
}
vector<int> countVec(maxElement - minElement + 1);
for (int i = 0; i < size; ++i)
++countVec[vec[i]-minElement];
for (int i = 0, j = 0; i < countVec.size(); ++i){
while (countVec[i]--){
vec[j++] = i+minElement;
}
}
}
int main(int argc, char** argv){
int arr[] = {8, 6, 9, 2, 4, 1, 3, 0, 7, 5};
int n = sizeof(arr)/sizeof(int);
vector<int> vec(arr, arr+n);
countSort(vec);
cout << vec << endl;
return 1;
}
代码输出：
1 | 0 1 2 3 4 5 6 7 8 9 |
2. 小结
上述排序算法可分类如下：
- 插入排序类：插入排序，希尔排序
- 选择排序类：选择排序，堆排序
- 交换排序类：冒泡排序，快速排序
- 归并排序类：归并排序
前七中排序都是比较排序，而计数排序不是比较排序，其速度快于任何比较排序。