插入排序（Insertion sort）是一种简单直观且稳定的排序算法，时间复杂度O(n^2)。对于近乎有序的数组，是比较快的。算法思想：将一个数据插入到已经排好序的有序数据中合适的位置中，直到全部插完为止。类似我们在玩扑克牌的时候，发到手里的牌，我们按照一张一张插入到合适的位置。
一. c语言版
【原版1】
//插入排序
/*
插入一个数都要将它和之前的已经完成排序的序列进行重新排序，
也就是要找到新插入的数对应原序列中的位置。
那么也就是说，每次插入一个数都要对原来排序好的那部分序列进行重新的排序。
整体思路：
a. 默认第一个数arr[0]是有序的，剩下的arr[len-2]区域是无序的
b. 每次从无序区域取出一个元素，插入前面已经排好序的区域中，合适的位置
8 6 2 =>一开始我们假设8是有序的
=>插入6元素，发现6比前一个元素小，交换位置6 8 2 ，6继续向比较已经到头，小循环结束
=>插入2元素，发现2比前面的8要小，交换位置6 2 8, 2继续向前比较小于6，交换位置2 6 8 小循环结束
=>然后整体循环结束，整个数组有序2 6 8
*/
void InsertSort1(int *arr,int n)
{
int i,j;
//假设第一个元素是有序的
for(i=1; i<n; i++){
for(j = i;j>0;j--){
if(arr[j] < arr[j-1]){//判断是否与前一个元素小
swap(&arr[j],&arr[j-1]);//如果小于就交换
}else{//如果大于或者等于，就不用再向前循环，因为前面已经是有序的
break;//跳出循环
}
}
}
}【直接插入排序】
/*
优化
【直接插入排序】向左比较
由于之前的插入，每次如果小的话，都需要进行交换位置，也是比较耗时，所以我们这次先确定位置
8 6 2
一开始8是有序的
=>8
现在开始插入6 先让elem = 6 复制了一份，
然后向前寻找到elem合适的位置，由于8比6还要大，8向后移动赋值一位 =>8 8，然后再向左到头了，找到位置
然后插入(赋值) 6
=> 6 8
现在开始插入2 elem = 2 复制了一份
然后向左移动， 8>2,然后把8向后移动一为6 8 8 然后与之前的元素比较6>2 然后把6向后移动一位6 6 8
然后到头了，找到合适位置，然后赋值为2 变成2 6 8
=>2 6 8
简化一下说明：
[1]默认第一个元素是有序的，arr[0]
[2]取下一个元素记作elem，向前已经排好序的元素序列中，也就是向数组左边的比较。
[3]如果该元素大于elem新的要插入的元素，就向后移动到下一个元素。
[4]然后重复步骤3，直到找到已排序的元素小于或者等于新的元素的位置。
[5]就插入到该位置后面，由于等于的元素不会交换相对位置，所以排序是稳定的。
[6]重复2~5
*/
void InsertSort2(int *arr,int n)
{
int i,j;
//假设第一个元素是有序的
for(i=1; i<n; i++){
int elem = arr[i];
for(j = i;j>0 && elem <arr[j-1] ;j--){ //看一下当前elem的值 要比前面的值小，那么就不应该放到这里
arr[j] = arr[j-1];//那么j就不是我们要找的，向后移动一个元素
}
arr[j] = elem;//j就是我们要找的合适的位置
}
}【二分折半插入排序】
/*
折半插入（Binary Insert Sort）和直接插入类似
唯一的区别就是在有序列表中比较查找插入位置时用的是二分法。
因为前面部分是有序列表，所以是最理想的二分法。
*/
void InsertSort3(int *arr, int len)
{
int left,right,mid;
int elem;
int i,j;
for(i=1;i<len;i++){
right = i-1;
left = 0;
//二分获取插入位置
while(left<=right){
mid = (left+right)/2;
if(arr[mid] > arr[i]){
right = mid - 1;
}else{
left = mid + 1;
}
}
//得到位置，其他元素后移， 直接插入
elem = arr[i];
for(j=i;j>right+1;j--){
arr[j] = arr[j-1];
}
arr[right+1] = elem;
}
}
【完整代码】
#include<stdio.h>
#include<string.h>
#include<time.h>
#define MAX 100000
void InsertSort1(int *arr,int n);//插入排序 ，每次后面小的话，都要交换位置
void InsertSort2(int *arr,int n);//优化，先确定位赋值 ，减少交换次数
void InsertSort3(int *arr,int n);//折半查找法
void getRandArray(int *arr,int n,int Range); //随机生成一个长度为n一维数组 随机数的范围在[0 Range)
void getNearRandArray(int *arr,int n,int times);//随机生成一个部分有序的数组 长度为n 无序交换次数
void swap(int *a,int *b); //交换两个变量
void dump(int arr[],int n); //打印
int main()
{
clock_t begin , end;
double time;
int arr1[MAX],arr2[MAX],arr3[MAX];
getRandArray(arr1,MAX,100);
//getNearRandArray(arr1,MAX,5);
memcpy(arr2,arr1,sizeof(arr1));//拷贝
memcpy(arr3,arr1,sizeof(arr1));
begin = clock();//开始记录
InsertSort1(arr1,MAX);
end = clock(); //结束记录
time = (double)(end - begin)/CLOCKS_PER_SEC;
printf("【 array length is %d 】【插入排序1】【cost time is %lf 】\n",MAX,time);
begin = clock();
InsertSort2(arr2,MAX);
end = clock();
time = (double)(end - begin)/CLOCKS_PER_SEC;
printf("【 array length is %d 】【插入排序2】【cost time is %lf 】\n",MAX,time);
begin = clock();//开始记录
InsertSort3(arr3,MAX);
end = clock();
time = (double)(end - begin)/CLOCKS_PER_SEC;
printf("【 array length is %d 】【插入排序3】【cost time is %lf 】\n",MAX,time);
return 0;
}
//插入排序
/*
时间复杂度O(n^2) 稳定的排序算法。
对于近乎有序的数组，是比较快的。适用于少量数据的排序。
算法思想：将一个数据插入到已经排好序的有序数据中合适的位置中，直到全部插完为止。
插入一个数都要将它和之前的已经完成排序的序列进行重新排序，
也就是要找到新插入的数对应原序列中的位置。
那么也就是说，每次插入一个数都要对原来排序好的那部分序列进行重新的排序。
整体思路：
a. 默认第一个数arr[0]是有序的，剩下的arr[len-2]区域是无序的
b. 每次从无序区域取出一个元素，插入前面已经排好序的区域中，合适的位置
8 6 2 =>一开始我们假设8是有序的
=>插入6元素，发现6比前一个元素小，交换位置6 8 2 ，6继续向比较已经到头，小循环结束
=>插入2元素，发现2比前面的8要小，交换位置6 2 8, 2继续向前比较小于6，交换位置2 6 8 小循环结束
=>然后整体循环结束，整个数组有序2 6 8
*/
void InsertSort1(int *arr,int n)
{
int i,j;
//假设第一个元素是有序的
for(i=1; i<n; i++){
for(j = i;j>0;j--){
if(arr[j] < arr[j-1]){//判断是否与前一个元素小
swap(&arr[j],&arr[j-1]);//如果小于就交换
}else{//如果大于或者等于，就不用再向前循环，因为前面已经是有序的
break;//跳出循环
}
}
}
}
/*
优化
【直接插入排序】向左比较
由于之前的插入，每次如果小的话，都需要进行交换位置，也是比较耗时，所以我们这次先确定位置
8 6 2
一开始8是有序的
=>8
现在开始插入6 先让elem = 6 复制了一份，
然后向前寻找到elem合适的位置，由于8比6还要大，8向后移动赋值一位 =>8 8，然后再向左到头了，找到位置
然后插入(赋值) 6
=> 6 8
现在开始插入2 elem = 2 复制了一份
然后向左移动， 8>2,然后把8向后移动一为6 8 8 然后与之前的元素比较6>2 然后把6向后移动一位6 6 8
然后到头了，找到合适位置，然后赋值为2 变成2 6 8
=>2 6 8
简化一下说明：
[1]默认第一个元素是有序的，arr[0]
[2]取下一个元素记作elem，向前已经排好序的元素序列中，也就是向数组左边的比较。
[3]如果该元素大于elem新的要插入的元素，就向后移动到下一个元素。
[4]然后重复步骤3，直到找到已排序的元素小于或者等于新的元素的位置。
[5]就插入到该位置后面，由于等于的元素不会交换相对位置，所以排序是稳定的。
[6]重复2~5
*/
void InsertSort2(int *arr,int n)
{
int i,j;
//假设第一个元素是有序的
for(i=1; i<n; i++){
int elem = arr[i];
for(j = i;j>0 && elem <arr[j-1] ;j--){ //看一下当前elem的值 要比前面的值小，那么就不应该放到这里
arr[j] = arr[j-1];//那么j就不是我们要找的，向后移动一个元素
}
arr[j] = elem;//j就是我们要找的合适的位置
}
}
/**
【折半插入排序】
折半插入（Binary Insert Sort）和直接插入类似
唯一的区别就是在有序列表中比较查找插入位置时用的是二分法。
因为前面部分是有序列表，所以是最理想的二分法。
*/
void InsertSort3(int *arr, int len)
{
int left,right,mid;
int elem;
int i,j;
for(i=1;i<len;i++){
right = i-1;
left = 0;
//二分获取插入位置
while(left<=right){
mid = (left+right)/2;
if(arr[mid] > arr[i]){
right = mid - 1;
}else{
left = mid + 1;
}
}
//得到位置，其他元素后移， 直接插入
elem = arr[i];
for(j=i;j>right+1;j--){
arr[j] = arr[j-1];
}
arr[right+1] = elem;
}
}
//随机生成一个数组
void getRandArray(int *arr,int n,int Range)
{
srand(time(NULL));//设置随机种子
int i = 0;
for (i=0; i<n; i++){
arr[i] = rand() % Range;//范围在Range以内
}
}
//随机生成一个比较有序的数组 先有序，然后随机交换位置
void getNearRandArray(int *arr,int n,int times)
{
int i = 0;
for(i;i<n;i++){//先构造一个有序的数组
arr[i] = i;
}
srand(time(NULL));//设置种子
for(i=0;i<times;i++){//尽量有序 循环交换多少次
int posx = rand()%(n-1);//在[1,n-1]上随机位置
int posy = rand()%(n-1);
swap(&arr[posx],&arr[posy]);//随机交换两个位置的数
}
}
//交换两个值 利用指针交换位置
void swap(int *a,int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
//打印输出数组
void dump(int *arr,int n)
{
int i=0;
for(i=0;i<n;i++)
printf("%d ",arr[i]);
printf("\n");//换行
} 二. PHP版
【直接插入】
/* * 插入排序 * 时间复杂度 O(n^2) 稳定性 ，只有小于前面的数，才交换 * @param array $arr 要排序的数组 * @param int $len 数组的长度 * * @return array $arr 排好序的数组 */ public function insertSort($arr,$len) { $i=0; $temp=0; for($i=1; $i<$len ; $i++){ $temp = $arr[$i];//保存当前值 for($j=$i; $j>0; $j--){//向前比较 if($temp < $arr[$j-1]){//看一下当前值比前面的小，就赋值 $arr[$j] = $arr[$j-1]; } } $arr[$j] = $temp;//找到合适的位置 把当前的值给过去 } return $arr; }
【二分插入】
/**
* 折半插入排序
*/
public function binaryInsertSort($arr,$len)
{
$left=$right=$mid=0;
$temp=0;
$i=$j=0;
for($i=1;$i<$len;$i++){
$right=$i-1;
$left =0;
//二分获取插入位置
while($left<=$right){
$mid = ($left+$right)/2;
if($arr[$mid] > $arr[$i]){//那么就是在左边
$right = $mid - 1;
}else{
$left = $mid + 1;//那么就是在右边
}
}
//得到位置$right，其他元素后移，
$temp = $arr[$i];
for($j=$i;$j>$right+1;$j--){
$arr[$j] = $arr[$j-1];
}
$arr[$right+1] = $temp;//插入
}
return $arr;
}【完整代码】
<?php
//插入排序
class Insert
{
const MIN = 0;
const MAX = 1000;//设置随机数的范围
private $len = 10;//默认构造的数组长度
private $times= 10;//无序交换次数
public $arr = [];//要排序的数组
public $out = [];//排好序的数组
public function __construct($len=0,$times=0,$min=Insert::MIN,$max=Insert::MAX)
{
$this->len = empty($len) ? $this->len:$len;//判断要生成数组的长度
$this->times= empty($times) ? $this->times:$times; //无序交换次数
//$this->arr = $this->getRandArray($this->len,$min,$max);//生成无序数组
$this->arr = $this->getNearRandArray($this->len,$this->times,$min,$max);//生成相对有序数组
echo '数组长度:',$len,'<br/>';
echo '随机数范围:[',$min,',',$max,']','<br/>';
echo '无序交换次数:',$times,'<br/>';
$stime=microtime(true);
$this->out = $this->insertSort($this->arr,$this->len);//调用插入排序
$etime=microtime(true);
$total=$etime-$stime;
echo "<br />[直接插入排序]执行时间为：{$total} 秒<br/>";
$stime=microtime(true);
$this->out = $this->binaryInsertSort($this->arr,$this->len);//调用插入排序
$etime=microtime(true);
$total=$etime-$stime;
echo "<br />[二分插入排序]执行时间为：{$total} 秒<br/>";
// var_dump($this->arr,$this->out);
}
/*
* 插入排序
* 时间复杂度 O(n^2) 稳定性 ，只有小于前面的数，才交换
* @param array $arr 要排序的数组
* @param int $len 数组的长度
*
* @return array $arr 排好序的数组
*/
public function insertSort($arr,$len)
{
$i=0;
$temp=0;
for($i=1; $i<$len ; $i++){
$temp = $arr[$i];//保存当前值
for($j=$i; $j>0; $j--){//向前比较
if($temp < $arr[$j-1]){//看一下当前值比前面的小，就赋值
$arr[$j] = $arr[$j-1];
}
}
$arr[$j] = $temp;//找到合适的位置 把当前的值给过去
}
return $arr;
}
/*
* 折半插入排序
*/
public function binaryInsertSort($arr,$len)
{
$left=$right=$mid=0;
$temp=0;
$i=$j=0;
for($i=1;$i<$len;$i++){
$right=$i-1;
$left =0;
//二分获取插入位置
while($left<=$right){
$mid = ($left+$right)/2;
if($arr[$mid] > $arr[$i]){//那么就是在左边
$right = $mid - 1;
}else{
$left = $mid + 1;//那么就是在右边
}
}
//得到位置$right，其他元素后移，
$temp = $arr[$i];
for($j=$i;$j>$right+1;$j--){
$arr[$j] = $arr[$j-1];
}
$arr[$right+1] = $temp;//插入
}
return $arr;
}
//交换两个变量
private function swap(&$a,&$b)
{
$temp = 0;//借助第三个变量
$temp = $a;
$a = $b;
$b = $temp;
}
/**
* 生成部分有序的数组
*
* @params $len 数组长度
* @params $times 数组无序交换的次数
* @params $min $max 随机数的范围
*
* return array
*/
private function getNearRandArray($len,$times,$min,$max)
{
$arr = [];//生成部分有序的数组
for($i=0; $i<$len; $i++){
$arr[$i] = $i;
}
for($i=0; $i<$times; $i++){//打乱有序 循环交换多少次
$posx = mt_rand($min,$max)%($len-1);//在[1,len-1]上随机位置
$posy = mt_rand($min,$max)%($len-1);
$this->swap($arr[$posx],$arr[$posy]);//随机交换两个位置的数
}
return $arr;
}
/**
* 生成随机数组
*
* @params $len 随机数组的长度
* @params $min $max 随机数的范围
*/
private function getRandArray($len,$min,$max)
{
$arr = [];//生成无序的数组
for($i=0; $i<$len; $i++){
$arr[$i] = mt_rand($min,$max);
}
return $arr;
}
}
new Insert(1000,5);//实例化类 
京公网安备 11010502036488号