插入算法

来源:互联网 时间:1970-01-01

插入学习算法是一种原地排序(sorted in place)的算法,亦即不用重新分配内存,在原数组或者vector中进行排序的。

其伪代码为

  1. 1 INSERTION-SORT(A)2 for j<-2 to length[A]3 do key<-A[j]4 //INSERT A[j] into the sorted sequence A[1..j-1]5 i<-j-16 while i>0 and A[i]>key7 do A[i+1]<-A[i]8 i<-i-19 A[i+1]<-key


    伪代码的好处在于看起来方便直观,而且在使用其他语言实现的时候也非常简单,是个非常好的表达自己思维的一种方式。

  2. 使用 数组的方式实现上述伪代码
#define SIZE 6//插入算法的数组引用实现方式void insertion_sort(int (&array)[ SIZE]){ int key; for(int j=1;j<SIZE;j++) { key=array[j]; int i=j-1; while(i>=0&&array[i]>key) { array[i+1]=array[i]; --i; } array[i+1]=key; }


   其中数组的引用作为形参的时候,必须固定数组大小,可以采用#define的形式。

3.采用vector的方式进行传参

void insert_sort(vector<int>&array) //当使用vector<int>array作为形参的时候, //不能改变原vector中对象的内容,{ //当使用容器的引用的时候,可以正常改变 //利用vector下标形式进行索引,同字符串和数组 int key; for(int j=1;j<array.size();j++) { key=array[j]; int i=j-1; while(i>=0&&array[i]>key) { array[i+1]=array[i]; --i; } array[i+1]=key; }}

这里面有个不匹配的,就是array.size()是unsigned int形式的,但是j是int类型的,两者比较的时候容易出现问题。如果将i,j定义为unsigned类型的话,while循环中,i=0的时候,--i,为无符号类型,所以i变成了232,于是array[i]就会溢出。如果一定要用unsigned int i,j的话,那么在主函数中要设置一个岗哨。岗哨设置在下面可以看到。

4.采用迭代器

void insertSort(vector<int>&array){ vector<int>::iterator it=array.begin()+1; for(it+=1;it!=array.end();++it) { int key=*it; vector<int>::iterator ita=it-1; while(ita>=array.begin()+1&&(*ita)>key) { *(ita+1)=*ita; --ita; } *(ita+1)=key; }}int main(){ vector<int> A; A.push_back(INT_MIN); //通过设置岗哨,可以让程序继续运行下去。 A.push_back(5); A.push_back(2); A.push_back(4); A.push_back(3); A.push_back(1); A.push_back(6); //insert_sort(A); insertSort(A); vector<int>::iterator it=A.begin()+1; while(it!=A.end()) { cout<<*it<<"/t"; ++it; } }

 



相关阅读:
Top