1.基本思想
在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。
2.过程
·(1)从第一个元素开始,该元素可以认为已经被排序;
·(2)取出下一个元素,在已经排序的元素序列中从后向前扫描;
·(3)如果该元素(已排序)大于新元素,将该元素移到下一位置;
·(4)重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
·(5)将新元素插入到该位置后;
·(6)重复步骤2~5。
动图演示:
3.参考代码
#include<iostream> using namespace std; int main() { int arr[]= {12,45,13,88,79,11,52,66}; //定义数组 int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度 int cur,i,j; for(i =1; i<len;i++) { cur = arr[i]; //待排序元素 for(j=i-1;j>=0 && arr[j]>cur;j--) { arr[j+1]=arr[j]; } arr[j+1]=cur; //将待排序元素插入数组中 /* for(int i=0;i<len;i++) cout<<arr[i]<<" "; cout<<endl; */ } return 0; }
第二种写法
#include<iostream> using namespace std; int main() { int arr[]={12,45,13,88,79,11,52,66}; //定义数组 int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度 int i,j,k; for (i =0; i < len; i++) { /*1目的是为arr[i]找到合适的位置*/ for (j=i-1; j >= 0; j--) // 在前面有序区间中为a[i]找合适的插入位置 if (arr[j] <= arr[i]) //找到比a[i]小的位置就退出,插入其后 break; /*2 判断是否找到合适位置*/ if (j != i - 1) { int temp = arr[i]; //将比temp大的数据往后移动 for (k = i-1; k > j ; k--) arr[k+1] = arr[k]; //将arr[i]放到合适的位置 arr[k+1] = temp; } /* for(int i=0;i<len;i++) cout<<arr[i]<<" "; cout<<endl; */ } return 0; }
其他写法:
#include<iostream> using namespace std; int main() { int arr[]= {12,45,13,88,79,11,52,66}; //定义数组 int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度 for(int i=1; i<len; i++) { //从第2个元素开始遍历 int temp=arr[i];//将当前位置的元素取出 int j; for(j=i; j>0; j--) { if(temp<arr[j-1]) {//如果这个元素比temp大就覆盖,否则就证明该元素之前已经有序就break arr[j]=arr[j-1];//直接用前一个元素进行覆盖 } else { break; } } //将temp中的元素插入合适位置 arr[j]=temp; /* for(int i=0;i<len;i++) cout<<arr[i]<<" "; cout<<endl; */ } }
#include<iostream> using namespace std; int main() { int arr[]={12,45,13,88,79,11,52,66}; //定义数组 int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度 for(int i=1;i<len;i++){ //遍历无序部分, int tmp=arr[i],j=i-1; //j为当前下标,tmp为无序部分第一个元素 while(j>=0&&tmp<arr[j]){ //找到k元素在有序部分的位置 arr[j+1]=arr[j]; //循环的时候直接右移有序数组,为tmp空出位置 j--; //不是tmp正确位置,继续循环往前 } arr[j+1]=tmp; //出来的时候j多减1,要加回去 /* for(int i=0;i<len;i++) cout<<arr[i]<<" "; cout<<endl; */ } }
4.问题及改进
插入排序是将一个一个的元素单独进行插入,效率较慢,可以考虑把一个有序的序列直接插入到数组中,这样速度就比较快了。也就是希尔排序的思想。
返回目录:算法