浅谈C++之冒泡排序、希尔排序、快速排序、插入排序、堆排序、基数排序性能对比分析(好戏在后面，有图有真相)
由于没考虑到一些情况，对以上一些算法做了改进和对比！以及昨晚把希尔排序写错而误以为其效率高过快速排序的糗事，今天一一做了更正和说明，如果你绝得本随笔不是很妥可以尝试看看这http://www.cnblogs.com/maxiaofang/p/3382927.html，有错误或不妥欢迎指正！！共同学习，共同进步！O(∩_∩)O哈哈~ 推荐一段博友分享的排序视频很艺术、很形象、很生动哦（http://www.oschina.net/question/561584_65522）
最近一段时间去武汉参加了N多笔试，在几次试题中都出现了排序。偏偏出现了我没怎么看的插入排序，弄得我好是纠结。趁回学校的机会把这几个不是很复杂的排序重新复习了一下，借此比较了一下他们的效率。让我有点以外的是在数据量达到1W~10W之间，希尔排序竟然比快速排序效率还要高。贴上完整代码！
冒泡排序
1 //冒泡排序
2 //////////////////////////////////////////////////////////////////////////
3 void BubleSort(int a[],int n)
4 {
5 int temp;
6 bool flag=false;
7 for (int i=0;i<n;i++)
8 {
9 flag=true;
10 for (int j=0;j<n-i-1;j++)
11 {
12 if(a[j]>a[j+1])
13 {
14 temp=a[j];
15 a[j]=a[j+1];
16 a[j+1]=temp;
17 flag=false;
18 }
19 }
20 if(flag) break;
21 }
22 }
冒泡排序的时间复杂度为O(n²),在数据比较小的情况下各个算法效率差不多。
希尔排序：
以前竟然没有发现，希尔排序如此短小精悍的代码。其效率很多时候并不输给快速排序其时间复杂度为O(nlogn)。
1 void ShellSort(int array[],int length)
2
3 {
4
5 int d = length/2; //设置希尔排序的增量
6 int i ;
7 int j;
8 int temp;
9 while(d>=1)
10 {
11 for(i=d;i<length;i++)
12 {
13 temp=array[i];
14 j=i-d;
15 while(j>=0 && array[j]>temp)
16 {
17 array[j+d]=array[j];
18 j=j-d;
19 }
20 array[j+d] = temp;
21 }
22 //Display(array,10);
23 d= d/2; //缩小增量
24 }
25 }
快速排序：
1 //快速排序
2 ///////////////////////////////////////
3 void Swap(int &a,int &b)
4 {
5 int temp;
6 temp=a;
7 a=b;
8 b=temp;
9 }
10
11 int Partition(int a[],int p,int r)
12 {
13 int i=p;
14 int j=r+1;
15 int x=a[p];
16 while (true)
17 {
18 while(a[++i]<x&&i<r);
19 while(a[--j]>x);
20 if (i>=j)break;
21 Swap(a[j],a[i]);
22
23 }
24 a[p]=a[j];
25 a[j]=x;
26 return j;
27 }
28
29 void QuickSort(int a[],int p,int r)
30 {
31 if (p<r)
32 {
33 int q=Partition(a,p,r);
34 QuickSort(a,p,q-1);
35 QuickSort(a,q+1,r);
36 }
37 }
正如其名快速排序，其效率也是比较高的，时间复杂度为O(nlogn)。其算法思想是每次确定一个基准值的位置，也就是函数int Partition(int a[],int p,int r)的作用。然后通过递归不断地确定基准值两边的子数组的基准值的位置，直到数组变得有序。难点还是递归的理解！
插入排序：
1 //插入排序
2 //////////////////////////////////////////////////////////////////
3 void Insert(int *a,int n)
4 {
5 int i=n-1;
6 int key=a[n];//需要插入的元素
7 while ((i>=0)&&(key<a[i]))
8 {
9 a[i+1]=a[i]; //比key大的元素往后一个位置，空出插入key的位置
10 i--;
11 }
12 a[i+1]=key;//找到位置插入元素
13 return;
14 }
15
16 //由于递归的原因数太大了栈可能会溢出
17 void InsertionSort(int *a,int n)
18 {
19 if (n>0)
20 {
21 InsertionSort(a,n-1);
22 Insert(a,n);
23 }
24 else return;
25 }
算法效率和冒泡排序相差无几，时间复杂度为O(n²)。这里要注意的问题是由于不断地递归，栈的不断开辟如果数据太大可能会导致栈溢出而不能得到结果。
堆排序：
1 //堆排序
2 ////////////////////////////////////////////////////////////////////////////
3 int Parent(int i)
4 {
5 return i/2;
6 }
7 int Left(int i)
8 {
9 return 2*i;
10 }
11 int Right(int i)
12 {
13 return 2*i+1;
14 }
15
16 //把以第i个节点给子树的根的子树调整为堆
17 void MaxHeap(int *a,int i,int length)
<补充：软件开发 , C++ ,
