本人介绍的排序算法主要有:插入排序,选择排序,冒泡排序,快速排序,堆排序,归并排序,希尔排序,二叉树排序,桶排序,基数排序(后两者为非比较排序,前面的为比较排序)。
排序的稳定性和复杂度:
不稳定:
选择排序(selection sort)— O(n2)
快速排序(quicksort)— O(nlogn) 平均时间, O(n2) 最坏情况; 对于大的、乱序串列一般认为是最快的已知排序
堆排序 (heapsort)— O(nlogn)
希尔排序 (shell sort)— O(nlogn)
基数排序(radix sort)— O(n·k); 需要 O(n) 额外存储空间 (K为特征个数)
稳定:
插入排序(insertion sort)— O(n2)
冒泡排序(bubble sort) — O(n2)
归并排序 (merge sort)— O(nlogn); 需要 O(n) 额外存储空间
二叉树排序(Binary tree sort) — O(nlogn); 需要 O(n) 额外存储空间
桶排序 (bucket sort)— O(n); 需要 O(k) 额外存储空间
1、插入排序
对于一个序列{a[0]……a[n]},当记录值是第i个元素时,前面i-1个元素已经排好序了,那么这个记录值从第i-1个元素一直往前比较,找到属于它的位置后插进去。
1 #include <iostream>
2 using namespace std;
3
4 int main()
5 {
6 int a[]={1,99,2,88,3,77,4,66};
7 int n=sizeof(a)/4;
8 for(int i=0; i<n; i++)
9 {
10 int tp=a[i], j;
11 for(j=i-1; j>=0&&a[j]>tp; j--) a[j+1]=a[j];
12 a[j+1]=tp;
13 }
14 cout << a[0] ;
15 for(int i=1; i<n; i++) cout << " " << a[i];
16 cout <<endl;
17 return 0;
18 }
View Code
2、选择排序
对于一个序列{a[0]……a[n]},前面i-1个元素都是已经排好序的,那么从第i到第n个元素,找到最小值的那个元素,如果下标不是i,则让第i个元素和那个最小的元素位置互换。
1 #include <iostream>
2 using namespace std;
3
4 int main()
5 {
6 int a[]={1,99,2,88,3,77,4,66};
7 int n=sizeof(a)/4;
8 for(int i=0; i<n; i++)
9 {
10 int pos=-1, minn=a[i];
11 for(int j=i+1; j<n; j++)
12 {
13 if(a[j]<minn) minn=a[j], pos=j;
14 }
15 if(pos!=-1) swap(a[i],a[pos]);
16 }
17 cout << a[0] ;
18 for(int i=1; i<n; i++) cout << " " << a[i];
19 cout <<endl;
20 return 0;
21 }
View Code
3、冒泡排序
冒泡排序顾名思义就是从最后往前两个元素开始进行两两比较,如果a[i]小于a[i-1],那么让他们互换位置,每比较一轮必有一个最小的元素冒泡到这些所比较元素的前面。
1 #include <iostream>
2 using namespace std;
3
4 int main()
5 {
6 int a[]={1,99,2,88,3,77,4,66};
7 int n=sizeof(a)/4;
8 for(int i=0; i<n; i++)
9 {
10 for(int j=n-1; j>i; j--)
11 if(a[j]<a[j-1]) swap(a[j],a[j-1]);
12 }
13 cout << a[0] ;
14 for(int i=1; i<n; i++) cout << " " << a[i];
15 cout <<endl;
16 return 0;
17 }
View Code
4、快速排序
基本思想就是取一个数作为中间数(一般是取第一个数作为中间数),小于它的都放到左边,大于它的都放到右边,再对每一边利用同样的思想进行处理。
1 #include <iostream>
2 using namespace std;
3
4 void QuickSort(int *a, int l, int r)
5 {
6 if(a==NULL||l>=r) return ;
7
8 int i=l, j=r, tmp=a[l];
9 while(i<j)
10 {
11 while(j>i&&a[j]>=tmp) j--;
12 a[i]=a[j];
13 while(i<j&&a[i]<=tmp) i++;
14 a[j]=a[i];
15 }
16 a[i]=tmp;
17 QuickSort(a,l,i-1);
18 QuickSort(a,i+1,r);
19 }
20
21 int main()
22 {
23 int a[]= {1,99,2,88,3,77,4,66};
24 int n=sizeof(a)/4;
25 QuickSort(a,0,n-1);
26 cout << a[0] ;
27 for(int i=1; i<n; i++) cout << " " << a[i];
28 cout <<endl;
29 return 0;
30 }
View Code
5、堆排序
堆排序其实要利用到二叉堆,二叉堆其实完全可以理解为一颗有限制的完全二叉树。
二叉堆的定义:二叉堆可以分为最大堆和最小堆。最大堆为对于所有节点它的左右节点权值一定比它小,最小堆为对于所有节点它的左右节点权值一定比它大。
二叉堆的插入:将一个序列下表从0开始一个一个往堆里插入,因为满足完全二叉树性质,所以这么做是可行的。对于插入的第i个数,那么从下往上,它的父亲节点为(i-1)/2个数,再根据二叉堆的性质进行调整。
二叉堆的删除:每次进行一次堆调整之后,根节点必是最大的(最大堆),每次把根节点a[0]取出和数组第n个数互换,然后再用数组第1个到第n-1个数再次建堆,如此反复取出再建堆,那么得到的新序列必是一个有序序列。
1 #include <iostream>
2 using namespace std;
3
4 void BuildHeap(int *a, int i, int n) //建二叉堆
5 {
6 int j=(i-1)/2; //j为i节点的父亲节点
7 while(i>0)
8 {
9 if(a[j]>=a[i]) break;
10 swap(a[i],a[j]);
11 i=j;
12 j=(i-1)/2;
13 }
14 }
15
16 void MaxHeapSort(int *a, int i, int n) //二叉堆排序
17 {
18 int j=2*i+1, tmp=a[i];
19 while(j<n)
20 {
21 if(a[j+1]>a[j]&&j+1<n) j++; //选出i节点左右孩子节点的最大值
22 if(tmp>=a[j]) break;
23 a[i]=a[j];
24 i=j;
25 j=2*i+1;
26 }
27 a[i]=tmp;
28 }
29
30
31 int main()
32 {
33 int a[]= {1,99,2,88,3,77,4,66};
34 int n=sizeof(a)/4;
35 for(int i=0; i<=n-1; i++)
36 BuildHeap(a,i,n);
37 for(int i=n-1; i>=1; i--)
38 {
39 swap(a[i],a[0]);
40 MaxHeapSort(a,0,i);
41 }
42 cout << a[0] ;
43 for(int i=1; i<n; i++) cout << " " << a[i];
44 cout <<endl;
45 return 0;
46 }
View Code
6、归并排序
归并的意思就是两个或两个以上的有序表组合成一个新的有序表。整个归并排序需要进行【lgn取上限】次,总的时间复杂度为O(nlgn)。与快速排序相比,归并排序的最大特点是:它是一种稳定的排序方法。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnLmRGMyYTOjFTYwQjMtY2NkhTLjVDZz0yYmhjMtYGZmFWZiRzNvwFN0ITM4QzLcRnbl1GajFGd0F2LcRWYvxGc19CXt92YuUWelRXauwGZvw1LcpDc0RHaiojIsJye.png)
1 #include <iostream>
2 using namespace std;
3
4 void Merge(int *a, int s, int m, int t)
5 {
6 int *b=new int[10];
7 int i=s, j=m+1, num=0;
8 while(i<=m&&j<=t)
9 {
10 if(a[i]<=a[j]) b[num++]=a[i], i++;
11 else b[num++]=a[j],j++;
12 }
13 while(i<=m) b[num++]=a[i], i++;
14 while(j<=t) b[num++]=a[j], j++;
15 for(int i=s; i<=t; i++) a[i]=b[i-s];
16 delete[] b;
17 }
18
19 void MergeSort(int *a, int s, int t)
20 {
21 if(a==NULL) return ;
22 if(s<t)
23 {
24 int mid=(s+t)/2;
25 MergeSort(a,s,mid);
26 MergeSort(a,mid+1,t);
27 Merge(a,s,mid,t);
28 }
29 }
30
31
32 int main()
33 {
34 int a[]= {1,99,2,88,3,77,4,66};
35 int n=sizeof(a)/4;
36 MergeSort(a,0,n-1);
37 cout << a[0] ;
38 for(int i=1; i<n; i++) cout << " " << a[i];
39 cout <<endl;
40 return 0;
41 }
View Code
7、希尔排序
很多人都说希尔排序是插入排序的一种改进,我看了半天也没看明白这句话。
希尔排序就是利用无空位的跳跃值gap进行跳跃排序,如果n为8,为gap的取值则为8 4 2 1, gap=gap/2,gap初始值为n/2。
对于每个gap值,都要从后往前扫一遍(以gap值大小跳跃比较),即i,i-gap,i-2*gap……。注意:只限在相邻两个扫到的数比较。
时间复杂度:O(nlog(n*n))。
1 #include <iostream>
2 using namespace std;
3
4 void ShellSort(int *a, int n)
5 {
6 for(int gap=n/2; gap>0; gap/=2)
7 for(int i=gap; i<n; i++)
8 for(int j=i-gap; j>=0; j-=gap)
9 if(a[j]>a[j+gap]) swap(a[j],a[j+gap]);
10 }
11
12 int main()
13 {
14 int a[]= {1,99,2,88,3,77,4,66,123,321,58,324,127,428};
15 int n=sizeof(a)/4;
16 ShellSort(a,n);
17 cout << a[0];
18 for(int i=1; i<n; i++) cout << " " << a[i];
19 cout << endl;
20 return 0;
21 }
View Code
8、二叉树排序
二叉树的性质:对于每个节点,它的左孩子的键值一定比它小,右孩子的键值一定比它大。
二叉树排序简单点说就是先随便设置一个根节点,然后将其他数一个一个插入到树中,权值小于此节点则往左走,大于往右走,一直找到合适的位置建立自己新的节点位置。
1 #include <iostream>
2 #include <cstring>
3 #include <sstream>
4 #include <algorithm>
5 using namespace std;
6
7 struct Node
8 {
9 int key;
10 Node *l, *r;
11 Node(){ l=NULL; r=NULL;}
12 };
13
14 Node* Insert(Node *rt, int key)
15 {
16 if(rt==NULL)
17 {
18 Node *rt=new Node();
19 rt->key=key;
20 return rt;
21 }
22 if(key<rt->key) rt->l=Insert(rt->l,key);
23 else rt->r=Insert(rt->r,key);
24 return rt;
25 }
26
27 void Printf(Node *rt)
28 {
29 if(rt->l!=NULL) Printf(rt->l);
30 cout << rt->key << " ";
31 if(rt->r!=NULL) Printf(rt->r);
32 }
33
34 int main()
35 {
36 int a[]= {1,99,2,88,3,77,4,66,123,321,58,324,127,428};
37 int n=sizeof(a)/4;
38 Node *root=new Node();
39 root->key=a[0];
40 for(int i=1; i<n; i++)
41 {
42 Insert(root,a[i]);
43 }
44 Printf(root);
45 cout << endl;
46 return 0;
47 }
View Code
9、基数排序
基数是一种不稳定的排序,它的时间复杂度为O(k*n),k表示最大数的位数,所以当一个序列中有一个很大很大的数时,它排序所花费的时间是非常高昂的。
基数排序的原理是一位一位来排序:先按个位大小排序,再按十位大小排序,接着百位……,一直排到最大位数停止。
比如这样一个数列排序: 342 ,58, 576, 356
第一次排序(个位):
3 4 2
5 7 6
3 5 6
0 5 8
第二次排序(十位):
3 4 2
3 5 6
0 5 8
5 7 6
第三次排序(百位):
0 5 8
3 4 2
3 5 6
5 7 6
结果: 58 342 356 576。
1 #include <iostream>
2 #include <cstring>
3 #include <sstream>
4 #include <algorithm>
5 using namespace std;
6
7 int maxdigit(int *a, int n) //返回数组中最大数的位数
8 {
9 int maxx=0;
10 for(int i=0; i<n; i++)
11 {
12 stringstream sa;
13 sa<<a[i];
14 string s=sa.str();
15 maxx=max(maxx,int(s.size()));
16 }
17 return maxx;
18 }
19
20 void BaseSort(int *a, int n)
21 {
22 int *count=new int[10];
23 int *tmp=new int[n];
24 int m=maxdigit(a,n);
25 int base=1;
26 for(int i=1; i<=m; i++)
27 {
28 for(int j=0; j<10; j++) count[j]=0;
29 for(int j=0; j<n; j++)
30 {
31 int k=a[j]/base%10;
32 count[k]++;
33 }
34 for(int j=1; j<10; j++)
35 count[j]+=count[j-1];
36 for(int j=n-1; j>=0; j--)
37 {
38 int k=a[j]/base%10;
39 count[k]--;
40 tmp[ count[k] ]=a[j];
41 }
42 for(int j=0; j<n; j++) a[j]=tmp[j];
43 base*=10;
44 }
45 delete[] count;
46 delete[] tmp;
47 }
48
49 int main()
50 {
51 int a[]= {1,99,2,88,3,77,4,66,123,321,58,324,127,428};
52 int n=sizeof(a)/4;
53 BaseSort(a,n);
54 cout << a[0] ;
55 for(int i=1; i<n; i++) cout << " " << a[i];
56 cout <<endl;
57 return 0;
58 }
View Code
转载于:https://www.cnblogs.com/kane0526/p/3597516.html