插入排序（Insertion Sort）

概念

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

步骤

• 从第一个元素开始，该元素可以认为已经被排序
• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果该元素（已排序）大于新元素，将该元素移到下一位置
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
• 将新元素插入到该位置中
• 重复步骤2

实例

/**
 * 插入排序
 *
 * @param  array  $arr
 */
static function insertSort(array &$arr): void
{
    if (empty($arr)) return;
    $count = count($arr);

    for ($i = 1; $i < $count; $i++)
    {
        // 当前要对比的元素
        $temp = $arr[$i];
        // 往前去对比，对比到第一个下标即可完成一轮
        for ($j = $i - 1; $j >= 0; $j--)
        {
            if ($temp < $arr[$j]) //从小到大 < || 从大到小 >
            {
                // 元素小于，与之后的交换位置
                $arr[$j+1] = $arr[$j];

                // 将前面的数设置为 当前需要交换的数
                $arr[$j] = $temp;
            }else{ // 当前一轮完成
                break;
            }
        }
    }
}