void insertsort(struct element a[],int n){         
	int i,j; 
	struct element x;    
	for(i=1;i<n;i++){    
	    if(a[i].key<a[i-1].key)    //反序时 
	    {
	    	x=a[i];
	    	j=i-1;	    	
	    	do      //找a[i].key的插入位置 
	    	{
	    		a[j+1]=a[j];     //将关键字大于a[i].key的记录后移 
	    		count1++;
				j--;
				move1++;
			}while(j>=0&&a[j].key>x.key);
			a[j+1]=x;      //在j+1处插入a[i] 
		    move1=move1+2;
	  }
	  count1++;
	}	
}

2. 复杂度分析：

时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)

3. 运行结果：

1.3 学习链接

数据结构之直接插入排序思想_哔哩哔哩_bilibili

2. 希尔排序（分组排序）

2.1 希尔排序简介

1. 什么是希尔排序

希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法便终止。

2.排序思想

将元素等分为n小组，元素较少时，元素一般以4开始，将组内元素进行排序，一般采取插入排序
排序完成之后，将元素再次分组（n/2组），组内元素再次排序
以此类推，当n==1时，排序完成

2.2 排序实现

1. 希尔排序代码

void shellsort(struct element a[],int n){
	int i,j,k;
	struct element tmp;
	k=n/2;     //增量置初值 
	while(k>0)
	{
		for(i=k;i<n;i++)   //对所有组采用直接插入排序 
		{
			tmp=a[i];      //对相隔k个位置一组采用直接插入排序 
			j=i-k; 
			while(j>=0&&tmp.key<a[j].key)
			{
				a[j+k]=a[j];
				j=j-k;
				move2=move2+3; 
			}
			a[j+k]=tmp;
			count2++; 
		}
		k=k/2;   //减小增量 
	}
}

2. 复杂度分析

时间复杂度平均：O(N^1.3)
空间复杂度：O(1)

3. 运行结果

2.3 学习链接

[算法]六分钟彻底弄懂希尔排序，简单易懂_哔哩哔哩_bilibili

3. 快速排序

3.1 快速排序简介

1. 什么是快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

2.排序思想

先从数列中取出一个数作为基准数，从左右两端开始遍历数字，将数字进行分区
分区过程，将比这个数大的数全放在他的右边，小于或者等于它的数全放到它的左边
再对桌游区间重复第一二步，直到各个区间只有一个数为止，排序完成

3.2 排序实现

1. 快速排序代码

int hoare(struct element a[size],int low,int high){   //分区处理函数 
	int i,j;
	struct element x;
	i=low;
	j=high;
	x.key=a[i].key;   //以a[i]为基准 
	while(i<j)        //从两端交替向中间扫描，直至i=j为止 
	{   
		while(j>i&&a[j].key>=x.key){
		    j--;       //从右向左扫描，找一个小于x.key的a[j] 
     	    count3++;
		 }
		a[i]=a[j];     //找到这样的a[j],放入a[i]处 
		move3++;
		while(i<j&&a[i].key<=x.key){
		  i++;       //从左向右扫描，找一个大于x.key的a[i] 
	      count3++;
		}  
		a[j]=a[i];     //找到这样的a[i],放入a[j]处
		move3++;
	 } 
	 a[i]=x;
	 return i;
}
void quicksort(struct element a[size],int low,int high){   //对a[low....high]的元素进行快速排序 
	int i;
	if(low<high){                //区间内至少存在两个元素的情况 
		i=hoare(a,low,high);           //划为两个区 
		quicksort(a,low,i-1);          //对左分区快速排序 
		quicksort(a,i+1,high);         //对右分区快速排序 
	}	
}

2. 复杂度分析

时间复杂度：

快速排序最优的情况下时间复杂度为：O( nlogn )

快速排序最差的情况下时间复杂度为：O( n^2 )

快速排序的平均时间复杂度也是：O(nlogn)

空间复杂度：

最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况

最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况

3. 运行结果

3.3 学习链接

快速排序算法_哔哩哔哩_bilibili

4. 堆排序

4.1 堆排序简介

1. 什么是堆排序

堆排序就是基于这种结构而产生的一种程序算法。堆是一种叫做完全二叉树的数据结构，可以分为大根堆，小根堆，即子结点的键值或索引总是小于（或大于）它的父节点。

2.排序思想

首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
将顶端的数字弹出堆，然后将末尾的数放置到堆顶
将剩余的n-1个数再构造成大根堆
如此反复执行2，3，便能得到有序数组

注意:升序用大根堆，降序就用小根堆(默认为升序)，前提是排序满足完全二叉树

4.2 排序实现

1. 堆排序代码

void heap(struct element a[size],int i,int m){   //调整堆的函数 
//i是根结点编号，m是以i为根的子树的最后一个结点编号 
	struct element x;
	int j;
	x.key=a[i].key;               //保存记录内容 
	j=i*2;                     //j为左孩子编号  
	while(j<=m){
		count4=count4+2;
		if(j<m)
		    if(a[j].key>a[j+1].key){   //当结点i有左、右两个孩子时，j取关键较小的孩子编号 
		        j++;
		        
		    }
		    if(a[j].key<x.key){        //向下一层探测 ,若根节点大于最小孩子的关键字 
				a[i].key=a[j].key;     //将a[j]调整到双亲节点位置上 
		    	i=j;
		    	j=2*i;
		    	move4=move4+3;
			}
			else
			    j=m+1;     //x.key小于左、右孩子的关键字时，使j>m，以便结束循环 （若根节点小于最小孩子关键字） 
	}
	a[i].key=x.key;      //被筛选结点放入最终位置上 
}
void heapsort(struct element a[size],int n){        //堆函数的主体函数 
	int i,v;
	struct element x;
	for(i=n;i>0;i--)
		a[i].key=a[i-1].key;   
	for(i=n/2;i>=1;i--)
		heap(a,i,n);
	for(v=n;v>=2;v--){
		x.key=a[1].key;              //堆顶堆尾元素交换 
		a[1].key=a[v].key;
		a[v].key=x.key;
		move4=move4+3;
		heap(a,1,v-1);          //这次比上次少处理一个记录 
	}
	for(i=0;i<n;i++)   
	    a[i].key=a[i+1].key;  
	for(i=0;i<n/2;i++){    
		int k;
		k=a[i].key;
		a[i].key=a[n-i-1].key;
		a[n-i-1].key=k;
		
	}
}

2. 复杂度分析

时间复杂度：最好，最坏，和平均时间复杂度都为：O(nlogn)

空间复杂度：O(1)

3. 运行结果

4.3 学习链接

十分钟搞定堆排序_哔哩哔哩_bilibili

5. 冒泡排序

5.1 冒泡排序简介

1. 什么是冒泡排序

冒泡排序(BubbleSort)以其”在排序过程中相邻元素不断交换，一些元素慢慢被换到最后，看起来就像是元素在冒泡一样“而得名，是一种简单的基于关键词比较的排序算法。

2. 排序思想

外循环是遍历每个元素，每次都放置好一个元素
内循环是比较相邻的两个元素，把大的元素交换到后面
当两个循环都遍历完毕就说明全部元素排序好了

冒泡排序分从大到小和从小到大两种排序方式。它们的唯一区别就是两个数交换的条件不同，从大到小排序是前面的数比后面的小的时候交换，而从小到大排序是前面的数比后面的数大的时候交换。

5.2 排序实现

1. 冒泡排序代码

void bubblesort(struct element a[],int n)
{
	int i,j;
	struct element tmp;
	bool exchange;
	for(i=0;i<n-1;i++)
	{
		exchange=false;       //一趟前exchange为假 
		for(j=n-1;j>i;j--){   //归位a[i],循环n-i-1次 
		  if(a[j].key<a[j-1].key)          //相邻两个元素反序时 
		  {
		  	tmp.key=a[j].key;           //将a[j]和a[j-1]两个元素交换 
		  	a[j].key=a[j-1].key;
		  	a[j-1].key=tmp.key;
		  	exchange =true;        //一旦有交换，exchange置为真 
		    move5=move5+3;
		  }
		  count5++; 
	    }
	    if(!exchange)         //本趟没有发生交换，中途结束算法 
		    return;
	}
 }

2. 复杂度分析

时间复杂度：

最好情况的时间复杂度为O(n）

最坏情况子下的时间复杂度为O(n^2)

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

空间复杂度：

最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；

最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；

平均的空间复杂度为：O(1)；

稳定性：

因为每次比较后如果两个相邻元素相等我们并不会将他们交换，所以冒泡不会改变相同元素的下标，所以冒泡排序是一个稳定的排序

3. 运行结果

5.3 学习链接

冒泡排序法_哔哩哔哩_bilibili

6. 简单选择排序

6.1 简单选择排序简介

1. 什么是简单选择排序

简单选择排序采用最简单的选择方式，从头至尾顺序扫描序列，找出最小的一个关键字，和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终达到排序的目的

2.排序思想

从待排序序列中，找到数值最小的元素
如果最小元素不是序列中的第一个元素，将最小的元素和起始位置的元素交换
从余下的元素中，找出依次数值最小的元素，重复第一二步，直到排序结束

6.2 排序实现

1. 简单选择排序代码

void selectsort(struct element a[],int n)
{
	int i,j,k;
	struct element tmp;
	for(i=0;i<n-1;i++)    //做第i趟排序 
	{
		k=i;
		for(j=i+1;j<n;j++){   //在当前无序区a[i...n-1]中选出key最小的a[k] 
		   count6++;
		   if(a[j].key<a[k].key)
		      k=j;           //k记下目前找到的最小关键字所在的位置 
		}
		if(k!=i){
		   	tmp.key=a[i].key;   //a[i],a[k]两个元素交换 
		   	a[i].key=a[k].key;
		   	a[k].key=tmp.key;
		   	move6=move6+3; 
		   } 
	}
}