常用排序算法实现合集

本文记录了冒泡、插入、选择、希尔排序、快排、堆排、归并排序的C++实现

概述

排序一般分为内排序和外排序

  • 内排序:通俗地说排序的过程在内存中执行,没有与外存产生数据交换
  • 外排序:排序的文件存入外存储器,排序过程是借助于内外存数据交换(或归并)来完成

排序的种类

排序一般分为:插入排序、交换排序、选择排序、归并排序、基数排序

插入排序一般是通过移动把数据插入到合适位置来完成排序的,这类排序有:

  • 直接插入排序
  • 折半插入排序
  • 希尔排序

交换排序一般是通过比较交换两个位置的值来达到排序的目的,这类排序有:

  • 冒泡排序
  • 快速排序

选择排序一般是先选择某个数放到某个位置,这类排序有:

  • 直接选择排序
  • 堆选择排序

冒泡排序

重复遍历过要排序的数列,依次比较两个元素,如果他们的顺序错误(在此错误取决于升序或降序)就把他们交换过来。 遍历的工作是重复的进行直到没有再交换,也即是排序完成。

item description
平均时间复杂度 \(O(n^{2})\)
最优时间复杂度 \(O(n)\)
最差时间复杂度 \(O(n^{2})\)
空间复杂度 总共\(O(n)\) ,需要辅助空间 \(O(1)\)
稳定性 稳定

算法助记

1
2
3
i∈[0,N-1)               //循环N-1遍
j∈[0,N-1-i) //每遍循环要处理的无序部分
swap(j,j+1) //两两排序(升序/降序)

C++实现

1
2
3
4
5
6
7
8
9
10
void bubble_sort(int *arr, int n){
int i, j;
for (i=0; i<n-1; i++){
for (j=0; j<n-i-1; j++){
if (*(arr+j) > *(arr+j+1)){
swap(arr, j, j+1);
}
}
}
}

插入排序

通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

item description
平均时间复杂度 \(O(n^{2})\)
最优时间复杂度 \(O(n)\)
最差时间复杂度 \(O(n^{2})\)
空间复杂度 总共\(O(n)\) ,需要辅助空间 \(O(1)\)
稳定性 稳定
1
2
3
4
5
6
7
8
9
10
11
12
void insert_sort(int *arr, int n){
int i, j, k;
for (i=1; i<n; i++){
j = i-1;
k = *(arr+i);
while (j>=0 && k < *(arr+j)){
*(arr+j+1) = *(arr+j);
j--;
}
*(arr+j+1) = k;
}
}

选择排序

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾,以此类推,直到所有元素均排序完毕。

item description
平均时间复杂度 \(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
void select_sort(int *arr, int n){
int i, j, min_idx;
for (i=0; i<n; i++){
min_idx = i;
for (j=i+1; j<n; j++){
if (*(arr+j) < *(arr+min_idx)){
min_idx = j;
}
}
if (min_idx != i)
// swap
swap(arr, i, min_idx);
}
}

希尔排序

递减增量排序算法,是插入排序的一种更高效的改进版本。

item description
平均时间复杂度 根据步长序列的不同而不同
最优时间复杂度 \(O(n)\)
最差时间复杂度 根据步长序列的不同而不同
空间复杂度 \(O(n)\)
稳定性 不稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void shell_sort(int *arr, int n){
int d, i, j, k;
d = n/2;
while (d>0){
for (i=d; i<n; i++){
k = *(arr+i);
j = i-d;
while (j>=0 && *(arr+j) > k){
*(arr+j+d) = *(arr+j);
j -= d;
}
*(arr+j+d) = k;
}
d /= 2;
}
}

快速排序

快排是一种很重要的排序,故单独叙述,请查看文章快速排序

item description
平均时间复杂度 \(O(nlogn)\)
最优时间复杂度 \(O(nlogn)\)
最差时间复杂度 \(O(n^{2})\), 退化为冒泡排序
空间复杂度 \(O(logn)\)
稳定性 不稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int partition(int *arr, int low, int high){
// 选择随机数作为哨兵
int randint = rand()%high + low;
swap(arr, randint, high);

int store_idx=low, i, j, privot= *(arr+high);
for (i=low; i<high; i++){
if (*(arr+i) < privot){
swap(arr, i, store_idx);
store_idx++;
}
}
swap(arr, store_idx, high);
return store_idx;
}
int quick_sort(int *arr, int low, int high){
if (low < high){
int mid = partition(arr, low, high);
quick_sort(arr, low, mid-1);
quick_sort(arr, mid+1, high);
}
}

堆排序

利用堆所设计的排序算法,堆是一个近似完全二叉数的结构,并同时满足堆的性质:子结点的键值或索引总是小于(或大于)它的父节点

item description
平均时间复杂度 \(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
// 构建大顶堆
void build_maxheap(int *arr, int root, int n){
int L, R, largest;
L = 2*root+1;
R = 2*root+2;
largest = root;
if (L < n && *(arr+L) > *(arr+largest)){
largest = L;
}
if (R < n && *(arr+R) > *(arr+largest)){
largest = R;
}

if (largest != root){
swap(arr, largest, root);
build_maxheap(arr, largest, n);
}
}
void heap_sort(int *arr, int n){
int i;
for (i=n/2; i>=0; i--){
// 构建初始大顶堆
build_maxheap(arr, i, n);
}
for (i=n-1; i>=0; i--){
swap(arr, 0, i);
build_maxheap(arr, 0, i);
}
}

归并排序

是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。且是一种稳定的排序算法,归并排序即是内排序也可作为外排序

item description
平均时间复杂度 \(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
void merge(int *arr, int low, int mid, int high){
int n1, n2, i, j, k;
n1 = mid - low + 1;
n2 = high - mid;
int *L = new int[n1];
int *R = new int[n2];
for (i=0; i<n1; i++){
*(L+i) = *(arr+low+i);
}
for (j=0; j<n2; j++){
*(R+j) = *(arr+mid+j+1);
}
k = low;
i = 0;
j = 0;
while (i<n1 && j<n2){
if (*(L+i) < *(R+j)){
*(arr+k) = *(L+i);
i++;
}else{
*(arr+k) = *(R+j);
j++;
}
k++;
}
while (i<n1){
*(arr+k) = *(L+i);
i++;
k++;
}
while (j<n2){
*(arr+k) = *(R+j);
j++;
k++;
}
}

void merge_sort(int *arr, int low, int high){
if (low < high){
int mid = (low+high) / 2;
merge_sort(arr, low, mid);
merge_sort(arr, mid+1, high);
merge(arr, low, mid, high);
}
}

本文所有代码均放在GitHub上

sean lee wechat
欢迎关注我的公众号!
感谢支持!