您的位置: 首页  >  文章  >  八大排序———插入排序（及优化）

八大排序———插入排序（及优化）

分类: 文章 • 2024-01-06 10:19:04

一：直接插入排序的原理

  有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数据，插入后使该数据序列仍然有序。

算法适用于少量的数据排序，时间复杂度为O(n^2)，是稳定的排序算法。

   关键码：是数据元素中某个数据项的值，用于标识一个数据。例如：一个学生的信息就是一条记录，它包括学号，姓名，性别等，学号是关键码。

        稳定性：若待排序的记录中，存在两个或两个以上的关键码相同的记录，经排序后这些记录的相对次序不会改变，那么则称该排序是稳定的排序算法。

         算法思路：

         ①设置监视哨r[0]，将待插入的记录的值赋给r[0]即可；

         ②设置开始查找的位置j

         ③在数组中进行搜索，若不符合条件则前移，直至r[0].key>=r[j].key为止

         ④将r[0]插入r[j+1]的位置

八大排序———插入排序（及优化）

 

二：代码分析

  

#include<iostream>
using namespace std;

template<typename T>
void dir_ins_sort(T arr[],int len)
{

    int i = 1;
    int j = 0;
    T tmp = T();

    while(i<len)
    {    
        j = i -1;
        tmp = arr[i];    
        while(j>0 && arr[j] > tmp)
        {
            --j;
            arr[j+1] = arr[j];
        }

        arr[j+1] = tmp;
        ++i;
    }
}

三：时间复杂度

  观察代码我们可以知道，外层循环i是（len -1）,内层是要比较len*（len-1）/2,所以时间复杂度为O(n^2),

空间复杂度为O(n)。

四：算法稳定性 

是一种稳定的算法。

五：直接插入排序的优化

将待排序的那个数据元素插入到有序列中时，这个序列已经是有序的，我们是将待排序元素逐个和前面的元素比较，直至找到小于等于这个带排序元素的，然后插入。既然这个序列已经是有序的那么我们查找的时间可不可以用二分查找呢！显然是可以的，这也就是二分直接插入排序算法。

二分法插入排序是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

六：二分插入代码

#include<iostream>
using namespace std;
template<typename T>
int bin_ch(int start,int end,T tmp,T arr[])//二分查找
{
		int mid = (start + end)/2;
		while(end - start > 1)
		{
				if(tmp == arr[mid])return mid+1;
				else if(tmp > arr[mid])
				{
						start = mid;
						return bin_ch(start,end,tmp,arr);
				}
				else if(tmp < arr[mid])
				{
						end = mid ;
						return bin_ch(start,end,tmp,arr);
				}
		}
		if(end - start == 1)return end;
}
template<typename T>
void pri_i_s_sort(T arr[],int len)
{
		int i = 1;//len-1次插入
		int j = 0;
		int pos = 0;
		T tmp = T();//临时存储
		while(i<len)//1   -     len-1
		{
				tmp = arr[i];
				j = i-1;//有序部分的最大的。
				if(tmp <= arr[0])//第一个元素
				{
						for(j;j>-1;--j)
						{
								arr[j+1] = arr[j];
						}
						++i;
						arr[0] = tmp;
						continue;
				}
				if(tmp>=arr[j])//最后一个元素
				{
						++i;
						continue;
				}
				pos =  bin_ch(0,j,tmp,arr);//获取插入位置

				//pos -j后移动
				for(j;j>pos-1;--j)
				{
						arr[j+1]=arr[j];
				}
				arr[pos] = tmp;
				++i;
		}
}
int main()
{
		int arr[] = {12,48,49,99,48,6,85,19,13};
		int len = sizeof(arr)/sizeof(arr[0]);
		pri_i_s_sort(arr,len);
		for(int i=0;i<len;++i)
		{
				cout<<arr[i]<<" ";
		}
		cout<<endl;
}

时间复杂度为O(n^2),空间复杂度为O(1),是稳定排序。

相关推荐