插入排序
<ul>
<li>对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。</li>
<li>在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。</li>
</ul>
<h2>实现</h2>
<pre><code class="language-php">function insert(array $arr)
{
$count = count($arr);
if (empty($arr) || $count == 1) {
return $arr;
}
for ($out = 1; $out < $count; $out++) {
//获得当前需要比较的元素值
$tmp = $arr[$out];
//内层循环控制 比较 并 插入
for ($in = $out - 1; $in >= 0; $in--) {
//$arr[$out];需要插入的元素
//$arr[$in];需要比较的元素
if ($tmp < $arr[$in]) { //从小到大 < || 从大到小 >
//发现插入的元素要小,交换位置
//将后边的元素与前面的元素互换
$arr[$in + 1] = $arr[$in];
//将前面的数设置为 当前需要交换的数
$arr[$in] = $tmp;
} else {
//如果碰到不需要移动的元素
//由于是已经排序好是数组,则前面的就不需要再次比较了。
break;
}
}
}
return $arr;
}</code></pre>
<h2>测试</h2>
<pre><code class="language-php">$arr = [23, 15, 43, 25, 54, 2, 6, 82, 11, 5, 21, 32, 65];
$insert = insert($arr);
var_export($insert);</code></pre>
<h2>结果</h2>
<pre><code class="language-php">array (
0 => 2,
1 => 5,
2 => 6,
3 => 11,
4 => 15,
5 => 21,
6 => 23,
7 => 25,
8 => 32,
9 => 43,
10 => 54,
11 => 65,
12 => 82,
)</code></pre>