数据结构插入排序（InsertionSort Sort）详解附C++代码实现：

客官°小女子只卖身不卖艺 2024-02-19 18:11 48阅读 0赞

**目录**

简介：

算法描述：

代码实现：

总结：

--------------------

## 简介： ##

是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

时间复杂度为o(n^2),是一种稳定的排序算法，比较类排序算法

## 算法描述： ##

*  从第一个元素开始，该元素可以认为已经被排序；
 *  取出下一个元素，在已经排序的元素序列中从后向前扫描；
 *  如果该元素（已排序）大于新元素，将该元素移到下一位置；
 *  重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
 *  将新元素插入到该位置后；
 *  重复步骤2~5。

![849589-20171015225645277-1151100000.gif][]

## 代码实现： ##

#include<iostream>
    #include<time.h>
    #include<stdlib.h>
    using namespace std;
    #define range 10000
    void myrandom(int a[],int len)
    {
    	srand((unsigned)  time(NULL));
    	for(int i=0;i<len;i++)
    	a[i]=rand()%range+1;
    }
    void InsertionSort(int a[],int len)
    {
    	int k,current;
    	for(int i=1;i<len;i++)
    	{
    		k=a[i];
    		current=i-1;
    		for(;current>=0&&a[current]>k;current--)
    		{
    			a[current+1]=a[current];
    		}
    		a[current+1]=k;
    	}
    }
    int main()
    {
    	clock_t start,end;
    	start=clock();
    	freopen("out.txt","r",stdin);
    	freopen("out插入排序.txt","w",stdout);
    	int arr[range];
    	int n=range;
    	myrandom(arr,n);
    	InsertionSort(arr,n);
    	for(int i=0;i<n;i++)
    	{
    		printf("%5d ",arr[i]);
    	}
    	cout<<endl;
    	end=clock();
    	cout<<"插入排序共计用时："<<(float)(end-start)*1000.0/CLOCKS_PER_SEC<<"ms"<<endl; 
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70][]

## 总结： ##

时间复杂度分析：

最好：o(n),最坏：o(n^2)

平均：o(n^2)

稳定类算法。

小伙伴们，如果还看不懂，在评论区留言，乐意解答。

（上学期我老师的一句话：一个人自己懂了，不见的是真懂，只有给别人讲明白了，才算真的懂。ps：我老师是菊厂毕业的O(∩\_∩)O哈哈~）

[849589-20171015225645277-1151100000.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/348786fc16264bf9a5caa9f651b7f9d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/f43d504d41c046c68af35782582b2718.png