算法与数据结构系列 ( 四 ) - 插入排序法- Insert

前言

本章我们继续理解另外一个排序算法 插入排序
插入排序 也算是我们 O(n^2) 的经典排序算法之一
插入排序 其实非常简单, 在我们日常当中也是常见的一种思想
可能相对而言大家并没有归类总结。所以可能大家使用过，但是并不知晓。

举个生活栗子

我们在打 扑克牌 的时候，我们整理牌的思想，差不多就是 插入排序 的思想。
换句话说，就是把牌插入到相对合适的位置。
当我们把手上所有的牌插入到指定位置，我们的牌就插入完成了

插入排序，先简单了解一下思路

• 首先我们有这么一段数据，我们需要将他们重新整合有序
  | 7 | 2 | 1 | 5 | 4 | 6 | 9 | 3 | 8 |

第一次排序

• 用插入排序的思路就是先找到拿到数字坐标 0 也就是 7
• 但是和选择排序不同的时候，此时我们并不会去移动 7
  | 7 | 2 | 1 | 5 | 4 | 6 | 9 | 3 | 8 |

第二次排序

• 接下来我们继续对数字坐标 1 的数字，和前面的数字进行一个对比
• 显然 2 比 7 小，我们就将 2 放在 7 的前面
• 此时| 2 | 7 |已然排序完成
  | 2 | 7 | 1 | 5 | 4 | 6 | 9 | 3 | 8 |

第三次排序

• 接下来我们继续对数字坐标 2 的数字，和前面的数字进行一个对比
• 显然 1 比 7小，我们就将 1 放在 7 的前面
• 然后再拿 1 和 2 对比，1 比 2 小，我们就将 1 放在 7 的前面
• 此时 | 1 | 2 | 7 | 已然排序完成
  | 1 | 2 | 7 | 5 | 4 | 6 | 9 | 3 | 8 |

第四次排序

• 接下来我们继续对数字坐标 3 的数字，和前面的数字进行一个对比
• 显然 5 比 7小，我们就将 5 放在 7 的前面
• 然后再拿 5 和 2 对比，5 比 2 大，我们就将 5 原定不动
• 此时| 1 | 2 | 5 | 7 |已然排序完成
  | 1 | 2 | 5 | 7 | 4 | 6 | 9 | 3 | 8 |

TimAutumnWind （转载请注明出处 https://learnku.com/users/48310）

此后一直以此类推，直至到底

实现一下代码 - for

• 时间和性能记录，可以参照章节三中的 选择排序
• 以后会直接实现代码

/**
 * 插入排序操作方法  - for
 * @param $sort
 * @param $n
 * @return mixed
 */
function get_insertion_sort_for($sort,$n){
    /** 将数据循环一次 */
    for ($i = 0; $i < $n; $i++ ){
        /** 将前面数据进行循环 */
        for($j = $i;$j > 0; $j--){
            /** 如果当前数字小于前面数字，则为 true */
            if($sort[$j] < $sort[$j - 1]){
                /** 
                 *  如果当前数字小于前面数字，则进行位置交换
                 *  php 没有位置交换的函数，所以简单一点，先取出，再覆盖
                 */
                $val = $sort[$j];
                $sort[$j] = $sort[$j - 1];
                $sort[$j - 1] = $val;
            }else{
                /** 如果大于前面数字，则跳出，不进行位置交换 */
                break;
            }
        }
    }
    return $sort;
}

实现一下代码 - while

• tips： 在 php 当中，while 要比 for 快一丢丢

/**
 * 插入排序操作方法 - while
 * @param $sort
 * @param $n
 * @return mixed
 */
function get_insertion_sort_while($sort,$n){
    $i = 0;
    while ( $i < $n ){
        $j = $i;
        while($j > 0){
            if($sort[$j] < $sort[$j - 1]){
                $val = $sort[$j];
                $sort[$j] = $sort[$j - 1];
                $sort[$j - 1] = $val;
            }else{
                break;
            }
            $j--;
        }
        $i++;
    }
    return $sort;
}