那些年,我们一起玩过的排序之插入排序！

插入排序：
基本思想：
每次将一个待排序的记录,按其关键字的大小插入到前面已经排好序的有序序列中的适当位置上,直到全部记录插入完成为止。
1：直接插入排序
依次将记录序列中的每一个记录插入到有序序列中，使有序序列的长度不断地扩大。

直接插入法算法简单，容易实现，其算法的时间复杂度是O(n平方)。

#include<stdio.h>

main(){

	int i,j;

	int r[9] = {0,42,36,56,78,67,11,27,36};/*定义数组并赋初值,其中r[0]为监视韶,初值为0*/

	for(i = 2;i<=8;++i){

		if(r[i]<r[i-1]){/*如果小于 需将r[i] 插入到前面有序序列中*/

			r[0] = r[i];/*将r[i]放入到监视哨中*/

			for(j=i-1;r[0]<r[j];--j)

				r[j+1] = r[j];/*记录后移*/

			r[j+1] = r[0];/*插入到正确的位置*/

		}

	}

	for( i=1;i<=8;i++){

		printf("%d ",r[i]);/*输出*/

	}

}

2：折半插入排序。
折半插入排序是对直接插入排序的改进算法,它是利用折半来实现插入位置的定位，适用于待排序记录数量较大的情况。

#include<stdio.h>

main(){

	int i,j,low,high,m;

	int r[0]= {0,42,36,56,78,67,11,27,36};

	for(i = 2;i<=8;++i){

		r[0] = r[i];/*将r[i]暂存到r[0]中*/

		low =1;

		high = i - 1;

		while(low<=high){//在r[0] 和r[i] 中折半查找插入位置

			m = (low+high)/2;

			if(r[0]<r[m])

				high = m-1;

			else

				low = m+1;

		}

		for(j=i-1;j>=high+1;--j){

			r[j+1] = r[j];//插入位置以后的记录后移

			r[high+1] = r[0];//插入记录

		}



		for(i=1;i<=8;i++){

			printf("%d ",r[i]);

		}

	}

}

3 二路插入排序
是对折半插入排序的改进算法，它是利用增加辅助空间来减少排序过程中移动的次数。

具体做法：
建立一个和待排序序列r[n]同类型的数组d[n]作为辅助空间,首先将r[0]的值赋值给d[0],将d[0]看成是处于最后有序序列中处于中间位置的记录,然后从r[1]开始依次将记录插入到d[0]之前或之后的有序序列中。

#include<stdio.h>

main(){

	int i,j,first,final;

	int r[8] = {42,36,56,78,67,11,27,36};/*定义并初始化*/

	int d[8];

	d[0] = r[0];

	first =final = 0;

	for(i=1;i<8;i++){

		if(r[i]>=r[0]){/*r[i]插入到r[0]之后的序列*/

			for(j= final;r[i]<r[j];j--)//寻找r[i]应插入的位置

				d[j+1] = d[j];//后移元素

			d[j+1]=r[i];/*将r[i]插入到正确的位置*/

			final ++;

			

		}else{/*r[i]插入到r[0]之前的序列*/

			if(first ==0){//若指针first在初始位置

				first = 7;

				d[first] = r[i];

			}else{

				for(j=first;r[i]>d[j]&&j<8;j++)

					d[j-1] = d[j];//向前移动元素

				d[j-1] = r[i];

				first --;

			}

		

		}

	}

	if(first < final)//若first所指的位置在final之前 则依次输出

		for(i=first;i<8;i++)

			printf("%d ",d[i]);

	else{

			for(i=first;i<8;i++)//输出前半序列

				printf("%d ",d[i]);

			

			for(i=0;i<final;i++)//输出后半序列

				printf("%d ",d[i]);

		}

	printf("\n");

}

4：希尔排序
希尔排序方法又称为缩小增量排序,是对直接插入排序方法的改进。
基本思想：
将整个待排序的记录序列划分成若干个子序列,然后分别对每个子序列进行直接插入排序。
不稳定排序。

#include<stdio.h>

main(){

	int r[10] = {45,38,63,85,71,17,28,45,6,90};

	int d,i,j,k,x;

	d = 10/2;//取第一个步长值

	while(d>=1){

		for(i=d;i<10;i++){//对各组进行直接插入排序

			x = r[i];//记录r[i]暂存x中

			j = i-d;//确定每组中的记录r[i]前一个位置

			while(j>=0 && x<r[j]){//在组中查找插入位置

				r[j+d] = r[j];//记录后移

				j = j-d;//记录位置前移一个步长

			}

			r[j+d]=x;/*插入记录*/

			printf("%d %d ",i,r[i]);

		}

		d = d/2;//缩小步长,取下一步长值

	}

	for(k=0;k<10;k++)

		printf("%d ",r[k]);



}

谨以此和大家一起学习。后续会有选择排序和交换排序