排序算法1之插入排序

本文主要是介绍排序算法1之插入排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

插入排序

排序算法作为互联网找工作的必考的问题，现在得补补了。之前对排序算法有一些了解，有些排序算法看起来比较简单，但是真要自己手写code也不是那么容易的。所以纸上得来终觉浅，绝知此事要躬行。

算法的三个特性

时间效率，一般情况，当然希望排序算法越快越好。一般排序算法能达到 $\Omega(n)$ 的时间复杂度就已经非常好了。
空间效率，受限于计算机的硬件条件，加上大数据处理问题日渐普及，排序算法考虑算法的内存需要是必须的。In-place sort是指不占用额外的内存或者占用的额外内存是常数，与排序数据大小无关。
稳定与否，也即经常看到的stable sort或者unstable sort。这个稳定是指，排序完成后，相等项目是否保持着原本相对的位置。

插入排序
原理：
每次将一个待排序的项目，按照关键字的大小插入前面已经排序好的子序列中，直至整个数组排序完成。时间复杂度 $\Omega(n^2)$ ，空间复杂度 $\Omega(n)$ 。插入排序由两部分组成：

寻找插入位置
插入待排序的项目

按照寻找插入位置方法的不同，又可以细化为：

线性插入排序
二分插入排序
希尔排序

线性插入排序

#include<iostream>
using namespace std;
void InsertSort(int* p,int length)
{int pos=0;//待插入位置,默认情况就直接插在最前面for(int i=1;i<length;i++){for(int j=i-1;j>=0;j--){if(p[j]<=p[i]){pos=j+1;break;}}//完成第一步的查找插入位置int tmp=p[i];for(int j=i-1;j>=pos;j--)p[j+1]=p[j];p[pos]=tmp;//完成第二步的插入待排序项目}
}
int main()
{int data[10]={5,4,3,2,1,1,6,3,10,11};InsertSort(data,10);for(int i=0;i<10;i++)cout<<"第"<<(i+1)<<"个数是"<<data[i]<<endl;return 0;
}

上面的代码可以进行优化，将查找待插入位置和插入待排序项目合并在一起。因为如果待插入元素小于其左边的元素，那么就需要将待插入元素向左移；相反如果待插入元素大于其左边的元素，那么也就大于左边已经排列好的序列，也就是说待插入元素已经处于正确的位置。两种代码的时间复杂度和空间复杂度是一样的，只是下面的code更加简化。

void swap(int& a,int& b)
{int tmp=a;a=b;b=tmp;
}
void InsertSort(int* p,int length)
{for(int i=1;i<length;i++)for(int j=i-1;j>=0&&p[j+1]<p[j];j--)swap(p[j+1],p[j]);
}

二分插入排序法
个人感觉二分插入排序法是不稳定的排序算法。

#include<iostream>
using namespace std;
int FindPos(int* p,int startPos,int endPos,int num)
{int index=0;while(startPos<=endPos){index=(startPos+endPos)/2;if(p[index]<num)startPos=index+1;elseendPos=index-1;}return startPos;
}
void InsertSort(int* p,int length)
{int pos=0;//待插入位置,默认情况就直接插在最前面for(int i=1;i<length;i++){pos=FindPos(p,0,i-1,p[i]);//完成第一步的查找插入位置int tmp=p[i];for(int j=i-1;j>=pos;j--)p[j+1]=p[j];p[pos]=tmp;//完成第二步的插入待排序项目}
}
int main()
{int data[10]={5,4,3,2,1,1,1,3,10,11};InsertSort(data,10);for(int i=0;i<10;i++)cout<<"第"<<(i+1)<<"个数是"<<data[i]<<endl;return 0;
}

希尔排序算法
希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。实验证明希尔排序的时间复杂度为 $\Omega(n^{3/2})$
基本思想：
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

#include<iostream>
using namespace std;void swap(int& a,int& b)
{int tmp=a;a=b;b=tmp;
}
void HillInsert(int* p,int length)
{for(int gap=length/2;gap>0;gap=gap/2)//分组排序的次数for(int i=0;i<gap;i++)//每次需要进行几组排序for(int j=i+gap;j<length;j+=gap)//对每组进行直接排序for(int k=j;k>=0&&p[k]<p[k-gap];k-=gap)swap(p[k],p[k-gap]);}
int main()
{int data[10]={5,4,3,2,1,1,1,3,10,11};HillInsert(data,10);for(int i=0;i<10;i++)cout<<"第"<<(i+1)<<"个数是"<<data[i]<<endl;return 0;
}