插入排序

上几年班,做几年业务开发,大学学的数据结构和算法基本都快忘完了。查找和排序算法,作为高频问答题,面试的时候遇到过好几次。插入排序又是排序算法中必须掌握的一种,操作的时候有点像平时打扑克牌的意思,特此记录!

一、概念

  1. 将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是依次取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。
  2. 插入排序是一种基于比较的排序算法。

二、实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function insertionSort($data)
{
$n = count($data);
if ($n <= 1) {
return $data;
}

for ($i = 1; $i < $n; ++$i) {
$value = $data[$i];// 从下标为1开始,依次取后面的数和前面已排好序的数进行比较

// 查找插入的位置
$j = $i - 1;
for ($j; $j >= 0; --$j) {
if ($data[$j] > $value) {
$data[$j + 1] = $data[$j];// 数据移动
} else {
break;
}
}

$data[$j + 1] = $value;// 插入数据
}
return $data;
}