Bubblesort
时间复杂度：
平均：O(n^2)
最好：O(n)
最坏：O(n^2)
空间复杂度：
O(1)
1
2
3
4
5
6
7
8
9
10
11
| void Bubblesort(int a[],int n){
for(int i=n;i>=1;i++){
for(int j=0;j<i;j++){
if(a[j]>a[j-1]){
int t=a[j];
a[j]=a[j-1];
a[j-1]=t;
}
}
}
}
|
Selectionsort
时间复杂度：
平均：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
| void Selectionsort(int a[],int n){
for(int i=0;i<n;i++){
int pos=i;
int max=a[i];
for(int j=i+1;j<n;j++){
if(a[j]>max){
max=a[j];
pos=i;
}
}
if(pos!=i){
int temp=a[pos];
a[pos]=a[i];
a[i]=temp;
}
}
}
|
Insertsort
时间复杂度：
平均：O(n^2)
最好：O(n)
最坏：O(n^2)
空间复杂度：
O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
| void Insertsort(int a[],int n){
for(int i=1;i<n;i++){
int key=a[i];
int j;
for(j=i;j>=1;j--){
if(a[j-1]<key){
a[j]=a[j-1];
}
else break;
}
a[j]=key;
}
}
|
Quicksort
非常重要
时间复杂度：
平均：O(nlongn)
最好：O(nlogn)
最坏：O(n^2)
空间复杂度：
O(logn)-O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void quick_mid(int a[],int left,int right){
int pivot=a[left];
while(left<right){
while(left<right&&a[left]<pivot)left++;
a[right]=a[left];
while(right>left&&a[right]>=pivot)right--;
a[left]=a[right];
}
a[left]=pivot;
return left;
}
void quick_sort(int a[],int left,int right){
if(l<r){
int mid=quick_mid(a[],l,r);
quick_sort(a[],l,mid-1);
quick_sort(a[],mid+1,r);
}
}
|
Shellsort
时间复杂度：
平均：O(n^1.3)
最好：O(n)
最坏：O(n^2)
空间复杂度：
O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void Shellsort(int a[],.int n){
int i,j,dis;
for(dis=n/2;dis>=1;dis/=2){
for(i=dis;i<n;i++){
int key=a[i];
for(j=i;j<=dis;j+=dis){
if(a[j-dis]<key){
a[j]=a[j-dis];
}
else break;
}
a[j]=key;
}
}
}
|
3ways_Quicksort
序列如图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void 3ways_quicksort(int a[],int l,int r){
int i,j,lr,gt;
lr=l;
gt=r+1;
int pivot=a[l];
for(i=l;i<gt;){
if(a[i]>pivot){
swap(a[i],a[lt+1]);
lt++;
i++;
}
if(a[j]<pivot){
swap(a[gt],a[i]);
gt--;
}
else i++;
}
swap(a[l],a[lt]);
3ways_Quicksort(a,l,lt);
3ways_Quicksort(a,gt,r);
}
|
Heapsort
时间复杂度：
平均：O(nlogn)
最好：O(nlogn)
最坏：O(nlogn)
空间复杂度：
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
| void Build_heap(int tree[],int n){
int last_node=n-1;
int node=(last_node-1)/2;
for(int i=node;i>=0;i--){
heapify(tree,n,i);
}
}
void Heapify(int tree[],int n,int node){
if(node>=n) return ;
int c1=node*2+1;
int c2=node*2+2;
int max=node;
if(c1<n&&tree[c1]>tree[max]){
max=c1;
}
if(c2<n&&tree[c2]>tree[max]){
max=c2;
}
if(max!=node){
swap(tree[node],tree[max]);
heapify(tree,n,max);
}
}
void Heapsort(int tree[],int n){
Build_tree(tree,n);
int i;
for(i=n-1;i>=0;i--){
swap(tree[0],tree[i]);
heapify(tree,i,0);
}
}
|
MergeSort
时间复杂度：
平均：O(nlogn)
最好：O(nlogn)
最坏：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
| void merge(int a[],int l,int m,int r){
int l_size=m-l+1;
int r_size=r-mid;
int lnum[l_size];
int rnum[r_size];
int i,j,k;
i=0;
j=0;
k=0;
while(i<l_size)lnum[i++]=a[k++];
while(j<r_size)rnum[j++]=a[k++];
i=0;
j=0;
k=0;
while(i<l_size&&j<r_size){
if(lnum[i]>rnum[j])
a[k++]=rnum[j++];
else if(lnum[i]<rnum[i]>)
a[k++]=lnum[i++];
else{
a[k++]=rnum[i++];
a[k++]=rnum[j++];
}
}
while(i<l_size)
a[k++]=lnum[i++];
while(j<r_size)
a[k++]=rnum[j++];
}
void MergeSort(int a[],int l,int r){
if(l<r){
int mid=(l+r)/2;
mergesort(a,l,mid);
mergesort(a,mid+1,r);
merge(a,l,mid,r);
}
else return;
}
|
