数据结构之八大排序

数据结构中的排序算法是面试中经常问到的,包括算法的实现逻辑,时间复杂度和是否稳定等。下面是用c++实现数据结构中常见的八大排序。

冒泡排序

最坏的时间复杂度为 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
#include <iostream>
using namespace std;

void print(int *a,int n){
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}

int main()
{
int a[100];
int n;
int tem;

cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}

// 冒泡排序
for(int i=1;i<=n-1;i++){
int flg=false;
for(int j=1;j<=n-i;j++){
if(a[j]<a[j-1]){
tem = a[j-1];
a[j-1]=a[j];
a[j]=tem;
flg=true;
}
}
if(!flg){
break;
}
}
print(a,n);
return 0;
}

/*
5
5 1 3 2 4
*/

插入排序

插入排序是最简单的排序方法,他的基本操作是将一个记录插入到已排序好的前子序列中。有n个数的数列,总共要进行n-1次插入排序。

例如原数列为[5,1,3,2,4]总共进行4次排序分别为:[1,5,3,2,4], [1,3,5,2,4], [1,2,3,5,4],[1,2,3,4,5].

复杂度为 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
#include <iostream>
using namespace std;

//...

int main()
{
// ...

/* 直接插入排序 */
for(int i=1;i<=n-1;i++){
int j=i-1;
int val = a[i];
while(a[j]>val && j>=0){
a[j+1] = a[j];
j--;
}
a[j+1] = val;
}

print(a,n);
return 0;
}

希尔排序

希尔排序 (shell sort) 先将整个带排序记录序列分割成若干个子序列分别进行直接插入排序,待整个序列的记录‘基本有序’时,再对全体记录进行一次直接的插入排序。

时间复杂度:O(n^1.5), 属于插入排序的一种,是稳定的排序。

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
/***** shell-sort 希尔排序 稳定的排序 O(n^1.5)******/

#include <iostream>
using namespace std;

//...

void shell_sort(int *a,int n){
for(int step = n/2;step>=1;step/=2){
for(int i=step;i<n;i++){
if(a[i]<a[i-step]){
int val = a[i];
a[i] = a[i-step];
int j = i-step-step;
while(j>=0 && a[j]>val){
a[j+step] = a[j];
j-=step;
}
a[j+step] = val;
}
}
}
}

int main()
{
//...
shell_sort(a,n);
print(a,n);
return 0;
}

快速排序

快速排序 (qiuck sort) 是对冒泡排序的一种改进,通过一趟排序把记录分隔成两部分,其中一部分的关键字比另一部分都下,然后递归对这两部分进行快速排序。

时间复杂度:最坏 O(n^2),平均 O(nlogn),属于不稳定的排序。

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
#include <iostream>
using namespace std;

//..
void qsort(int *a,int l,int r){
if(l < r){
int key_value = a[l];
int left = l;
int right = r;
while(l<r){
while(l<r && a[r]>=key_value) r--;
a[l]=a[r];
while(l<r && a[l]<=key_value) l++;
a[r]=a[l];
}
a[l] = key_value;
qsort(a,left,l-1);
qsort(a,l+1,right);
}
}

void quick_sort(int *a,int n){
qsort(a,0,n-1);
}

int main()
{
// ...
quick_sort(a,n);
print(a,n);
return 0;
}

选择排序

选择排序在每一次在n-i+1(i=1,2,,,n-1)个记录中选取关键字最小的记录作为有序序列第i个记录。

复杂度为 O(^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
#include <iostream>
using namespace std;

// ...
void select_sort(int *a,int n){
for(int i=0;i<n-1;i++){
int min_value = a[i];
int index = i;
for(int j=i+1;j<n;j++){
if(a[j] < min_value){
index = j;
min_value = a[j];
}
}
if(index != i){
int tem = a[index];
a[index] = a[i];
a[i] = tem;
}
}
}

int main()
{
// ...
select_sort(a,n);
print(a,n);
return 0;
}

堆排序

堆排序(heap-sort):把关键字序列看成一颗二叉树,树上的非叶子节点的值均小于(或者大于)其左右子节点的值,所以树根肯定是这个序列的最小值或者最大值。堆排序的核心是树节点的调整,以维护一个最小堆树(或者最大堆),建堆树也是通过堆调整建立的。

时间复杂度为:O(nlong) ,不稳定的排序

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
#include <iostream>
using namespace std;

//...

void heap_ajust(int *a,int s,int len){
int key_value = a[s];
for(int j = 2*s;j<=len;j*=2){
if(j<len && a[j+1]>a[j])
j++;
if(key_value > a[j])
break;
a[s] = a[j];
s=j;
}
a[s] = key_value;
}

void heap_sort(int *a,int n){
// build heap
for(int i=n/2;i>=1;i--){
heap_ajust(a,i,n);
}
// sort
for(int i=n;i>0;i--){
swap(a[i],a[1]);
heap_ajust(a,1,i-1);
}
}

int main()
{
// ...
heap_sort(a,n);
print(a,n);
return 0;
}

归并排序

归并排序 (merge-sort) 将两个或两个以上的有序列表组合成一个新的有序表,合并的m,n长度的两个表的复杂度为 O(m+n),n个数的序列进行归并共有ceil(logn)次,每一次合并都是n常数级别的,所以总的复杂度为 O(nlogn)。同时归并排序是一种稳定的排序。

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
#include <iostream>
using namespace std;

// ...

void Merge(int*sr,int*& tr,int i,int m,int n){
// 将有序表sr[i...m],sr[m+1...n]合并成tr[i...n]
int k,j;
for(j=m+1,k=i;j<=n&&i<=m;k++){
if(sr[i]<sr[j]){
tr[k]=sr[i++];
}else{
tr[k]=sr[j++];
}
}
while(i<=m){
tr[k++]=sr[i++];
}
while(j<=n){
tr[k++]=sr[j++];
}
}

void Msort(int* sr,int*& tr,int s,int t){
// 将表sr[s....t]归并成有序表tr[s....t]
if(s==t)
tr[s]=sr[s];
else{
int m = (s+t)/2;
int *mr = new int[t+1];
Msort(sr,mr,s,m);
Msort(sr,mr,m+1,t);
Merge(mr,tr,s,m,t);
}
}

void Merge_sort(int *a,int n){
Msort(a,a,1,n);
}

int main()
{
// ...
Merge_sort(a,n);
print(a,n);
return 0;
}