直接插入排序法与希尔排序法——插入类排序_直接插入法

目录

一、插入类排序的基本思想

二、直接插入排序法

1.基本思想

2.代码

 3.时空复杂度与稳定性

三、希尔排序法

1.基本思想

2.代码

  3.时空复杂度与稳定性

---

一、插入类排序的基本思想

在一个已经排好序的记录子集的基础上，每一步将待排序的记录有序地插入已经排好序的有序子集中，形成新的有序子集。重复这一操作，直到将待排序的记录全部插入为止。

可以用打扑克牌时的抓牌来加深理解。抓牌就是一个生活中很常见的插入排序的例子，每从牌堆中抓一张牌，将它插入到合适的位置，直到牌抓完为止，即可得到一个有序的序列。

下面代码中测试的数据均用随机生成数，如果不懂的小伙伴，可以去瞄一眼我的另一篇文章

链接：随机生成数——C语言

二、直接插入排序法

1.基本思想

      将第i个记录插入到前面i-1个已经排好序的序列中。具体过程：将第i个记录的关键字Ki与前面的记录的关键字Ki-1,Ki-2.....K1进行比较，如果大与Ki则后移一位，直到遇到小于或等于Ki的关键字，那么其后面必然有一个空位置（最后一次比较时后移留出的空位），将第i个记录插入到该空位置即可，到此一趟插入排序完成。下面依次将未插入的记录按照这个规则插入即可，最终得到一个有序的递增序列。

2.代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//打印序列值
void Print(int a[],int n){
	int i;
	for(i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
} 
//直接插入排序法
void InsertSort(int r[],int n){
	int i,j;
	for(i=2;i<=n;i++){//因为默认第一个记录即为有序，故从第2个记录开始插入 
		r[0]=r[i];//监视哨 ,存放待插入的关键字值 
		j=i-1;
		while(r[0]<r[j]){
			r[j+1]=r[j];//将大于待插入的关键字后移
			j--; 
		}
		r[j+1]=r[0];//将待插入的关键字插入到有序的记录中 
	}
} 
int main(){
	int i,random[10];
	srand((unsigned int)time(NULL));
	for(i=0;i<10;i++){
		random[i]=rand()%100;
	} 
	printf("随机序列为：\n");
	Print(random,10);
	InsertSort(random,10);
	printf("经过直接插入排序后：\n");
	Print(random,10);
} 

运行结果

 3.时空复杂度与稳定性

算法的时间复杂度为：O（n^2）

算法的空间复杂度为：O（1）

直接插入排序是一种稳定的排序方法。

其适用于待排序的记录较少且基本有序的情况。

三、希尔排序法

1.基本思想

     为什么我将直接插入排序法与希尔排序法放在一起讨论？原因在于希尔排序法是直接插入排序法的进一步优化的算法，使得排序的性能有了一个极大的飞跃！

    希尔排序法又称为缩小增量排序法，是一种基于插入思想的排序方法。它的伟大之处在于很好的利用了直接插入法的最佳性质：待排序记录较少且基本有序。所以希尔排序法的思路是将待排序的序列按照增量递减的方式分成若干个组，将原来较大的序列不断切割成一个个小的子序列，使子序列符合“数目少且基本有序”这一条件，然后分别对各个子序列进行直接插入排序，经过上述的操作后，使得整个序列已经基本有序，然后对整个序列进行一次直接插入排序，即可得到一个整体有序的序列，排序完成。

    在具体实现时，首先要选定两个记录间的距离d1，在整个待排序的序列中将距离为d1的记录分成一组，进行组内的直接插入排序；然后再取更小的距离d2，在整个待排序的序列中距离为d2的记录分成一组，再次进行组内直接插入排序......如此反复操作，直到选定的距离dt=1为止。此时只有一个子序列，即整个序列，排序完成。

2.代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//打印序列值
void Print(int a[],int n){
	int i;
	for(i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
} 
//希尔排序法
void ShellInsert(int r[],int length,int add){
	int i,j;
	for(i=1+add;i<=length;i++){
		if(r[i]<r[i-add]){
			r[0]=r[i];//备份要插入的关键字值 
			for(j=i-add;j>0&&r[0]<r[j];j-=add){
				r[j+add]=r[j];//交换位置
			}
			r[j+add]=r[0]; 
		}
	}
}
void ShellSort(int r[],int length,int add[],int n){
	int i;
	for(i=0;i<=n-1;++i){
		ShellInsert(r,length,add[i]);
	} 
} 
int main(){
	int i,j,random[10],add[10],count=0;
	srand((unsigned int)time(NULL));
	for(i=0;i<10;i++){
		random[i]=rand()%100;
	} 
	printf("随机序列为：\n");
	Print(random,10);
	//构造增量序列
	i=10;
	do{
		j=i/2;
		i=j;
		add[count++]=j;
	}while(i>=1);
	ShellSort(random,10,add,count-1);//count-1为实际增量数组的长度 
	printf("经过希尔排序后：\n");
	Print(random,10);
	return 0;
} 

运行结果

  3.时空复杂度与稳定性

希尔排序法的时间耗费主要在所取得“增量”序列的函数，所以其时间复杂度的分析则变得复杂，到目前为止，尚未有人能够求得一种最好的“增量”序列。

空间复杂度为：O（1）

希尔排序是一种不稳定的排序方法。因为在排序过程中，相同关键字的领先关系发生了变化。

码字不易，点个赞再走哦~

关注我，一起进步！