排序算法-插入排序

插入排序（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);//实例化类