插入排序相当于对冒泡排序的改进，取消了挨个比较大小进行交换位置的过程，而是先挨个进行比较，找出适合的位置在进行插入，然后把元素进行前移或者后移操作，省去了交换的过程
#include<iostream>
using namespace std;
//插入排序
void insertSort(int arr[],int len)
{
//i一开始记录数组中第一个元素的位置
for (int i = 1; i < len; i )
{
int j = i - 1;//j记录i后面一个元素的位置
int temp = arr[i];//临时值，每次循环用来保存i记录的元素位置
//如果temp指向的元素大于j指向的元素，就不改变位置，因为从小到大排序
//如果temp指向的元素小于j指向的元素.
//temp拷贝的元素，就是j 1位置的元素
while (temp < arr[j])
{
//从j 1位置开始，把从j位置开始的数组后面元素都往前移动，每一次都与temp值比较，直到找到数组中某个位置j的元素值小于temp，就停止当前while循环，把temp值赋值给j 1位置的值，即J前面的位置的元素
arr[j 1] = arr[j];
//每一次j--是为了，让数组后面的元素都往前覆盖式的移动一次
j--;
}
//1.如果temp值即j 1的值比j的值大，就不移动
//2.通过while循环找到了temp值因该插入的地方
arr[j 1] = temp;
}
}
int main()
{
int arr[5] = { 2,1,3,5,4 };
insertSort(arr, 5);
for (int i = 0; i < 5; i )
{
cout << *(arr i) <<" ";
}
system("pause");
return 0;
}双重for循环写法
代码语言：javascript复制#include<iostream>
using namespace std;
void test(int arr[],int len,int low,int high)
{
int i, j, temp;
for ( i = 1; i < len; i )
{
temp = arr[i];
for ( j = i - 1; j >= 0&&temp<arr[j]; j--)
{
arr[j 1] = arr[j];
}
arr[j 1] = temp;
}
}
int main()
{
int arr[9] = { -1,20,1,2,3,4,4,10,12};
test(arr, 9, 0, 8);
for (int i = 0; i < 9; i )
cout << arr[i] << endl;
system("pause");
return 0;
}
插入排序在处理大数据排序时，复杂度为(n^2)
可以对插入排序进行优化，通过二分查找替代原有查找算法，降低循环次数
遍历无序区间的所有元素，每次取无序区间的第一个元素Array[i]，因为0到i-1是有序排列的，所以用中点m将其平分为两部分，然后将待排序数据同中间位置为m的数据进行比较，若待排序数据较大，则low到m-1分区的数据都比待排序数据小，反之，若待排序数据较小，则m 1~high分区的数据都比 待排序数据大，此时将low或high重新定义为新的合适分区的边界，对新的小分区重复上面操作。直到low和high 的前后顺序改变，此时high 1所处位置为待排序数据的合适位置。
时间复杂度：O(n^2)
稳定性：稳定。
代码语言：javascript复制#include<iostream>
using namespace std;
void test(int Array[], int len)
{
int i, j, x, m; /*i,j均为循环变量，x用来存储当前待排序的数据，m充当比较区间的中点*/
int low, high; /*low代表要与Array[i]进行比较的有序区间的第一个元素所在位置。
high代表要与Array[i]进行比较的有序区间的最后一个元素所在位置。*/
for (i = 1; i < len; i )
{
x = Array[i];
low = 0; /*第一次划分有序比较区间，比较区间的第一个元素所在位置为0*/
high = i - 1; /*第一次划分有序比较区间，比较区间的最后一个元素所在位置为n-1*/
/*比较查找Array[i]合适插入的位置*/
while (low <= high)
{
//要把每次给m的赋值放入while循环体内部，因为每一次循环都要更新mid的值
m = (low high) / 2;
if (x >= Array[m])
{
low = m 1;
}
else
{
high = m - 1;
}
}
//退出循环，此时high的位置指向要插入位置的前一个元素
/*确定好位置后，将位置之后的数据后移，插入待排序数据*/
for (j = i - 1; j > high; j--)
{
Array[j 1] = Array[j];
}
//经历过上面的循环，此时j的值指向要插入元素的前一个位置
//j 1的位置为从乱序数组中取出第一个元素，要放入到有序数组中的位置
Array[j 1] = x;
}
}
int main()
{
int arr[9] = { -1,20,1,2,3,4,4,10,12};
test(arr, 9);
for (int i = 0; i < 9; i )
cout << arr[i] << endl;
system("pause");
return 0;
}
