做一件是之前我们总是要先知道我们做这件的核心思想，这样会让我们做事的效率得到有效的提高；现在我们来看看插入排序算法的实现思路：直接插入排序就是把待排序的记录按其关键码值的大小逐个插入到一个已经有序的序列中，指导所有的记录插入完为止，得到的一个新的有序队列。这就和我们现实生活中打扑克拍抓牌的时候是一样的，当我们拿到一张新的扑克牌的时候，会把它和我们手里已经拍好序的扑克做比较，找到它应该放在那里。
于是我们就可以写出下面的代码：
void InsertSort(int *arr, int left, int right)
{
for (int i = left + 1; i < right; i++)
{
int end = i;
while (end > left && arr[end] < arr[end - 1])
{
swap(arr[end], arr[end - 1]);
end--;
}
}
}
但是如果我们调用swap函数的话，效率是比较低的，于是我们想到可以用一个中间变量temp来实现；使用中间变量的思想是把当前要插入的数据（未排序的数据）赋值给temp，然后寻找该变量适合插入的位置，之后把元素向后移动一位，把temp插入该位置。
上面这张图，一开始temp的值为9，前一位数为8，也就是说前两位为有序数字，不用排序，后面我们以2为例子，向大家展示了把2排序的过程，当2排序完成后，3也重复了2的操作，一直到最后使得整个数组有序。
void InsertSort1(int *arr, int left, int right)
{
for (int i = left + 1; i < right; i++)
{
int temp = arr[i];
int end = i;
while (end > left && temp < arr[end - 1])
{
arr[end] = arr[end - 1];
end--;
}
arr[end] = temp;
}
}
我们注意到上面的代码都有end > left这个条件，这样做的原因是为了避免数组下标越界，那么我们可不可以不用这各条件又能避免数组越界呢。我们使用的方法是引入“哨兵”，说通俗一点就是在需要排序的元素中多添加一个元素，它也充当上面中间变量的角色，所以最后是不参与排序的。注意到当最后
void InsertSort2(int *arr, int left, int right)
{
for (int i = left + 1; i < right; i++)
{
arr[0] = arr[i];
int end = i;
while (arr[0] < arr[end-1])
{
arr[end] = arr[end - 1];
end--;
}
arr[end] = arr[0];
}
}
使用插入排序的过程中我们发现它有一个查找插入位置的步骤，而之前我们又学习过二分查找，当我们把二分查找和插入排序结合的时候，这就是二分插入排序。
void BinInsertSort(int *arr, int left, int right)
{
for (int i = left + 1; i < right; ++i)
{
int temp = arr[i];
int low = 0;
int heigh = i - 1;
while (low <= heigh)
{
int m = (low + heigh) / 2;
if (temp < arr[m])
{
heigh = m - 1;
}
else
{
low = m + 1;
}
}
for (int j = i - 1; j >= heigh + 1; j--)
{
arr[j + 1] = arr[j];
}
arr[heigh + 1] = temp;
}
}
commit.h
#pragma once
#include <time.h>
#include <iostream>
using namespace std;
sort.h
#pragma once
#include "commit.h"
//直接插入排序
void InsertSort(int *arr, int left, int right);
//改进版的插入排序算法
void InsertSort1(int *arr, int left, int right);
//带哨兵位的插入排序算法
void InsertSort2(int *arr, int left, int right);
//二分插入排序
void BinInsertSort(int *arr, int left, int right);
void Print(int *arr, int left, int right);
//测试效率
void testEfficiency();
void InsertSort(int *arr, int left, int right)
{
for (int i = left + 1; i < right; i++)
{
int end = i;
while (end > left && arr[end] < arr[end - 1])
{
swap(arr[end], arr[end - 1]);
end--;
}
}
}
//改进版的插入排序算法
void InsertSort1(int *arr, int left, int right)
{
for (int i = left + 1; i < right; i++)
{
int temp = arr[i];
int end = i;
while (end > left && temp < arr[end - 1])
{
arr[end] = arr[end - 1];
end--;
}
arr[end] = temp;
}
}
//带哨兵位的插入排序算法
void InsertSort2(int *arr, int left, int right)
{
for (int i = left + 1; i < right; i++)
{
arr[0] = arr[i];
int end = i;
while (arr[0] < arr[end-1])
{
arr[end] = arr[end - 1];
end--;
}
arr[end] = arr[0];
}
}
//二分插入排序
void BinInsertSort(int *arr, int left, int right)
{
for (int i = left + 1; i < right; ++i)
{
int temp = arr[i];
int low = 0;
int heigh = i - 1;
while (low <= heigh)
{
int m = (low + heigh) / 2;
if (temp < arr[m])
{
heigh = m - 1;
}
else
{
low = m + 1;
}
}
for (int j = i - 1; j >= heigh + 1; j--)
{
arr[j + 1] = arr[j];
}
arr[heigh + 1] = temp;
}
}
//打印排序好的数组，传入起始位置和末尾位置
void Print(int *arr,int left,int right)
{
for (int i = left; i < right; i++)
{
cout << arr[i] << ' ';
}
cout << endl;
}
void testEfficiency()
{
int n = 50000;
int *a = (int *)malloc(sizeof(int)*n);
int *a1 = (int *)malloc(sizeof(int)*n);
int *a2 = (int *)malloc(sizeof(int)*n);
int *a3 = (int *)malloc(sizeof(int)*n);
srand(time(0));
for (int i = 0; i < n; i++)
{
a[i] = rand();
a1[i] = a[i];
a2[i] = a[i];
a3[i] = a[i];
}
time_t start = clock();
InsertSort(a, 0, n);
time_t end = clock();
cout << "InsertSort:" << end - start << endl;
start = clock();
InsertSort1(a1, 0, n);
end = clock();
cout << "InsertSort1:" << end - start << endl;
start = clock();
InsertSort2(a2, 0, n);
end = clock();
cout << "InsertSort2:" << end - start << endl;
start = clock();
BinInsertSort(a3, 0, n);
end = clock();
cout << "BinInsertSort:" << end - start << endl;
}
sort.cpp
#include "sort.h"
int main()
{
int arr[] = { 8, 9, 2, 7, 3, 52, 46, 82 };
int len = sizeof(arr) / sizeof(arr[0]);
InsertSort(arr, 0, len);
cout << "插入排序后的结果：";
Print(arr, 0, len);
InsertSort1(arr, 0, len);
cout << "改进插入排序后的结果：";
Print(arr, 0, len);
BinInsertSort(arr, 0, len);
cout << "二分插入排序后的结果：";
Print(arr, 0, len);
int arr1[] = { 0, 8, 9, 2, 7, 3, 52, 46, 82 };
len = sizeof(arr1) / sizeof(arr1[0]);
InsertSort2(arr1, 1, len);
cout << "带哨兵位的插入排序后的结果：";
Print(arr1, 1, len);
testEfficiency();
system("pause");
return 0;
}