常用排序算法及实现

排序算法

天下排序算法千千万,归根结底思想是不变的,让我们从头开始看看排序算法及实现

选择排序

选择排序的思想

选出数组中最小的元素,将其与第一个元素交换。然后找出次小的元素与第二个元素交换,一直进行下去,直到数组排完。选择排序是一种原址排序

时间复杂度: 平均情况 \(O(N^2)\),最坏情况\(O(N^2)\),最好情况 \(O(N^2)\)

空间复杂度:\(O(1)\)

稳定性:不稳定

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//选择排序
void sort1(vector<int>& vec)
{
for (int i = 0; i < vec.size(); i++)
{
int min = vec[i];
int indexMin = i;
for (int j = i + 1; j < vec.size(); j++)
{
if (vec[j] < min)
{
min = vec[j];
indexMin = j;
}
}
if (indexMin != i)
swap(vec[i], vec[indexMin]);
}
}

插入排序

插入排序的思想

类似于扑克牌排序,依次将牌插入到适合的位置,插入排序的运行时间和输入数据的原始排列顺序密切相关,如果文件较大,并且关键词已经几乎排好序,插入排序比选择排序要快的多。

时间复杂度: 平均情况 \(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
//插入排序
void sort2(vector<int>& vec)
{
int i = vec.size()-1;
int indexMin=i;
//选出最小的值放在第一位
for (; i > 0; i--)
{
if (vec[i] < vec[indexMin])
indexMin = i;
}
swap(vec[0], vec[indexMin]);
//从第三个数开始,与之前的进行倒序比较,遇到比其大的值,便整体后移一位,直到遇到比其小或者等于的值,然后插入这个位置。
for (i = 1; i < vec.size()-1; i++)
{
int j = i+1;
int v = vec[j];
while(vec[j-1] > v)
{
vec[j] = vec[j - 1];
j--;
}
vec[j] = v;
}
}

冒泡排序

冒泡排序的思想

冒泡排序是许多人学的第一种排序算法,遍历文件,如果两个元素的大小顺序不对,就交换,重复这样的操作使文件排好序,其优势是实现简单,但执行的时间较慢。

时间复杂度: 平均情况 \(O(N^2)\),最坏情况\(O(N^2)\),最好情况\(O(N)\)

空间复杂度:\(O(1)\)

稳定性:稳定

实现:

1
2
3
4
5
6
7
8
9
10
11
12
//冒泡排序
void sort3(vector<int>& vec)
{
for (int i = 0; i < vec.size(); i++)
{
for (int j = 0; j < vec.size()-1; j++)
{
if (vec[j] > vec[j + 1])
swap(vec[j], vec[j + 1]);
}
}
}

再提一个冒泡排序的优化,双向冒泡,是为了解决冒泡我那天中的乌龟问题,即假设我们需要将序列A按照升序序列排序。序列中的较小的数字又大量存在于序列的尾部,这样会让小数字在向前移动得很缓慢。双向冒泡可以消除这个问题。双向冒泡便是左右交错的进行冒泡排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//双向冒泡(抖动)排序
void sort5(vector<int>& vec)
{
for (int i = 0; i < vec.size(); i++)
{
if (i % 2 == 0)
{
for (int j = 0; j < vec.size()-1; j++)
{
if (vec[j] > vec[j + 1])
swap(vec[j], vec[j + 1]);
}
}
else
{
for (int j = vec.size() - 1; j > 0; j--)
{
if (vec[j] < vec[j - 1])
swap(vec[j], vec[j - 1]);
}
}
}
}

简单基数排序

简单基数排序的思想

将元素放到一个以其键值为下标的数组位置,然后在依次输出就行了。

时间复杂度: 平均情况 \(O(dN)\),最坏情况\(O(dN)\),最好情况\(O(dN)\)

空间复杂度:\(O(d)\)

稳定性:稳定

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void sort6(vector<int>&vec)
{
int max=vec[0];
for (size_t i = 0; i < vec.size(); i++)
{
if (vec[i] > max)
max = vec[i];
}
vector<int> cnt(max+1,0);
for (int i = 0; size_t(i) < vec.size(); i++)
cnt[vec[i]]++;
size_t j = 0;
for (size_t i = 0; i < cnt.size(); i++)
{
while (cnt[i] > 0)
{
vec[j++] = i;
cnt[i]--;
}
}
}

快速排序

快速排序的思想

最为经典的排序手段,分治法的典型,要排序,则选个参考点,参考点的左边都比参考点小,参考点的右边都比参考点大。如此递归下去
快排的优化可以在对于参考点的选取上,三点取一或者随机数选点都可以。

时间复杂度: 平均情况 \(O(Nlog_2N)\),最坏情况\(O(N^2)\),最好情况\(O(Nlog_2N)\)

空间复杂度:\(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
int partition(vector<int>& vec, int Begin, int End)
{
int x = vec[End-1];
int i = Begin;
for (int j = Begin; j < End-1; j++)
{
if (vec[j] < x)
{
swap(vec[j], vec[i]);
i++;
}
}
swap(vec[End-1], vec[i]);
return i;
}
//快速排序
void quick_sort(vector<int>& vec,int left,int right)
{
if (left < right)
{
int q = partition(vec, left, right);
quick_sort(vec, left, q);
quick_sort(vec, q+1, right);
}
}

希尔排序

希尔排序的思想

在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为 增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。

时间复杂度: 平均情况 \(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
//希尔排序,步长取1 4 7 10...3k+1
void sort4(vector<int>& vec)
{
int i, h;
for (h = 1; h < (vec.size() - 1) / 9; h = 3 * h + 1);
for (; h >0 ; h /= 3)
{
for (i = h; i < vec.size(); i++)
{
int j = i; int v = vec[j];
while (j >= h&&v < vec[j - h])
{
vec[j] = vec[j - h];
j -= h;
}
vec[j] = v;
}
}
}

希尔排序的性能改进主要在于步长的选择,常见的希尔步长如下:

  • 1 2 4 8 16 32 64 …
  • 1 4 13 40 121 364…\(O(N^{1.5})\)
  • 1 2 4 10 23 51 113 249 …
  • 1 8 23 77 281 1073 4193…\(O(N^{1.333})\)
  • 1 2 3 4 6 9 8 12 18 27…\(O(N(log_2N)^2)\)

当然对于步长的研究水太深了,常用的

归并排序

归并排序的思想

同为经典的排序手段,分治法的典型,要排序,先排好左边,再排好右边,再合并左右两边

时间复杂度: 平均情况 \(O(Nlog_2N)\),最坏情况\(O(N^2)\),最好情况\(O(Nlog_2N)\)

空间复杂度:\(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
void merge(vector<int>& vec,int first,int mid,int last,vector<int>& temp)
{
temp.resize(last - first + 1);
int i = first, j = mid;
int k = 0;
while (i < mid && j < last)
{
if (vec[i] < vec[j])
{
temp[k++]=vec[i++];
}
else
{
temp[k++] = vec[j++];
}
}
while (i < mid)
temp[k++] = vec[i++];
while (j<last)
{
temp[k++] = vec[j++];
}
for (int m = 0; m < k; m++)
{
vec[first + m] = temp[m];
}
}
//归并排序
void merge_sort(vector<int>& vec,int first,int last,vector<int>& temp)
{
if (first < last-1)
{
int mid = (first + last)>>1;
merge_sort(vec, first, mid, temp);
merge_sort(vec, mid, last, temp);
merge(vec, first, mid, last, temp);
}
return;
}

堆排序

堆排序的思想

堆排序是一种抽象的树的排序结构,以数据来抽象一个完全二叉树,大根堆要求每个节点的值都不大于其父节点的值,所以对一个数组进行堆排序的过程,便是对全体元素建堆,然后将第一个元素移动到最后,接着对N-1个元素进行建堆维护

堆排序

时间复杂度: 平均情况 \(O(Nlog_2N)\),最坏情况\(O(Nlog_2N)\),最好情况\(O(Nlog_2N)\)

空间复杂度:\(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
//堆排序
//对某个节点下沉调整
void precDown(vector<int>& vec, int i, int N)
{
int child;
if (2 * i + 2 < N)
{
for (; 2 * i + 2 < N; i = child)
{
//child为较大的那个子节点
if (vec[2 * i + 1] > vec[2 * i + 2])
child = 2 * i + 1;
else
child = 2 * i + 2;
if (vec[child] > vec[i])
swap(vec[i], vec[child]);
}
}
else if(2*i+1<N)
{
for (; 2 * i + 1 < N; i = child)
{
child = 2 * i + 1;
if (vec[child] > vec[i])
swap(vec[i], vec[child]);
}
}
}
void heap_sort(vector<int>& vec)
{
//建堆
for (int i = vec.size() / 2; i >= 0; i--)
{
precDown(vec, i, vec.size());
}
for (int i = vec.size() - 1; i > 0; i--)
{
swap(vec[0], vec[i]);
precDown(vec, 0, i);
}
}

测试数据

以上给出的排序算法都可以使用以下程序进行测试

1
2
3
4
5
6
7
8
9
10
#include<vector>
using namespace std;
int main(void)
{
vector<int> vec = { 8,9,4,2,3,4,7,5,2,1,5,4,5,6,4,5,45,221,548,45,213,45,878,5,21,54,58,54,523,564,5 };
vector<int> vec1 = { 8,9,6,5,4 };
vector<int> temp(10);
quick_sort(vec,0,vec.size()-1);
return 0;
}