排序算法
插入排序
算法思路
- 从第一个元素开始，该元素可以认为已经被排序
- 取下一个元素tem，从已排序的元素序列从后往前扫描
- 如果该元素大于tem，则将该元素移到下一位
- 重复步骤3，直到找到已排序元素中小于等于tem的元素
- tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
- 重复步骤2~5
一句话总结：每次取第$i+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
|
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n - 1; ++i)
{
//记录有序序列最后一个元素的下标
int end = i;
//待插入的元素
int tem = arr[end + 1];
//单趟排
while (end >= 0)
{
//比插入的数大就向后移
if (tem < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
//比插入的数小，跳出循环
else
{
break;
}
}
//tem放到比插入的数小的数的后面
arr[end + 1] = tem;
//代码执行到此位置有两种情况:
//1.待插入元素找到应插入位置（break跳出循环到此）
//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）
}
}
|
时间复杂度：最坏情况下为O(N²)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)
希尔排序
思路：
- 先选定一个小于N的gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作
- 当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
一句话总结：第一次取gap=n/2，然后距离为gap的两个元素按照大小顺序决定是否交换，然后第二次取gap=gap/2，以此类推，直到gap减小到1，进行一次直接插入排序，排序完成
如上图所示，在初始位置gap=10/2=5，将距离为5的元素分在同一组，即（8，3）、（9，5）、（1，4）、（7，6）、（2、0），每组内的两个元素比较后依照插入排序更新位置 排序结束后取gap/=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
|
//希尔排序
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap>1)
{
//每次对gap折半操作
gap = gap / 2;
//单趟排序
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int tem = arr[end + gap];
while (end >= 0)
{
if (tem < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tem;
}
}
}
|
时间复杂度（平均）：O（N^1.3） 空间复杂度：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
|
//选择排序
void swap(int* a, int* b)
{
int tem = *a;
*a = *b;
*b = tem;
}
void SelectSort(int* arr, int n)
{
//保存参与单趟排序的第一个数和最后一个数的下标
int begin = 0, end = n - 1;
while (begin < end)
{
//保存最大值的下标
int maxi = begin;
//保存最小值的下标
int mini = begin;
//找出最大值和最小值的下标
for (int i = begin; i <= end; ++i)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
//最小值放在序列开头
swap(&arr[mini], &arr[begin]);
//防止最大的数在begin位置被换走
if (begin == maxi)
{
maxi = mini;
}
//最大值放在序列结尾
swap(&arr[maxi], &arr[end]);
++begin;
--end;
}
}
|
时间复杂度：最坏情况：O(N^2)
最好情况：O(N^2)
空间复杂度：O(1)
计数排序
计数排序是一种非比较排序，其核心是将序列中的元素作为键存储在额外的数组空间中，而该元素的个数作为值存储在数组空间中，通过遍历该数组排序。
计数排序的应用场景
- 序列中最大值和最小值之间的差值不能过大，这主要是防止建立数组时造成内存的浪费。
- 序列中存在的元素是整数，因为我们使用的是该元素作为键存储在额外的数组空间中，如果不是整数，不能作为键。
代码
创建临时数组
我们先创建一个临时的数组tmp并且该数组的最大下标为原数组中元素的最大值（里面的元素初始化为0）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
//先遍历原数组找到最大值
int max = a[0];
for (int i = 1; i < n; i++)
{
if (max < a[i])
{
max = a[i];
}
}
//动态内存开辟max+1个int空间并初始化为0用calloc
int* tmp = (int)calloc(max+1, sizeof(int));
if (tmp == NULL)
{
perror("calloc fail!\n");
return;
}
|
统计次数
然后遍历一遍原数组，原数组中出现哪个元素就在tmp数组中与该元素数值相同的下标对应的地方进行加加操作来记录该元素出现的次数。
1
2
3
4
5
|
//统计次数
for (int i = 0; i < n; i++)
{
tmp[a[i]]++;
}
|
排序
最后我们再进行排序，记住tmp的下标对应原数组可能出现的元素，而里面的值对应该元素出现的次数，如果为0就说明该元素在原数组不存在。遍历tmp数组，将对应的下标覆盖原数组即可完成排序。
1
2
3
4
5
6
7
8
9
10
11
12
|
//排序
int j = 0;
for (int i = 0; i < max + 1; i++)//第一层循环遍历tmp数组
{
while (tmp[i]--)//对应元素出现的次数
{
a[j++] = i;//tmp的下标对应的就是原数组可能出现的元素
}
}
//释放资源，避免内存泄漏
free(tmp);
tmp = NULL;
|
简单版本
完整代码如下：(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
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
void CountSort(std::vector<int>& a)
{
// 如果数组为空，直接返回
if (a.empty()) return;
// 使用std::max_element找到数组中的最大值
int max = *std::max_element(a.begin(), a.end());
// 创建一个大小为(max + 1)的数组，初始值都为0
std::vector<int> tmp(max + 1, 0);
// 统计每个元素的出现次数
for (int num : a)
{
tmp[num]++;
}
// 排序阶段
int j = 0;
// 遍历tmp数组，按照每个元素出现的次数重新填充原数组a
for (int i = 0; i <= max; ++i)
{
// 当tmp[i]不为0时，将i填充到a数组中tmp[i]次
while (tmp[i]--)
{
a[j++] = i;
}
}
}
int main() {
// 示例数组
std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
// 调用计数排序函数
CountSort(arr);
// 输出排序后的数组
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
|
优化
如果我们的数据是这样的，如果还像之前那样开辟空间，会有大量的空间浪费遍历的次数增大，就存在性能的降低 
如图，数据的最小值为100，而按照原代码则浪费了0-100中的数组空间，导致不必要的内存开销
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
|
#include <iostream>
#include <vector>
#include <algorithm>
void CountSort(std::vector<int>& a)
{
if (a.empty()) return;
// 使用std::min和std::max找出数组的最小值和最大值
int min = *std::min_element(a.begin(), a.end());
int max = *std::max_element(a.begin(), a.end());
int range = max - min + 1;
// 创建一个大小为range的vector，初始化为0
std::vector<int> tmp(range, 0);
// 统计每个元素出现的次数
for (int num : a)
{
tmp[num - min]++;
}
// 排序阶段
int j = 0;
for (int i = 0; i < range; ++i)
{
// 将tmp[i]个i+min值填充到a中
while (tmp[i]--)
{
a[j++] = i + min;
}
}
}
int main() {
// 示例数组
std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
// 调用计数排序函数
CountSort(arr);
// 输出排序后的数组
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
|
空间复杂度：除原数组外，计数排序额外开辟了一个大小为N的临时空间，所以计数排序的空间复杂度为O(N)。 时间复杂度：遍历找最大最小值取范围的时间复杂度为O(N)，遍历原数组统计次数的时间复杂度为O(N)，而排序里面，虽有两层循环，但从思想和本质来看，它只不过是将原来的元素按顺序覆盖了原数组，其执行循环的次数任然为O(N)，所以计数排序的时间复杂度为O(N).
归并排序
算法思路
归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。
将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。
一句话总结：第一次分为两组，第二次每一组又分为两组，也就是$2^2=4$组，以此类推，直到每组的元素个数为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
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
|
#include <iostream>
#include <vector>
struct MergeSort {
// 主排序函数
void sort(std::vector<int>& arr) {
if (!arr.empty()) {
mergeSort(arr, 0, arr.size() - 1);
}
}
private:
// 合并两个已排序的子数组
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1; // 左子数组的大小
int n2 = right - mid; // 右子数组的大小
std::vector<int> L(n1); // 创建左子数组
std::vector<int> R(n2); // 创建右子数组
// 将数据拷贝到临时数组 L[] 和 R[]
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 合并临时数组
int i = 0; // 初始索引 L
int j = 0; // 初始索引 R
int k = left; // 初始索引合并后的数组
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制 L[] 中剩余的元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 复制 R[] 中剩余的元素
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 归并排序函数
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// 递归排序左右半部分
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并已排序的部分
merge(arr, left, mid, right);
}
}
};
// 主函数
int main() {
std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
std::cout << "原数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
MergeSort sorter;
sorter.sort(arr); // 调用排序函数
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
|
堆排序
算法思路
因为建小堆可以选出最小的数即根节点，我们将每次建好的小堆的最后一个叶子节点和根节点进行交换，交换后不把最后一个数看作堆里的数据，此时根的左右子树依旧是大堆，然后我们再用向下调整算法选出次小的如此循环直到堆里剩一个数结束
• 升序建大堆
• 降序建小堆
代码
堆排序(降序)实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
//降序
void HeapSort(int* a, int n)
{
//建小堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
//把最小的换到最后一个位置，不把最后一个数看作堆里的
//每次选出剩下数中最小的
//从后往前放
while (end > 0)
{
int tem = a[end];
a[end] = a[0];
a[0] = tem;
//选出次小的数
AdjustDown(a, end, 0);
--end;
}
}
|
最坏的情况及满二叉树，且每个节点都需要调整
由以上推论过程可得建堆的时间复杂度为$O(N)$;
向下调整算法的时间复杂度为$O(log_2N$);
所以堆排序的时间复杂度为$O(Nlog_2N$);
快速排序
快排的实现方法有三种，逐一介绍：
hoare版本(左右指针法)
算法思路
1、选出一个key，一般是最左边或是最右边的。
2、定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要begin先走）。
3、在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
4.此时key的左边都是小于key的数，key的右边都是大于key的数
5.将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序
单趟动图如下：
代码
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
|
//快速排序 hoare版本(左右指针法)
void QuickSort(int* arr, int begin, int end)
{
//只有一个数或区间不存在
if (begin >= end)
return;
int left = begin;
int right = end;
//选左边为key
int keyi = begin;
while (begin < end)
{
//右边选小 等号防止和key值相等 防止顺序begin和end越界
while (arr[end] >= arr[keyi] && begin < end)
{
--end;
}
//左边选大
while (arr[begin] <= arr[keyi] && begin < end)
{
++begin;
}
//小的换到右边，大的换到左边
swap(&arr[begin], &arr[end]);
}
swap(&arr[keyi], &arr[end]);
keyi = end;
//[left,keyi-1]keyi[keyi+1,right]
QuickSort(arr, left, keyi - 1);
QuickSort(arr,keyi + 1,right);
}
|
挖坑法
代码可分为递归和非递归两种
算法思路
挖坑法思路与hoare版本(左右指针法)思路类似
1.选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑
2、还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）
单趟动图如下：
代码可分为递归和非递归两种
递归算法代码
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 QuickSort1(int* arr, int begin, int end)
{
if (begin >= end)
return;
int left = begin,right = end;
int key = arr[begin];
while (begin < end)
{
//找小
while (arr[end] >= key && begin < end)
{
--end;
}
//小的放到左边的坑里
arr[begin] = arr[end];
//找大
while (arr[begin] <= key && begin < end)
{
++begin;
}
//大的放到右边的坑里
arr[end] = arr[begin];
}
arr[begin] = key;
int keyi = begin;
//[left,keyi-1]keyi[keyi+1,right]
QuickSort1(arr, left, keyi - 1);
QuickSort1(arr, keyi + 1, right);
}
|
非递归算法代码
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
|
//单趟排
int PartSort(int* arr, int begin, int end)
{
int key = arr[begin];
while (begin < end)
{
while (key <= arr[end] && begin < end)
{
--end;
}
arr[begin] = arr[end];
while (key >= arr[begin] && begin < end)
{
++begin;
}
arr[end] = arr[begin];
}
arr[begin] = key;
int meeti = begin;
return meeti;
}
void QuickSortNoR(int* arr, int begin, int end)
{
stack<int> st;
//先入右边
st.push(end);
//再入左边
st.push(begin);
while (!st.empty())
{
//左区间
int left = st.top();
st.pop();
//右区间
int right = st.top();
st.pop();
//中间数
int mid = PartSort(arr, left, right);
//当左区间>=mid-1则证明左区间已经排好序了
if (left < mid - 1)
{
st.push(mid - 1);
st.push(left);
}
//当mid+1>=右区间则证明右区间已经排好序
if (right > mid + 1)
{
st.push(right);
st.push(mid + 1);
}
}
}
|
前后指针法
算法思路
1、选出一个key，一般是最左边或是最右边的。
2、起始时，prev指针指向序列开头，cur指针指向prev+1。
3、若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur到达end位置，此时将key和++prev指针指向的内容交换即可。
经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。
然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
//快速排序法 前后指针版本
void QuickSort2(int* arr, int begin, int end)
{
if (begin >= end)
return;
int cur = begin, prev = begin - 1;
int keyi = end;
while (cur != keyi)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
swap(&arr[cur], &arr[prev]);
}
++cur;
}
swap(&arr[++prev],&arr[keyi]);
keyi = prev;
//[begin,keyi -1]keyi[keyi+1,end]
QuickSort2(arr, begin, keyi - 1);
QuickSort2(arr, keyi + 1, end);
}
|
一句话总结：快速排序的模糊解释就是先选择一个元素作为标准元素key，让比key小的放在key左边，比key大的放在key右边，最后在key的两边分别做相同的排序，得到最终排序结果