插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

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

动图演示

插入排序（Insertion Sort） - 图1

代码实现

  1. <?php
  3. class Sorting
  4. {
  5.         /**
  6.      * 插入排序（稳定地原地排序算法）
  7.      * 时间/空间：O(n^2)/O(1)
  8.      *
  9.      * @param array $array
  10.      * @return array
  11.      */
  12.     public static function insertionSort(array $array): array
  13.     {
  14.         if (empty($array) || count($array) == 1) {
  15.             return $array;
  16.         }
  18.         $length = count($array);
  20.         for ($i = 1; $i < $length; $i++) {
  21.             $preIndex = $i - 1;
  22.             $current = $array[$i];
  24.             while($preIndex >= 0 && $current < $array[$preIndex]) {
  25.                 $array[$preIndex + 1] = $array[$preIndex];
  26.                 $preIndex--;
  27.             }
  28.             $array[$preIndex + 1] = $current;
  29.         }
  31.         return $array;
  32.     }
  33. }

算法分析

插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

  • 时间复杂度：O(n2)
  • 空间复杂度：O(1)
  • 稳定排序
  • 原地排序