排序的稳定性和复杂度：
不稳定：
选择排序（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
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
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
16 cout <
17 return 0;
18 }
复制代码
2、选择排序
对于一个序列{a[0]……a[n]}，前面i-1个元素都是已经排好序的，那么从第i到第n个元素，找到最小值的那个元素，如果下标不是i，则让第i个元素和那个最小的元素位置互换。
复制代码
1 #include
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
9 {
10 int pos=-1, minn=a[i];
11 for(int j=i+1; j
12 {
13 if(a[j]
14 }
15 if(pos!=-1) swap(a[i],a[pos]);
16 }
17 cout << a[0] ;
18 for(int i=1; i
19 cout <
20 return 0;
21 }
复制代码
3、冒泡排序
冒泡排序顾名思义就是从最后往前两个元素开始进行两两比较，如果a[i]小于a[i-1]，那么让他们互换位置，每比较一轮必有一个最小的元素冒泡到这些所比较元素的前面。
复制代码
1 #include
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
9 {
10 for(int j=n-1; j>i; j--)
11 if(a[j]
12 }
13 cout << a[0] ;
14 for(int i=1; i
15 cout <
16 return 0;
17 }
复制代码
4、快速排序
基本思想就是取一个数作为中间数（一般是取第一个数作为中间数），小于它的都放到左边，大于它的都放到右边，再对每一边利用同样的思想进行处理。
复制代码
1 #include
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
10 {
11 while(j>i&&a[j]>=tmp) j--;
12 a[i]=a[j];
13 while(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
28 cout <
29 return 0;
30 }
复制代码
5、堆排序
堆排序其实要利用到二叉堆，二叉堆其实完全可以理解为一颗有限制的完全二叉树。
二叉堆的定义：二叉堆可以分为最大堆和最小堆。最大堆为对于所有节点它的左右节点权值一定比它小，最小堆为对于所有节点它的左右节点权值一定比它大。
二叉堆的插入：将一个序列下表从0开始一个一个往堆里插入，因为满足完全二叉树性质，所以这么做是可行的。对于插入的第i个数，那么从下往上，它的父亲节点为（i-1）/2个数，再根据二叉堆的性质进行调整。
二叉堆的删除：每次进行一次堆调整之后，根节点必是最大的（最大堆），每次把根节点a[0]取出和数组第n个数互换，然后再用数组第1个到第n-1个数再次建堆，如此反复取出再建堆，那么得到的新序列必是一个有序序列。
复制代码
1 #include
2 using namespace std;
3
4 void BuildHeap(int *a, int i, int n) //建二叉堆
5 {
6 int j=(i-1)/2; //