数据结构—排序算法汇总（插入排序，交换排序，选择排序，二路归并排序，基数排序）

在没有特殊说明的情况下，默认排序结果是升序。 

对于直接插入排序，设A[n]是一个有n个数的待排序数组，现假设要排序的位置是i，其执行的过程为（第0号位置不适用，从1号开始）：

1、首先保存第i号元素，把第i号元素放在第0号位置，充当哨兵的作用，这样可以减少循环条件，相对来说会优化一点点；

2、1— i-1位置的元素都已排好序，将第i个位置的元素与前i-1个元素依次比较，直到找到小于等于自己的元素停止，假设位置是k。

3、将第k+1—i-1位置上的所有元素后移，空出的第k+1个位置放第i个元素。

具体代码：

//直接插入排序 
void InsertSort(int a[],int n)
{
	int j;
	for(int i=2;i<=n;i++)
	{
		if(a[i]a[0];j--)        //从后往前寻找待插入位置 
			{
				a[j+1]=a[j];                //向后移动 
			}
			a[j+1]=a[0];               //将第i个元素插入 
		}
	}
}

空间复杂度：O(1)；

时间复杂度：

最好情况：O(n)；       //原始表中有序，每次插入一个元素，只需要比较一次，而无需移动；

最坏情况：O(n)；       //原始表也是有序，但是是逆序。总的比较次数达到最大，移动次数也达到最大。

平均时间复杂度：O(n^2)；     

稳定性：每次都是从后往前移动元素，不会出现相同元素相对位置发生变化的情况，稳定。

直接插入排序即适合顺序存储，也适合链式存储的线性表。但是链式存储只是减少了移动的次数，比较的次数仍然回达到平方的数量级，时间复杂度仍然是平方级。

但其适用于待排序元素基本有序。 

折半插入排序是针对直接插入排序算法的一个小改进，其改进之处在于，由于在插入第i个元素时，前i-1个元素是排好序的，所以在查找这步中，我们可以使用折半查找，找到待插入位置，然后再移动。

具体代码：

//折半插入排序
void InsertSort(int a[],int n)
{
	int i,j,low,high,mid;
	for(i=2;i<=n;i++)
	{
		a[0]=a[i];
		low=1,high=i-1;
		while(low<=high)       //折半查找的思想，寻找待插入位置 
		{
			mid=(low+high)/2;
			if(a[mid]<=a[0])
			{
				low=mid+1;
			}
			else
			high=mid-1;
		}
		for(j=i-1;j>=high+1;j--)          //将low —i-1位置的元素后移 
		{
			a[j+1]=a[j];
		}
		a[high+1]=a[0];         //插入到low的位置 
	}
}

时间复杂度：折半查找虽然减少了比较的次数，但是移动的次数还是没变，因此，折半查找的时间复杂度仍为O(n^2)；

折半查找在处理的时候，特别注意了元素值相等的情况，当a[mid]=a[i]的时候，我们继续往后寻找合适的位置，这样做的好处就是可以保证插入排序的稳定性。

希尔排序是针对直接插入排序的一种改进。因为直接排序在数组相对有序的情况下，时间复杂度比较小，所以希尔排序的思想就是：先将待排序表分割成若干个形如：a[i，i+d，i+2d……]的“特殊”子表，即把相隔某个增量的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素都呈现出“基本有序”时，再对全体记录进行一次直接插入排序。

其实希尔排序只不过是增加了一个增量，每次比较的是同一增量的元素，每轮排序完成后，增量减半，但是其基本思想就是直接插入排序。要注意希尔排序的移动的判定条件。

具体代码：

//希尔排序
void ShellSort(int a[],int n)
{
	int d;         //增量
	for(d=n/2;d>=1;d/=2)     //不断缩短增量排序 
	{
		for(int i=d+1;i<=n;i+=d)      //前面元素是排好序的，从d+1开始 
		{
			if(a[i]0&&a[0]

时间复杂度：最坏情况下（当d取1时：O(n)；当n在某个特定范围时，时间复杂度约为：O(n^1.3)。

通过排序过程可以看出，希尔排序是个不稳定的排序算法。并且由于它需要使用增量d找到属于同一个子表的元素，所以它不能使用链表这种不具备随机访问特性的存储结构。

冒泡排序是一种基于交换的思想，每一趟排序将最大值或者最小值排到前面，每一趟结束后， 每一个位置的元素就是其最终所在的位置。

 //冒泡排序
void BubbleSort(int a[],int n)
{
 	for(int i=0;ia[j+1])          //若逆序 
			{
				swap(a[j],a[j+1]);         //则交换 
				flag=true;
			}
		}
		if(flag==false)             //本趟遍历没有发生交换，说明已经有序 
		return ;	
	}
}

快速排序是基于分而治之的思想：每一次在待排序的表中选择一个数作为基准，通过一趟排序将待排序表划分为两个部分，每一次排完序，比基准小的元素都在左边，比基准大的元素都在右边，然后左右两边递归进行排序，直到每个部分只有一个元素或者为空位为止。

在该代码中，假设每次都以第一个元素作为基准进行划分。

具体代码：

#include 
using namespace std;
int s[100];

int Partition(int a[],int low,int high)
{
	int p=a[low];               //选择基准元素 
	while(low=p)   //把基准后面比基准大的元素往前移 
		high--;
		a[low]=a[high];
		while(low>n;
	for(int i=0;i>s[i];
	QuickSort(s,0,n-1);
	for(int i=0;i 
可以看出，快速排序的算法关键在于划分，那么该算法的性能也就主要取决于划分操作的好坏。快速排序需要利用递归进行，所以需要一个递归工作栈作为辅助空间。
 
空间复杂度就是该栈所需的空间，最好情况下是：O(logn)；最坏的情况就是表基本有序或者基本逆序。空间复杂度为O(n)；平均空间复杂度为:O(logn)；
 
时间复杂度：最好的情况下：O（nlogn)；最坏的情况下：O(n)；
 
可以推算出，快排是一种不稳定的算法。
 
虽然快排每次排序后并不产生有序子序列，但是每次排序后都会把基准放到其最终位置上。
 
5、选择排序  
5.1 简单选择排序  
算法思想：每一趟排序都是在待排序元素中选取关键字最小（或最大）的元素加入到有序子序列中。
 
具体代码：
 
//简单排序
void SelectSort(int a[],int n)
{
	for(int i=0;i 
空间复杂度：O(1)；
 
时间复杂度：O(n*n)；
 
该算法不稳定，但其既适用于顺序表，又使用于链表。
 
5.2 堆排序  
堆排序是一个性能比较优秀的算法，它也是基于选择排序的思想，大顶堆：在完全二叉树中，根>=左右结点。小顶堆刚好相反。
 
堆排序分为：建堆和输出堆顶元素，再继续调整堆。
 
建堆过程（以大顶堆为例）：从完全二叉树中的最后一个非终端结点，也就是第n/2个结点 开始，若该结点存在左右孩子，则判断该结点的左右孩子是否比根结点大，若是，则选择最大的一个孩子结点和根结点互换，但是互换后可能会破坏其孩子结点的堆，所以继续采用刚才方法构造下一级堆，直到以该结点为根的子树构成大顶堆为止。
 
排序过程（以大顶堆为例）：每一趟排序将堆顶元素加入到有序子序列（与待排序元素序列中的最后一个元素交换），并将待排序元素序列再次调整为大顶堆。
 
大顶堆的具体代码：
 
#include 
using namespace std;
int s[100];
//大根堆排序
void HeadAdjust(int a[],int k,int len)
{
	a[0]=a[k];          //先把第k个元素存着，以期后面找到合适的位置放置
	for(int i=2*k;i<=len;i*=2)          //顺着k较大的子结点向下筛选 
	{
		if(i=1;i--)       //从最后一个非终端结点到根结点调整堆 
	{
		HeadAdjust(a,i,len);
	}
 } 

void HeapSort(int a[],int len)
{
	BuiltMaxHeap(a,len);              //先建堆 
	for(int i=len;i>1;i--)       //n个元素需要进行n-1趟排序 
	{
		swap(a[i],a[1]);           //和堆低元素交换，将最大值后移，实现升序 
		HeadAdjust(a,1,i-1);     
	}
 } 
int main(int argc, char** argv) {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>s[i];
	HeapSort(s,n);
	for(int i=1;i<=n;i++)
	{
		cout< 
小顶堆的分析过程和大顶堆类似，所以，这里直接给出代码。需要注意的是：基于大顶堆的排序是升序，基于小顶堆的排序是降序。
 
 小顶堆的具体代码：
 
#include 
using namespace std;
int s[100];
//小根堆排序
void HeadAdjust(int a[],int k,int len)
{
	a[0]=a[k];          //先把第k个元素存着，以期后面找到合适的位置放置
	for(int i=2*k;i<=len;i*=2)          //顺着k小的子结点向下筛选 
	{
		if(ia[i+1])       //i=1;i--)       //从最后一个非终端结点到根结点调整堆 
	{
		HeadAdjust(a,i,len);
	}
 } 

void HeapSort(int a[],int len)
{
	BuiltMinHeap(a,len);              //先建堆 
	for(int i=len;i>1;i--)       //n个元素需要进行n-1趟排序 
	{
		swap(a[i],a[1]);           //和堆低元素交换，将最小值后移，实现降序 
		HeadAdjust(a,1,i-1);     
	}
 } 
int main(int argc, char** argv) {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>s[i];
	HeapSort(s,n);
	for(int i=1;i<=n;i++)
	{
		cout< 
空间复杂度：O（1）；
 
时间复杂度为：最好，最坏和平均都是O(nlogn)；
 
可以推算出该算法是不稳定的。 
 
6、归并排序  
 归并排序的算法思想：将待排序表中的n个记录视为有n个有序的子表，但是每个子表的长度为1，然后两两归并，得到n/2向上取整个长度为1或2的有序表，继续两两归并，如此重复，直到合并为一个长度为n的有序表为止，这就是2路归并排序。
 
具体代码：
 
#include 
using namespace std;

#define n 100
int s[n];

int *b=(int *)malloc(sizeof(int)*(n+1));       //辅助数组B
int i,j,k;
void Merge(int a[],int low,int mid,int high)
{
	for(k=low;k<=high;k++)           //先将表中数据复制到辅助数组中 
	{
		b[k]=a[k];
	}
	for(i=low,j=mid+1,k=i;i<=mid&&j<=high;)
	{
		if(b[i]<=b[j])
		{
			a[k++]=b[i++];
		}
		else
		{
			a[k++]=b[j++];
		}
	}
	while(i<=mid)         //其中有一个表中还有数据 
	a[k++]=b[i++];
	while(j<=high)
	a[k++]=b[j++];
} 
void MergeSort(int a[],int low,int high)
{
	if(low>m;
	for(int i=1;i<=m;i++)
	{
		cin>>s[i];
	}
	MergeSort(s,1,m);
	for(int i=1;i<=m;i++)
	cout< 
归并排序的核心操作是：把数组 内的两个有序序列归并为一个。
 
空间复杂度：O（n）；虽然递归也需要空间，但是归并树可以看成是一个倒立的二叉树。递归深度 
时间复杂度：O(nlogn)。
 
7、基数排序  
基数排序不是基于比较和移动的思想，而是基于关键字各位的大小进行排序。
 
基数排序的基本思想（以递减序列为例）：
 
1、初始化：设置r个空队列，Qr-1,Qr-2,……，Q0，按照各个关键字位权重递减的次序（个、十、百），对d各关键字位分别做“分配” 和“收集”。
 
2、分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入Qx队尾。
 
3、收集：把Qr-1，Qr-2，……，Q0各个队列中的结点依次出队并链接。
 
空间复杂度：由于基数排序是用链式存储。需要辅助空间r个队列。所以时间复杂度为O（r)。
 
时间复杂度：O（d(n+r)）；基数排序需要进行d趟分配和收集，一趟分配需要O（n），一趟收集需要O（r）。
 
可以推算出：基数排序是稳定的。