插入算法

插入排序 ​ 编辑词条 摘要 概述　　有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为⊙(㎡)。是稳定的排序方法。 　　插入算法（insertion sort）把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。 编辑摘要 目录-[ 隐藏 ] 1.​ 1插入排序 2.​ 2基本思想 3.​ 3算法步骤 4.​ 4算法思路 5.​ 5算法描述 6.​ 6示例代码 7.​ 7算法复杂度 编辑本段|回到顶部插入排序 　　包括：直接插入排序，折半插入排序，链插入排序，Shell排序 编辑本段|回到顶部基本思想 　　将n个元素的数列分为已有序和无序两个部分，如下所示： 　　{，{a2，a3，a4，…,an}} 　　{{a1(1)，a2(1)}，{a3(1)，a4(1) …,an(1)}} 　　… 　　{{a1(n-1)，a2(n-1) ，…}, {an(n-1)}} 　　每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。 编辑本段|回到顶部算法步骤 　　1.从有序数列和无序数列{a2,a3,…,an}开始进行排序； 　　2.处理第i个元素时(i=2,3,…,n) , 数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的。用ai与ai-1，a i-2,…,a1进行比较,找出合适的位置将ai插入； 　　3.重复第二步，共进行n-1次插入处理，数列全部有序。 　　void insertSort(Type* arr,long len)/*InsertSort algorithm*/ 　　{ 　　long i=0,j=0;/*iterator value*/ 　　Type tmpData; 　　assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n"); 　　for(i=1;i 0 && tmpData < arr[j-1]) 　　{ 　　arr[j]=arr[j-1]; 　　j--; 　　} 　　arr[j]=tmpData; 　　} 　　} 编辑本段|回到顶部算法思路 　　假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a[1…k]是局部有序的,保证了插入过程的正确性. 编辑本段|回到顶部算法描述 　　一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下： 　　1. 从第一个元素开始，该元素可以认为已经被排序 　　2. 取出下一个元素，在已经排序的元素序列中从后向前扫描 　　3. 如果该元素（已排序）大于新元素，将该元素移到下一位置 　　4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 　　5. 将新元素插入到该位置中 　　6. 重复步骤2 　　如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。 编辑本段|回到顶部示例代码 　　示例代码为C语言，输入参数中，需要排序的数组为array[],起始索引为first，终止索引为last。示例代码的函数采用in-place排序，调用完成后，array[]中从first到last处于升序排列。 　　void insertion_sort(char array[], unsigned int first, unsigned int last) 　　{ 　　int i,j; 　　int temp; 　　for (i = first+1; i<=last;i++) 　　{ 　　temp = array; 　　j=i-1; 　　//与已排序的数逐一比较, 大于temp时, 该数移后 　　while((j>=first) && (array[j] > temp)) 　　{ 　　array[j+1] = array[j]; 　　j--; 　　} 　　array[j+1] = temp; 　　} 　　} 　　这个更好: 　　void InsertSort(char array[],unsigned int n) 　　{ 　　int i,j; 　　int temp; 　　for(i=1;i0 && temp < array[j-1] ; j--)//compare the new array with temp 　　{ 　　array[j]=array[j-1];//all larger elements are moved one pot to the right 　　} 　　array[j]=temp; 　　} 　　} 　　这个是c++语言版本的插入排序。为了支持list使用了std::advance()。 　　#include 　　template 　　void insertion_sort(biIter begin, biIter end) 　　{ 　　typedef typename std::iterator_traits::value_type value_type; 　　biIter bond = begin; 　　std::advance(bond, 1); 　　for(; bond!=end; std::advance(bond, 1)) { 　　value_type key = *bond; 　　biIter ins = bond; 　　biIter pre = ins; 　　std::advance(pre, -1); 　　while(ins!=begin && *pre>key) { 　　*ins = *pre; 　　std::advance(ins, -1); 　　std::advance(pre, -1); 　　} 　　*ins = key; 　　} 　　} 　　这是C#版，完整的代码，采用产生随机数，然后在利用插入排序重新排列。语言方式与C以及C++都有所不同，方法都是产用类的形式来表达。 　　class Program 　　{ 　　class Carry 　　{ 　　private int[] arr; 　　private int numitems; 　　private int upper; 　　public Carry (int size) //构建数组 　　{ 　　arr = new int[size]; 　　upper = size - 1; 　　numitems = 0; ; 　　} 　　public void insert(int items)//向数组中添加数据 　　{ 　　for (int i = 0; i < upper ; i++) 　　arr[numitems] = items; 　　numitems++; 　　} 　　public void display()//打印数组 　　{ 　　for (int i = 0; i < upper; i++) 　　Console.Write(arr[i]+" "); 　　} 　　public void insert sort()//插入排序 　　{ 　　for (int outer = 1; outer <= upper; outer++) 　　{ 　　int temp=arr[outer]; 　　int inner = outer ; 　　while(inner>0&&(int)arr[inner-1] >= temp) 　　{ 　　arr[inner] = arr[inner - 1]; 　　inner --; 　　} 　　arr[inner] = temp; 　　} 　　} 　　} 　　static void Main(string[] args) 　　{ 　　Carry arry = new Carry(10);//初始化一个10个数据元素的数组 　　Random rnd = new Random(100);//在1到100中随机产生10个数作为数组成员 　　for (int i = 0; i < 10; i++) 　　{ 　　arry.insert(rnd.Next (0,100)); 　　} 　　arry.insertsort ();//调用插入排序 　　arry.display();//打印数组 　　Console.ReadKey(); 　　} 　　} 　　这个是pascal语言版本的插入排序。 　　Procedure InsertSort(Var R : FileType); 　　//对R[1..N]按递增序进行插入排序, R[0]是监视哨// 　　Begin 　　for I := 2 To N Do //依次插入R[2],...,R[n]// 　　begin 　　R[0] := R[I]; J := I - 1; 　　While R[0] < R[J] Do //查找R[I]的插入位置// 　　begin 　　R[J+1] := R[J]; //将大于R[I]的元素后移// 　　J := J - 1 　　end 　　R[J + 1] := R[0] ; //插入R[I] // 　　end 　　End; //InsertSort // 编辑本段|回到顶部算法复杂度 　　如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法复杂度为O(n2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。 ​ 编辑词条