C语言数据结构——插入排序

约定不等于承诺〃 2023-10-06 18:01 58阅读 0赞

定义排序算法的数据元素的数据结构如下：

typedef struct
    {
        
    	KeyType key;
    }DataType;

## 一、直接插入排序 ##

> 基本思想是：  
> 1）将待排序的记录Ri+1，插入到已排好序的记录表R0, R1 ,…., Ri中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。  
> 2）设待排序的记录顺序存放在数组R\[0…n\]中，在排序的某一时刻，将记录序列分成两部分：  
> R\[0…i\]：已排好序的有序部分；  
> R\[i+1…n\]：未排好序的无序部分。  
> 显然，在刚开始排序时，R\[0\]是已经排好序的。

### 直接插入排序过程 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70]

### 算法如下： ###

void InsertSort (DataType a[], int n)
    //用直接插入法对a[0]--a[n-1]排序
    {
        
    	int i, j;
    	DataType temp;
    	for(i=0;  i<n-1; i++)
    	{
        
    		temp = a[i+1];//先暂存ai+1
    		j = i;
    		//已排好序的部分，大于ai+1的元素依次后移一个位置		
    		while(j > -1 && temp.key <a[j].key)
    		{
        
    			a[j+1] = a[j];
    			j--;
    		}
    		a[j+1] = temp;
    	}
    }

## 二、希尔(shell)排序(又称缩小增量排序) ##

> 基本思想：  
> 先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，  
> 待整个序列中的记录“基本有序”时，  
> 再对全体记录进行一次直接插入排序

> 具体算法：  
> ① 先取一个正整数d1(d1<n)作为第一个增量，将全部n个记录分成d1组，把所有相隔d1的记录放在一组中，即对于每个k(k=0,1, … d1-1)，R\[k\], R\[d1+k\], R\[2d1+k\] , …分在同一组中，在各组内进行直接插入排序。这样一次分组和排序过程称为一趟希尔排序；  
> ② 取新的增量d2<d1，重复①的分组和排序操作；直至所取的增量di=1为止，即所有记录放进一个组中排序为止。

### 希尔排序的排序过程如下： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 1]

### 算法如下： ###

void ShellSort (DataType a[], int n, int d[], int numOfD)
    //用希尔排序法对元素a[0]--a[n-1]排序，d[0]--d[numOfD-1]为希尔增量值
    {
        		
    	int i, j, k, m, span;
    	DataType temp;
    
    	for(m = 0; m < numOfD; m++)	       //共numOfD次循环
    	{
        	
    		span = d[m];		      //取本次的增量值
    		for(k = 0; k < span; k++)	      //共span个小组
    		{
        
    	//组内是直接插入排序，区别是每次不是增1而是增span
    			for(i = k; i < n; i = i+span)						
    			{
        	
    				temp = a[i+span];
    				j = i;
    				while(j > -1 && temp.key <= a[j].key)
    				{
        	
    					a[j+span] = a[j];
    					j = j-span;
    				}
    				a[j+span] = temp;
    			}
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210622145349937.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210622145643542.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTA4NDk4Ng==,size_16,color_FFFFFF,t_70