拔出排序 Insert Sort
● 拔出排序的思维:
将一个待排序的无序的数组看做是两个列表,一个有序的列表,一个无序的列表,从无序的列表每一次拿出一个待拔出的元素,拔出到有序的列表中,直到无序列表为空,排序终了
● 实际举例:
1. 有一个无序的一维数组是此次需求排序的数组,数组是:[36,12,96,-1]
2. 起首把数组的第一个元素 [36] 看做是一个自力的有序的列表,把剩下的元素 [12, 96, -1] 看做是一个无序的列表
3. 第一个待拔出的元素就是 12,要把 12 拔出到有序的列表中,起首需求 12 以及 36 比拟,假如带拔出的元素 12 小于 36, 就需求把 12 拔出到 36后面,也就是 36 要后移一名。
4. 拔出排序实际是需求比拟数组元素的总数减一轮,由于第一个元素没有需求比拟。
$arr = [36,12,96,-1]; //待拔出的数 $insertValue = $arr[1]; //待拔出数后面的数的索引 $insertIndek = 1 - 1; //$insertIndek >= 0 保障拔出轮回时,没有越界,保障第一个元素的下标要年夜于等0 //$insertValue < $arr[$insertIndek] 保障待拔出的数尚未找到拔出的地位,即待拔出的数是小于它后面的那一个元素的 //合乎上述前提的,需求将$arr[$insertIndek] 后移 while($insertIndek >= 0 && $insertValue < $arr[$insertIndek]) { $arr[$insertIndek+1] = $arr[$insertIndek]; $insertIndek--; //代表的就是有序列表的最后面一个元素的后面一个下标 -1; } //当加入轮回时,代表找到地位 $insertIndek + 1 $arr[$insertIndek + 1] = $insertValue; //把拔出的元素拔出到有序列表的第一个地位或许是没发作替换就正在自身的地位 $arr = [12,36,96,-1]; //待拔出的数 $insertValue = $arr[2]; //待拔出数后面的数的索引 $insertIndek = 2 - 1; //$insertIndek >= 0 保障拔出轮回时,没有越界,保障第一个元素的下标要年夜于等0 //$insertValue < $arr[$insertIndek] 保障待拔出的数尚未找到拔出的地位,即待拔出的数是小于它后面的那一个元素的 //合乎上述前提的,需求将$arr[$insertIndek] 后移 while($insertIndek >= 0 && $insertValue < $arr[$insertIndek]) { $arr[$insertIndek+1] = $arr[$insertIndek]; $insertIndek--; //代表的就是有序列表的最后面一个元素的后面一个下标 -1; } //当加入轮回时,代表找到地位 $insertIndek + 1 $arr[$insertIndek + 1] = $insertValue;//把拔出的元素拔出到有序列表的第一个地位或许是没发作替换就正在自身的地位
顺次类推,失去实现的有序数组
5. 完好代码以下:
<?php class InsertSort { public static function insertArraySort(array $data):array { if (!is_array($data)) { return ['message' => '待排序的序列非数组']; } $count = count($data); if ($count <= 1) { return $data; } for ($i = 1; $i < $count; $i++) { //待拔出的元素 $insertValue = $data[$i]; //待拔出数后面的数的索引 $insertIndek = $i - 1; //$insertIndek >= 0 保障拔出轮回时,没有越界,保障第一个元素的下标要年夜于等0\ //$insertValue < $arr[$insertIndek] 保障待拔出的数尚未找到拔出的地位,即待拔出的数是小于它后面的那一个元素的 //合乎上述前提的,需求将$arr[$insertIndek] 后移 while($insertIndek >= 0 && $insertValue < $data[$insertIndek]) { $data[$insertIndek+1] = $data[$insertIndek]; $insertIndek--;//代表的就是有序列表的最后面一个元素的后面一个下标 -1; } //当加入轮回时,代表找到地位 $insertIndek + 1 //把拔出的元素拔出到有序列表的第一个地位 //或许是没发作替换,即待拔出元素年夜于有序列表的最初一个元素,那末这里只要要将有序列表的最初一个元素的索引 + 1,把待拔出元素放正在后 //面一名便可 $data[$insertIndek + 1] = $insertValue;\ } return $data; } } $arr = [36,12,96,-1]; var_dump(InsertSort::insertArraySort($arr));
以上就是PHP 排序算法之拔出排序的具体内容,更多请存眷资源魔其它相干文章!
标签: php php开发教程 php开发资料 php开发自学
版权声明:除非特别标注,否则均为本站原创文章,转载时请以链接形式注明文章出处。
抱歉,评论功能暂时关闭!