最近实现的各种排序思路和代码

最近为了准备实习生面试，看了算法导论前面一部分的内容，还实现了一些常见的排序算法
现在稍微整理一下最近的工作，可能有些不足之处，实现的也是最简单的整形的操作，以后继续完善之。
首先是插入排序，插入排序的原理和我们打扑克一样，当你拿到一张新牌的时候，你会从后往前找，因为已经到手的部分是已经排序好的（如果你是高手乱序打牌请飘过）找到新牌可以插入的合适位置放入，然后继续拿牌。
代码如下

void insertSort(int* a,int len)//插入排序
{
	int i=0,j=0;
	int tmp;
	for(i=1;i<len;i++)//数组第二个数字开始
	{
		j=i;
		tmp = a[i];//记录插入的数字
		while(j > 0 && tmp < a[j-1])//向前寻找位置插入
		{
			a[j]=a[j-1];
			j--;
		}
		a[j]=tmp;
	}
}

接着是冒泡排序，方法就是每次从头到上次结束的位置（初始为尾部）一一比较将最大的数字往最边上推，就像气泡往上升的过程，所以叫冒泡排序。代码如下

void swap(int& a,int& b)
{
	int tmp;
	tmp=b;
	b=a;
	a=tmp;
}
void bubbleSort(int* a,int len)
{
	int i,j;
	for(i = len-1; i>0 ; --i)
	{
		for( j= 0; j < i ; ++j)
		{
			if( a[j] > a[j+1] )
			{
				swap(a[j],a[j+1]);
			}
		}
	}
}

二路归并排序，是一个很重要的排序，出现在外排序中，所以需要掌握，也是分治思想的一个好例子，直接上代码。

void merge(int *a,int left,int mid ,int right)//归并排序-合并
{
	int i,j,k;
	int n,m;
	n= mid - left + 1;
	m= right - mid;
	int leftA[n+2];// 最好从堆里分配空间，数据量大了这个程序直接挂，限额是1M的栈容量
	int rightA[m+2];
	for(i=1;i<=n;i++)
	{
		leftA[i]=a[left+i-1];
	}
	for(i=1;i<=m;i++)
	{
		rightA[i]=a[mid+i];
	}
	leftA[n+1]=MaxInt;
	rightA[m+1]=MaxInt;
	i=1;
	j=1;
	for(k=left;k<=right;++k)
	{
		if( leftA[i] < rightA[j] )
		{
			a[k]=leftA[i++];
		}
		else
		{
			a[k]=rightA[j++];
		}
	}
}
void merge_sort(int *a,int left,int right)//归并排序主函数
{
	if( left < right )
	{
		int mid=(left+right)/2;
		merge_sort(a,left,mid);
		merge_sort(a,mid+1,right);
		merge(a,left,mid,right);
	}
}

现在开始效率高点的排序了，快速排序和堆排序都是算法导论里所说的，理论上接近了比较排序法可以达到的最优复杂度O（NlogN）。如果想要再提升速度就只有另辟蹊径了，即采用非比较的排序，后面会说。
快速排序是典型的二分思想的应用，每次选取一个比较值，然后从前后同时开始向中间偏离，将左边大于比较值的和右边小于比较值的数字对换，直到左边的和右边的相遇。结束一轮，这样的结果是相遇的点上满足 左边的所有值都小于右边，然后递归调用该算法。
好像说的有些乱。。。看代码吧。

int qsort_partion(int* a,int start,int end)
{
	int i=start,j=end;
	int judge = a[ end ];//选择最后一个数字作为比较值
	while(1)
	{
		while( a[i] < judge ) ++i;
		--j;
		while( a[j] > judge ) --j;
		if( i >= j ) break;
		else
		{
			swap(a[i],a[j]);//交换需要调整的值
			++i;
		}
	}
	swap(a[end],a[i]);//将当前值于比较值对换，然后就完成以i 为界，一边的值都小于a[i],另一边都大于a[i]
	return i;
}

void quickSort(int* a, int start ,int end)
{

	if(start <end )
	{
		int q = qsort_partion(a,start,end);
		quickSort(a,start,q-1);
		quickSort(a,q+1,end);
	}
}

快排只要保证每次分割的调用是常数比例，即使是很不对称的 1/8 7/8 也可以满足O（NlogN）的复杂度，最怕有序的数组，简直是噩梦。因为每次选取最后值比较，其实每次都只遍历而无作为，会导致复杂度变成N的平方。所以真正能用的快排都会采用随机定位，和三数均值的方法防止这类问题。STL源码里引进了一种新的排序方法基于快排的，叫introSort 他其实就是加入了恶化处理机制（设置一个阀值，但递归次数超过这个值时候进行处理），对于有序数组，早些发现然后采用插入排序完成，插入排序对有序数组效率很高。

接下来是堆排序，堆排序有分最大堆和最小堆，实现机制反正差不多，我实现的是最大堆。
堆排序需要做的就是构建堆，堆调整（向上调整，和向下调整）然后就是排序的具体步骤了，这个理解起来确实不难，但我当时写加调试用了1个半小时。。基本功的问题。
上代码

void adjust_heap(int* a , int i)//调节该点 OK
{
	int tmp = a[i];
	while( i > 1 )
	{
		if( a[i>>1] < tmp )
		{
			a[i]=a[i>>1];
			i>>=1;
		}
		else
		{
			break;
		}
	}
	a[i] = tmp ;
}
void adjustDown_heap(int* a ,int size)
{
	int tmp = a[1];
	int i=1;
    while( i<= size )//有孩子
    {
    	if( 2*i > size ) break;//越界判断！！！！！
    	if( (2*i+1) > size)//只有一个孩子
    	{
    		if( tmp > a[2*i] )
    		{
    			break;
    		}
    		else
    		{
    			a[i]=a[2*i];
    			i=2*i;
    			continue;
    		}
    	}
    	if( tmp > a[2*i] && tmp > a[(2*i+1)])//两个孩子
    	{
    		break;
    	}
    	else//选择和较大的孩子节点替换
    	{
//    		cout<<"左孩子"<<2*i<<"  右孩子"<<2*i+1<<endl;
    		if( a[2*i] > a[(2*i+1)] )
    		{
    			a[i]=a[2*i] ;
    			i*=2;
    		}
    		else
    		{
    			a[i]=a[(2*i+1)];
    			i=2*i+1;
    		}
    	}
    }
    a[i] = tmp;
}

void make_heap(int* heap , int size )// OK
{
	int i;
	for(i=1;i<=size;i++)
	{
		adjust_heap(heap, i);
	}
}

void heap_sort(int* src, int size)
{
	int i;
    int tmp;
	make_heap(src, size);

	for( i= 1 ; i <= size ; ++i )
	{
        tmp=src[size+1-i];//保存最后一个元素
		src[size+1-i] = src[1];//将堆顶用最后个元素替代
		src[1] = tmp;//最后一个元素替代堆顶
		adjustDown_heap( src,size-i );//堆变小，进行调整
	}
}

堆排序和快速排序都是原地排序，可以说这两个思想都太牛了，一般人很难想到的，我们站在巨人的肩膀上应该更加努力。。废话说多了，这两个都是渐进最优的比较排序算法。
那么还有更快的么，算法导论里给了几个，计数排序，基数排序，桶排序。
我仅仅实现了计数排序，但对三种排序都稍微做了了解。
计数排序就是用空间换时间，并不进行任何比较，就是对数字进行统计。然后根据统计结果直接放入新数组的指定位置，所以这个排序可以在O(N)的复杂度完成排序，但空间复杂度为O(N+M)N为数组长度，M为数值范围。需要指定一个数值的范围，开辟一个数组记录该数字出现的次数。上代码

const  int range=1000;
void count_sort(int* a,int* b,int size)//计数排序，需要知道数据的范围range
{
	int i;
	int count[ range+1 ];
	for( i=0;i<=range;++i )
	{
		count[i]=0;
	}
	for( i= 1 ;i <=size;++i )
	{
		count[a[i]]+=1;
	}
	for( i=1; i<=range;++i )
	{
		count[i]+=count[i-1];
	}

	for( i=1 ;i<=size;++i )
	{
		b[count[a[i]]]=a[i];
		count[a[i]]-=1;
	}
}

其实很容易看出来，range就是这种排序的限制，Short类型都有2的16次方大。。这个数组得开多大啊。。所以这样看，计数排序的意义就是为基数排序服务。基数排序就是把要排的数字分割成1个一个的位数，比如138 就是1， 3， 8
                         241     2， 4， 1
                         163     1， 6， 3

就拿上面的数字为例，先对个位排序得到   
                                        2,4,1
                                        1,6,3
                                        1,3,8

然后对十位进行排序得到                 
                                        1,3,8
                                        2,4,1
                                        1,6,3

然后对百位进行排序                     
                                        1,3,8
                                        1,6,3
                                        2,4,1

这样结果就出来了，所有的数字就可以分解成range=10的从最低位到最高位的计数排序。
这样假设有d 位，那么完成的复杂度就是O(d*N) 比快排快吧。。
至于桶排序的思想其实类似，就是将数值按照一定范围进行划分，将某个范围内的数值放到一起（这里称为桶），然后对放在一起的进行排序，再从每一个桶中读出已经排序好的元素。

这些代码都是以升序为目的的，没有使用任何高级C++技术。 排序就到这里了，欢迎点评指正！