99-对直接插入排序算法的实现和分析

旧城等待， 2022-12-29 00:16 82阅读 0赞

***直接插入排序算法的思想***  
将待排序的数据序列分成两部分，左部分是已经排序好的序列，  
右部分是未排序的序列，  
初始排序时，左部分只有一个数据，剩下的数据都在右部分

一次直接插入：  
1.从右部分拿一个数据插到左部分，并且使左部分依旧有序  
2.循环此过程，直到右部分没有数据

首先先书写需要用到的辅助函数

#include<stdio.h>
    
    /*辅助函数：
        1.打印数据
    	2.判断整个数据序列是否已经有序
    	3.交互两个数据swap方法
    */
    
    void Show(int *arr,int len)//打印数据
    {
        
    	for(int i=0;i<len;++i)
    	{
        
    		printf("%d  ",arr[i]);
    	}
    	printf("\n");
    }
    
    bool IsSort(int *arr,int len)//判断整个数据序列是否已经有序
    {
        
    	for(int i=0;i<len-1;++i)
    	{
        
    		if(arr[i]>arr[i+1])
    		{
        
    			return false;
    		}
    	}
    	return true;
    }
    
    void SwapValue(int *a,int *b)//交互两个数据swap方法
    {
        
    	int tmp=*a;
    	*a=*b;
    	*b=tmp; 
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
**实现 直接插入排序算法的函数**

void InsertSort(int *arr,int len)
    {
        
    	for(int i=1;i<len;++i)//初始排序时，左部分只有一个数据，剩下的数据都在右部分
    	{
        
    		int tmp=arr[i];
    		int j=i;
    		for(;j>0&&arr[j-1]>tmp;--j)
    		{
        
    			arr[j]=arr[j-1];
    		}
    		arr[j]=tmp;
    	}
    }

完成主函数

int main()
    {
        
    	int arr[]={
        7,87,29,75,41,50,62,92,69,22,76,77,35};
    	Show(arr,sizeof(arr)/sizeof(arr[0]));
    	InsertSort(arr,sizeof(arr)/sizeof(arr[0]));
    	Show(arr,sizeof(arr)/sizeof(arr[0])); 
    	return 0;
    	
    }

运行截图如下  
![在这里插入图片描述][20201218132928808.png_pic_center]

***直接插入排序算法的分析***

时间复杂度：O(n^2) 最好情况–数据已经有序：O(n)  
直接插入排序数据越有序，时间复杂度越低  
空间复杂度：O(1)  
稳定性：稳定

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/f1fe93f845ff44f98645554c729d05e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/396f73fa08c943548b9a4aaf6be1a06d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/1df4cd4295a24ce6882e23b238b12a69.png
[20201218132928808.png_pic_center]: /images/20221120/f04ffca79b4d4e10b7cf4b79b1989e7a.png