PHP 希尔排序


希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。

但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率

  • 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位

算法步骤:

  1. 先将整个待排序的记录序列分割成为若干子序列,分别进行直接插入排序

  2. 待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

PHP实现代码:


/**
* 希尔排序 标准
*
* @param array $lists
* @return array
*/
function shell_sort(array $lists)
{
   $n = count($lists);
   $step = 2;
   $gap = intval($n / $step);
   while ($gap > 0) {
       for ($gi = 0; $gi < $gap; $gi++) {
           for ($i = $gi; $i < $n; $i += $gap) {
               $key = $lists[$i];
               for ($j = $i - $gap; $j >= 0 && $lists[$j] > $key; $j -= $gap) {
                   $lists[$j + $gap] = $lists[$j];
                   $lists[$j] = $key;
               }
           }
       }
       $gap = intval($gap / $step);
   }
   return $lists;
}


来源: up61技术博客 欢迎分享 (QQ:529857614)

qq交流群:63739043 up61博客-php交流群

上一篇: PHP 堆排序
下一篇: PHP 各种排序的稳定性,时间复杂度、空间复杂度、稳定性总结