【排序】----插入排序
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.问题及改进
插入排序是将一个一个的元素单独进行插入，效率较慢，可以考虑把一个有序的序列直接插入到数组中，这样速度就比较快了。也就是希尔排序的思想。