数据结构算法

数据结构算法总结

[TOC]

顺序表

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
#include<iostream>
using namespace std;
# define maxSize 100
template <class DataType>
class SeqList{
private:
DataType data[maxSize];
int length;
public:
SeqList(DataType a[],int n){
if(n>maxSize)throw "exception";
for(int i=0;i<n;i++){
data[i]=a[i];
}
length=n;
}
bool Insert(int i,DataType x){
if(i<1||i>length+1)return false;
if(length>=maxSize)return false;
for(int j=length;j>=i;j--)
data[j]=data[j-1];
data[i-1]=x;
length++;
return true;
}
DataType Delete(int i){//删除i位置上的元素
if(i<1||i>length+1)return false;
DataType x=data[i-1];
for(int j=i;j<length;j++) data[j-1]=data[j];
length--;
return true;
}
int Local(DataType x){//查找X
for(int i=0;i<length;i++){
if(data[i]==x)return i+1;
}
return 0;
}
DataType Get(int i){
if(i<1||i>length)throw "exception";
else return data[i-1];
}
};
int main(){

}

单链表

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
94
95
96
97
98
99
100
101
#include<iostream>
using namespace std;
# define maxSize 100
template <class DT>
struct Node{
DT data;
Node<DT> *next;
};
template <class DT>
class LinkList{
private:
Node<DT> *first;
public:
LinkList(){
first=new Node<DT>;
first->next=NULL;
}
LinkList_Head(DT a[],int n){
first=new Node<DT>;
first->next=NULL;
for(int i=0;i<n;i++){
Node<DT> *s=new Node<DT>;
s->data=a[i];
s->next=first->next;
first->next=s;
}
}
LinkList_Tail(DT a[],int n){
first=new Node<DT>;
Node<DT> *r=first;
Node<DT> *s=new Node<DT>;
for(int i=0;i<n;i++){
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
int Length(){
Node<DT> *p=first->next;
int count=0;
while(p!=NULL){
p=p->next;
count++;
}
return count;
}
DT Get(int i){
Node<DT> *p=first->next;
int count=1;
while(p!=NULL&&count<i){
p=p->next;
count++;
}
return p->data;
}
int Locate(DT x){
Node<DT> *p=first->next;
int count=1;
while(p!=NULL){
if(p->data==x)return count;
p=p->next;
count++;
}
return 0;
}
void Insert(int i,DT x){
Node<DT> *p=first;
int count=0;
while(p!=NULL&&count<i-1){
p=p->next;
count++;
}
Node<DT> *s=new Node<DT>;
s->data=x;
s->next=p->next;
p->next=s;

}
DT Delete(int i){
Node<DT> *p=first;
count=0;
while(p!=NULL&&count<i-1){
p=p->next;
count++;
}
if(p==NULL||p->next==NULL){
throw "位置";
}else{
Node<DT> *q=p->next;
DT x=q->data;
p->next=q->next;
delete q;
return x;
}
}

};
int main(){
cout<<1<<endl;
}

顺序栈

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
#include<iostream>
using namespace std;
# define StackSize 100
template <class DT>
class SeqStack{
private:
DT data[StackSize];
int top;
public:
SeqStack(){top=-1;}
void Push(DT x){
if(top==StackSize-1)throw "溢出";
data[++top]=x;
}
DT Pop(){
if(top==-1)throw "溢出";
DT x=data[top--];
return x;
}
DT GetTop(){
if(top!=-1)
return data[top];
}
};

int main(){

}

链栈

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
#include<iostream>
using namespace std;
# define maxSize 100
template <class DT>
struct Node{
DT data;
Node<DT> *next;
};
template <class DT>
class LinkStack{
private:
Node<DT> *top;
public:
LinkStack(){top=NULL;}
void Push(DT x){
Node<DT> *s=new Node<DT>;
s->data=x;
s->next=top;
top=s;
}
DT Pop(){
if(top==NULL)throw "下溢";
DT x=top->data;
Node<DT> *p=top;
top=top->next;
delete p;
return x;
}
DT GetTop(){
if(top!=NULL) return top->data;
}
};
int main(){

}

顺序共享栈

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;
# define StackSize 100
template <class DT>
class BothStack{
private:
DT data[StackSize];
int top1;
int top2;
public:
SeqStack(){top=-1;}
void Push(int i,DT x){
if(top1==top2-1)throw "溢出";
if(i==1)data[++top1]=x;
if(i==2)data[--top2]=x;
}
DT Pop(int i){
if(i==1){
if(top1==-1)throw "下溢";
return data[top1--];
}
if(i==2){
if(top2==StackSize)throw "下溢";
return data[top2++];
}
}

};

int main(){

}

循环队列

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
#include <iostream>
using namespace std;
const int QueueSize=100;
template <class DT>
class CirQueue{
private:
DT data[QueueSize];
int front,rear;
public:
CirQueue(){
front=rear=QueueSize-1;
}
void EnQueue(DT x){
if((rear+1)%QueueSize==front)throw "上溢";
rear=(rear+1)%QueueSize;
data[rear]=x;
}
DT DeQueue(){
if(rear=front)throw "下溢";
front=(front+1)%QueueSize;
return data[front];
}
DT GetQueue(){
if(rear=front)throw "下溢";
int i=(front+1)%QueueSize;
return data[i];
}
int Empty(){
front==rear?return 1:retuen 0;
}
};

int main(){

}

链队列

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
#include <iostream>
using namespace std;
template <class DT>
struct Node{
DT data;
Node *next;
};
template <class DT>
class LinkQueue{
private:
Node<DT> *front,*rear;
public:
LinkQueue(){
Node<DT> *s=new Node<DT>;
s->next=NULL;
front=rear=s;
}
void EnQueue(DT x){
Node<DT> *s=new Node<DT>;
s->data=x;
s->next=NULL;
rear->next=s;
rear=s;
}
DT DeQueue(){
if(rear==front) throw "下溢";
Node<DT> *p=front->next;
DT x=p->data;
front->next=p->next;
if(p->next==NULL)rear=front;
delete p;
return x;
}
int Empty(){
if(front==rear)return 1;
return 0;
}
};
int main(){

}

KMP

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
#include<iostream>
#include<String>
using namespace std;
void getnext(string T,int next[]){//T[0],next[0] 不用
int i=1,j=0;
next[1]=0;
while(i<=T[0]){
if(j==0||T[i]==T[j]){
i++;
j++;
next[i]=j;
}else{
j=next[j];
}
}
}
int KMP(string S,string T,int next[]){//s为主串,T为模式串,每个数组的0位置不用,用来存数组大小
int i=1,j=1;
while(i<=S[0]&&j<=T[0]){
if(j==0||S[i]==T[j]){
i++;
j++;
}else{
j=next[j];
}
}
if(j>T[0])return i-T[0];
else return 0;

}
int main(){
char cnt;

string S="abcabaaabaabcac";
cnt=15;
S=cnt+S;

string T="abaabcac";// char T[10]={8,'a','b','a','a','b','c','a','c'};
cnt=8;
T=cnt+T;

int next[9];next[0]=-1;
getnext(T,next);
cout<<KMP(S,T,next);
}

二叉排序树

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
#include <iostream>
using namespace std;
struct Node{
int data;
Node *lchild;
Node *rchild;
};
void InsertBST(Node *root,Node *s){
if(root==NULL)root=s;
else if(s->data<root->data)InsertBST(root->lchild,s);
else InsertBST(root->rchild,s);
}
Node *BiSortTree(int a[],int n){
Node *root=NULL;
for(int i=0;i<n;i++){
Node *s=new Node;
s->data=a[i];
s->lchild=s->rchild=NULL;//构造好要插入的节点,执行插入操作
InsertBST(root,s);
}
}
//此删除假设的是删除节点是父节点的左孩子情况
void DeleteBST(Node *p,Node *f){//待删结点p,双亲结点f
if(p->lchild==NULL&&p->rchild==NULL){
f->lchild=NULL;
delete p;
}else if(p->rchild==NULL){//p只有左子树
f->lchild==p->rchild;
delete p;
}else if(p->lchild==NULL){//p只有右子树
f->lchild=p->rchild;
delete p;
}else{
Node *par=p;
Node *s=p->lchild;
while(s->lchild!=NULL){
par=s;
s=s->lchild;
}
p->data=s->data;
if(par==p)par->rchild=s->rchild;
else par->lchild=s->rchild;
delete s;
}
}
int main(){

}

图邻接矩阵广搜深搜

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 <queue>
using namespace std;
const int MaxSize=10;
int visited[MaxSize]={0};
template <class DT>
class MGraph{
private:
DT vertex[MaxSize];//存放顶点
int arc[MaxSize][MaxSize];//存放边
int vertexNum,arcNum;
public:
MGraph(DT a[],int n,int e){//n个顶点,e条边
vertexNum=n;arcNum=e;
for(int i=0;i<vertexNum;i++)vertex[i]=a[i];
for(int i=0;i<vertexNum;i++)
for(int j=0;j<vertexNum;j++)
arc[i][j]=0;
for(int k=0;k<arcNum;k++){int i,j;
cin>>i>>j;
arc[i][j]=arc[j][i]=1;
}
}
void DFSTraverse(int v){//初始遍历结点
cout<<vertex[v];
visited[v]=1;
for(int i=0;i<vertexNum;i++)
if(arc[v][i]==1&&visited[i]==0)
DFSTraverse(i);
}
void BFSTraverse(int v){
queue<int> q;
int front,rear;front=rear=-1;
cout<<vertex[v];visited[v]=1;

q.push(v);
while(q.empty()!=true){
v=q.pop();
for(int i=0;i<vertexNum;i++){
if(arc[v][i]==1&&visited[i]==0)
cout<<vertex[i];
visited[i]=1;
q.push(i);
}
}
}
};
int main(){

}

图邻接表广搜深搜

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
#include <iostream>
#include <queue>
using namespace std;
const int MaxSize=10;
int visited[MaxSize]={0};
struct Node{//邻接点
int data;
Node *next;
};
template <class DT>
struct VertexNode{//顶点表结点
DT vertex;
Node *firstedge;
};
template<class DT>
class ALGraph{
private:
VertexNode<DT> adjlist[MaxSize];
int vertexNum,arcNum;
public:e
ALGraph(DT a[],int n,int e){//n顶点,e条边
vertexNum=n;arcNum=e;
for(int i=0;i<vertexNum;i++){
adjlist[i].vertex=a[i];
adjlist[i].firstedge=NULL;
}
for(int k=0;k<arcNum;k++){
int i,j;
cin>>i>>j;
Node *s=new Node;
s->data=j;
s->next=adjlist[i].firstedge;//头插
adjlist[i].fistedge=s;
}
}
void DFSTraverse(int v){
cout<<adjlist[v].vertex;visited[v]=1;
Node *p=adjlist[v].firstedge;
while(p!=NULL){
int i=p->data;
if(visited[i]==0)DFSTraverse(i);
p=p->next;
}
}
void BFSTraverse(int v){
queue<int> Q;
cout<<adjlist[v].vertex;
visited[v]=1;

Q.push(v);
while(Q.empty()!=true){
v=Q.pop();
Node *p=adjlist[v].firstedge;
while(p!=NULL){
int i=p->data;
if(visited[i]==0){
cout<<adjlist[i].vertex;
visited[i]=1;
Q.push(i);
}
p=p->next;
}
}
}
};
int main(){

}

排序

插入排序

优点:实现简单,数据量少时效率高

如果输入序列已经预排序,时间复杂度为O(n+d),d是反转的次数。

算法运行效率优于选择排序冒泡排序即使是最坏的情况三个算法时间复杂度均为O($n^2 $)

能在接收序列的同时进行排序

1
2
3
4
5
6
7
8
9
void InsertSort(int r[],int n){
for(int i=2;i<n;i++){
r[0]=r[i];//r[0]用于暂存要移动的元素
for(int j=i-1;r[0]<r[j];j--){//往前找插入位置
r[j+1]=r[j];//元素后移
}
r[j+1]=r[0];//插入
}
}

冒泡排序

按照改进的算法,对于一个已经有序的数组,算法完成第一次外层循环后就会返回。
实际上只发生了 N - 1次比较,所以最好的情况下,该算法复杂度是O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void BubbleSort(){
int [] array={1,5,3,2,6,7,9,13,54,20};
for(int i=0;i<array.length-1;i++){
//每一轮比较的次数为N-1-i;
for(int j=0;j<array.length-1-i;j++){
//比较相邻的两个数,小靠前
if(array[j]>array[j+1]){
//两个数做交换.通过设置临时变量
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void BubbleSortImproved(){
int [] array={1,5,3,2,6,7,9,13,54,20};
boolean swapped=true;
for(int i=0;i<array.length-1&&swapped;i++){
swapped=false;
//每一轮比较的次数为N-1-i;
for(int j=0;j<array.length-1-i;j++){
//比较相邻的两个数,小靠前
if(array[j]>array[j+1]){
//两个数做交换.通过设置临时变量
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
swapped=true;
}
}
}
}

选择排序

优点:容易实现,原地排序不需要额外的存储空间

缺点:扩展性差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void SelectSort(){
int [] array={1,5,3,2,6,7,9,13,54,20};
int min=0;//保存最元素值的下标
for(int i=0;i<array.length-1;i++){
min=i;
//查找最小数在数组中的下标
for(int j=i+1;j<array.length;j++){
if(array[min]>array[j]){
min=j;//保存最小数的下标
}
}
//如果第i个最小的数位置不在i上,则进行交换
if(i!=min){
int temp=array[i];
array[i]=array[min];
array[min]=temp;
}
}
}

希尔排序

希尔排序是基于直接插入排序的,直接插入排序在元素较少和元素基本有序时效率是不错的,但随着元素增多和有序性破坏,效率会下降的很明显。希尔排序通过分组实现跳跃式移动,保证待排序序列基本有序后再排序,就能提高效率。

1
2
3
4
5
6
7
8
9
10
11
void ShellSort(int r[],int n){
for(int d=n/2;d>1;d=d/2){
for(int i=d+1;i<n;i++){
r[0]=r[i];//把元素存起来
for(int j=i-d;j>0&&r[0]<r[j];j=j-d){//往前以步长d查找元素
r[j+d]=r[j];//元素后移
}
r[j+d]=r[0];//插入
}
}
}

快速排序

快速排序的思想是分割,是分治算法技术的一个实例。确保一个元素左边的元素都小于这个元素,右边的元素都大于这个元素,然后对这两部分分别继续进行分割,从而达到排序的效果。

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
void Quicksort(int[] a,int low,int high){
int temp;
if(low<high){
temp = partition(a,low,high);
Quicksort(a,low,temp-1);
Quicksort(a,temp+1,high);
}
}

int partition(int[] a,int low,int high){
int i=low;
int j=high;
while(i<j){
while(i<j&&a[i]<=r[j]) j--;//右侧扫描
if(i<j){swap(a,i,j);i++;}//小记录置前
while(i<j&&a[i]<=r[j]) i++;//左侧扫描
if(i<j){swap(a,i,j);j--}//大记录置后
}
return low;
}
void swap(int[] a,int low,int high){
if(low<high){
int temp=a[low];
a[low]=a[high];
a[high]=a[low];
}
}

堆排序

基于比较的排序,属于选择排序,优点是最坏的情况下O($ n \log n $)

基本思想:首先将待排序的记录序列构造成一个堆,此时,选出了堆中所有记录的最大者,然后将它从堆中移走,并将剩余的记录再调整成堆,这样又找出了次小的记录,以此类推,直到堆中只有一个记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 void HeapSort(int[] a,int n){
for(int i=n/2; i>=1; i--){
heapAdjust(a,i,n);//从最后一个有子节点的节点开始依次往前调整对应节点来生成大顶堆
}
for(int i=1; i<n; i++){
swap(a,1,n-i-1);//交换堆顶元素与未排序堆最后一个元素
heapAdjust(a,1,n-i);//根据调整节点重新生成大顶堆
}
}
void heapAdjust(int r[], int k, int m ){
//要筛选结点的编号为k,堆中最后一个结点的编号为m
int i=k;
int j=2*i;//到达下一层的左孩子
while (j<=m){ //筛选还没有进行到叶子
if (j<m && r[j]<r[j+1]) j++; //左右孩子中取较大者
if (r[i]>r[j]) break;
else {
swap(r,i,j);
i=j;
j=2*i;
}
}
}

归并排序

归并排序的主要操作是归并,其主要思想是:将若干有序序列逐步归并,最终得到一个有序序列。

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
int[] sort(int[] o,int m,int n){
int mid;
int[] result = new int[o.length];
if(o.length == 1|| m==n){
result[0] = o[0];
}else{
mid = (m+n)/2;
int[] temp1 = new int[mid-m+1];
int[] temp2 = new int[o.length-mid+m-1];
System.arraycopy(o,0,temp1,0,mid-m+1);
System.arraycopy(o,mid-m+1,temp2,0,o.length-mid+m-1);
int[] result1 = sort(temp1,m,mid);
int[] result2 = sort(temp2,mid+1,n);
result = Merge(result1,result2);
}
return result;
}
int[] Merge(int[] i,int[] j){
int m=0,n=0,k=0;
int[] result = new int[i.length+j.length];
for(; m<i.length&&n<j.length; k++){
if(i[m]<j[n]){
result[k] = i[m++];
}else{
result[k] = j[n++];
}
}
if(m<i.length){
while(m<i.length){
result[k++] = i[m++];
}
}
if(n<j.length){
while(n<j.length){
result[k++] = j[n++];
}
}
return result;
}

线性排序-计数排序

计数排序的基本思想是对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数(此处并非比较各元素的大小,而是通过对元素值的计数和计数值的累加来确定)。一旦有了这个信息,就可以将x直接存放到最终的输出序列的正确位置上。例如,如果输入序列中只有17个元素的值小于x的值,则x可以直接存放在输出序列的第18个位置上。

牺牲空间换取时间,当K=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
int[] CountSort(int[]a){
int b[] = new int[a.length];
int max = a[0],min = a[0];
for(int i:a){
if(i>max){
max=i;
}
if(i<min){
min=i;
}
}
int k=max-min+1;//这里k的大小是要排序的数组中,元素大小的极值差+1
int c[]=new int[k];
for(int i=0;i<a.length;++i){//O(n)
c[a[i]-min]+=1;//优化过的地方,减小了数组c的大小
}
for(int i=1;i<c.length;++i){//O(k)
c[i]=c[i]+c[i-1];
}
for(int i=a.length-1;i>=0;--i){//O(n)
b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
}
return b;
}

线性排序-桶排序

与计数排序类似,桶排序也对输入加以限制来提高算法性能。换言之。如果输入的序列来自固定集合,则桶排序的效率较高。例如假设所有输入元素是在【0,k-1】上的整数集合,这就表示k是输入序列中最远距离元素的数目。桶排序采用K个计数器,第i个计数器记录第i个的元素出现次数。

1
2
3
4
5
6
7
8
9
10
11
static int BUCKET=10;
void BucketSort(int A[],int array_size){
int[] bucket=new int[BUCKET];
for(int i=0;i<BUCKET;i++)bucket[i]=0;
for(int i=0;i<array_size;i++)++bucket[A[i]];
for(int i=0,j=0;j<BUCKET;j++){
for(int k=bucket[j];k>0;--k){
A[i++]=j;
}
}
}

线性排序-基数排序

1)取每个元素最低有效位

2)基于最低有效位对序列中的元素进行排序,并保持具有相同位的元素的原有次序(稳定排序)

3)对下一个最低有效位重复该过程

基数排序速度取决于内部基本操作。如果输入值具有的位数长度不等。还需要对附加位进行排序,这是基数排序最慢的部分之一,也是最难进行效率优化的部分之一。

算法灵活性不如其他排序算法,对于每一种不同类型数据,基数排序都需要重写,难以编写一个处理所有数据的通用基数排序算法。

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 RadixSort(int[] number, int d){ //d表示最大的数有多少位
int k = 0;
int n = 1;
int m = 1; //控制键值排序依据在哪一位
int[][]temp = new int[10][number.length]; //数组的第一维表示可能的余数0-9
int[]order = new int[10]; //数组orderp[i]用来表示该位是i的数的个数
while(m <= d) {
for(int i = 0; i < number.length; i++) {
int lsd = ((number[i] / n) % 10);
temp[lsd][order[lsd]] = number[i];
order[lsd]++;
}
for(int i = 0; i < 10; i++) {
if(order[i] != 0)
for(int j = 0; j < order[i]; j++) {
number[k] = temp[i][j];
k++;
}
order[i] = 0;
}
n *= 10;
k = 0;
m++;
}
}

性能比较

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
插入排序 O($ n^2 $) O(n) O($n^2$) O(1) 稳定
冒泡排序 O($ n^2 $) O(n) O($n^2$) O(1) 稳定
选择排序 O($ n^2 $) O($ n^2 $) O($n^2$) O(1) 不稳定
希尔排序 O($ n \log n $)~O($n^2$) O($ n^{1.3} $) O($ n^2 $) O(1) 不稳定
快速排序 O($ n\log n $) O($ n\log n $) O($ n^2 $) O($\log n$)~O($n$) 不稳定
堆排序 O($ n\log n $) O($ n\log n $) O($ n\log n $) O(1) 不稳定
归并排序 O($ n\log n $) O($ n\log n $) O($ n\log n $) O(n) 稳定
线性排序-计数排序 O(n+k) O(n+k) O(n+k) O(1) 稳定
线性排序-桶排序 O(n+k) O(n+k) O($ n^2 $) O(n+k) 稳定
线性排序-基数排序 O(n*k) O(n*k) O(n*k) O(n+k) 稳定

性能比较

注:Java 实现的排序源代码

鸣谢

感谢费劲心思整理此博客的杨学长

杨学长博客:COKID