插入排序的思想与达成InsertSort
发布时间：2021-11-20 17:33:33 所属栏目：教程 来源：互联网
导读：简单来说，插入排序的思想是将待排序数列（这里用数组表示）分为已排好序和未排好序的两部分，一般将前面先排有序，例如：a[0]...a[i]已经有序，剩下的任务就是将a[i+1]...依次插入到前面有序的数列中，并同时使前面的序列仍然有序。 插入排序的开销主要在：
|
简单来说，插入排序的思想是将待排序数列（这里用数组表示）分为已排好序和未排好序的两部分，一般将前面先排有序，例如：a[0]...a[i]已经有序，剩下的任务就是将a[i+1]...依次插入到前面有序的数列中，并同时使前面的序列仍然有序。 插入排序的开销主要在：找待插入的位置。最坏的情况是原序列是逆序的，每次都要找到最前，开销是 1+2+3+...n-1=n*(n-1)/2,故时间复杂度是O(n*n). 在插入的过程中还需要平移前面的数列。但是这个时间开销是伴随寻找插入位置同时进行的。下面是一段代码，包含测试代码，可直接运行。 #include "stdafx.h" #include"iostream" using namespace std; int* insertsort(int a[],int m); int _tmain(int argc, _TCHAR* argv[]) { int a[5]={1,3,4,2,0}; cout<<"Please input five numbers:"<<endl; for(int i=0;i<5;i++) { cin>>a[i]; } int *c=insertsort(a,5); for(int i=0;i<5;i++) cout<<*(c+i)<<endl; cout<<"finished input"; return 0; } int* insertsort(int a[],int m) { for(int i=0;i<m-1;i++) // i从0开始到i-1,j从i+1开始，到m { int j=i+1; //从i后面的第一个元素开始一次向前进行比较 int temp=a[j];//这一步是为了保存a[j]的值以便之后进行交换，否则有可能会被a[i]覆盖 while(i>=0&&temp<a[i]) { a[i+1]=a[i]; //否的话因为需要将a[i]往后移位 i--;//继续往前比较 } ///退出循环要么是找到了比a[j]小的a[i],那么从这个i+1到j-1的位置均后移了，所以要将temp赋值给a[i+1]; //第二种情况是i已经减小到-1,所以将temp直接插到a[0] a[i+1]=temp; } return a; }  （编辑：江门站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
