排序算法之插入排序

蚊子前端博客
发布于 2012-12-01 07:00
本篇主要讲解下插入排序,插入排序一般分为直接插入排序和二分插入插入排序

插入排序一般分为直接插入排序和二分插入插入排序。

直接插入排序又可以分为前插和后插,不过虽然是这样分,只是寻找地点的方向不一样而已。“前插”就是从头开始找合适的位置,“后插”就是从后面开始找合适的位置。这里我们只讨论“后插”。直接插入排序的思想很简单,开始时,整个数组都是无序的,默认第一个数是排好序的,然后要把第二个数插入到前面,那么就要找到合适的位置插入,从当前数的前一个数$a与当前数$s进行比较,如果此时$a<$s,那么就把$s插入到$a的后面,否则$s就与$a前面的数$b进行比较,或者$a已经是第一个数了就停止,把$s插入到数组的第一个位置。现在前两个数已经是有序的了, 然后就是插入第三个数,步骤是一样的。一个关键性的问题就是,循环停止的位置是要插入的位置的前一个,也就是说,应该从这个位置的后一个向后移动,腾出那个合适的位置。腾位置时应该是前一个数覆盖后一个数,所有for循环应该从后向前开始。

COPYPHP

function insertSort(&$a){ $t = count($a); for($i=1; $i<$t; $i++){ $j = $i-1; while($j>=0){ if($a[$j] < $a[$i]){ break; }else{ $j--; } } //保存当前数据 $s = $a[$i]; //将数据向后移动 for($k=$i; $k>$j+1; $k--){ $a[$k] = $a[$k-1]; } //将当前的数据放在找到的位置 $a[$j+1] = $s;21 } }

还有就是二分插入排序,二分插入排序只不过查找的方式不同而已。每次要插入的值$a[$i]总是与前面已排好序的中间的值$a[$mid]进行比较,如果$a[$i]比较小则在前面的区间继续二分查找,否则在后面的区间。

COPYPHP

function binarySort(&$a){ $t = count($a); for($i=1; $i<$t; $i++){ $left = 0; $right = $i; while($left <= $right){ $mid = intval(($left+$right)/2); if($a[$mid] > $a[$i]){ $right = $mid-1; }else if($a[$mid] < $a[$i]){ $left = $mid+1; }else{ break; } } //保存当前数据 $s = $a[$i]; //将数据向后移动 for($k=$i; $k>=$left; $k--){ $a[$k] = $a[$k-1]; } //将当前的数据放在找到的位置 $a[$left] = $s; } }

插入排序也是一种简单的排序方式。

标签:
阅读(195) 评论(0)

公众号:

qrcode

微信公众号:前端小茶馆