0%

排序算法的实现

排序算法简介

排序算法顾名思义,就是用来排序的算法,它可以将一组相同类型的元素从无序转变为有序。

排序算法有多种考量指标:

  • 时间复杂度:描述算法的快慢
  • 空间复杂度:描述算法额外占用的存储空间,如果不占用则可以说是原地排序
  • 稳定性:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变

常见的排序算法有:冒泡排序,插入排序,选择排序,归并排序,快速排序,堆排序,计数排序,基数排序,此外似乎还有一个比较奇葩的排序算法叫做睡眠排序。。。

排序算法

接下来实现下前5种排序算法。

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

1
2
3
4
5
6
void popSort(vector<int> &v) {
for (int i = 0; i < v.size() - 1; i++)
for (int j = 0; j < v.size() - i - 1; j++)
if (v[j] > v[j + 1])
swap(v[j], v[j + 1]);
}

是否原地排序:是
是否稳定:是
时间复杂度:O(n^2)

插入排序

将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

1
2
3
4
5
void insertSort(vector<int> &v) {
for (int i = 1; i < v.size(); i++)
for (int j = i; j > 0 && v[j] < v[j - 1]; j--)
swap(v[j], v[j - 1]);
}

是否原地排序:是
是否稳定:是
时间复杂度:O(n^2)

选择排序

选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

1
2
3
4
5
6
7
8
9
10
11
12
void selectSort(vector<int> &v) {
for (int i = 0; i < v.size() - 1; i++) {
int pos = i, minn = v[i];
for (int j = i + 1; j < v.size(); j++) {
if (v[j] < minn) {
pos = j;
minn = v[j];
}
}
swap(v[i], v[pos]);
}
}

是否原地排序:是
是否稳定:否
时间复杂度: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
void merge(vector<int> &v, int l, int m, int r) {
vector<int> num(r - l);
int t1 = l, t2 = m, t = 0;
while (t1 != m && t2 != r) {
if (v[t1] > v[t2])
num[t++] = v[t2++];
else
num[t++] = v[t1++];
}
while (t1 != m)
num[t++] = v[t1++];
while (t2 != r)
num[t++] = v[t2++];

for (int i = 0; i < num.size(); i++)
v[l + i] = num[i];
}

void mergeSort(vector<int> &v, int l, int r) {
if (l + 1 >= r)
return;
int m = (l + r) / 2;
mergeSort(v, l, m);
mergeSort(v, m, r);
merge(v, l, m, r);
}

void mergeSort(vector<int> &v) {
mergeSort(v, 0, v.size());
}

是否原地排序:否
是否稳定:是
时间复杂度:O(nlogn)

快速排序

快速排序也使用了分治的思想,快排的思想是这样的:如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot(哨兵)。

我们遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,将 pivot 放到中间。经过这一步骤之后,数组 p 到 r 之间的数据就被分成了三个部分,前面 p 到 q-1 之间都是小于 pivot 的,中间是 pivot,后面的 q+1 到 r 之间是大于 pivot 的。

根据分治、递归的处理思想,我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据,直到区间缩小为 1,就说明所有的数据都有序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void quickSort(vector<int> &v, int l, int r) {
if (l + 1 >= r)
return;
int p = v[l];
int lp = l, rp = r - 1;
while (lp != rp) {
while (rp > lp && v[rp] >= p)
rp--;
while (lp < rp && v[lp] <= p)
lp++;
swap(v[lp], v[rp]);
}
swap(v[l], v[lp]);
quickSort(v, l, lp);
quickSort(v, lp + 1, r);
}

void quickSort(vector<int> &v) {
quickSort(v, 0, v.size());
}

是否原地排序:是
是否稳定:否
时间复杂度:O(nlogn)

参考文档

想找一个所有排序算法的动图来着的,结果发现一篇写的很好的博客,虽然没有参考,不过收藏了:https://www.cnblogs.com/onepixel/articles/7674659.html