php实现希尔排序

对于排序的算法我想大家首先想到的事冒泡排序；快速排序；或者想起选择和插入排序；

今天的讲解并不是以上四种；而是希尔排序；

对18W个数字排序，时间比较（毫秒）希尔排序 0.1s 就完成了，有点不敢相信，插入排序用了4.2s

理解这些复杂的排序算法还是很有意思的，体会这些排序算法的精妙~

　　一、希尔排序（shell sort）：希尔排序是基于插入排序的，区别在于插入排序是相邻的一个个比较（类似于希尔中h=1的情形），而希尔排序是距离h的比较和替换。

希尔排序中一个常数因子n，原数组被分成各个小组，每个小组由h个元素组成，很可能会有多余的元素。当然每次循环的时候，h也是递减的（h=h/n）。第一次循环就是从下标为h开始。希尔排序的一个思想就是，分成小组去排序。

理解这些算法，最好是有个图示。就先来代码吧。

<?php

/**

 * 希尔排序

 */

function shell_sort(array $arr){

    // 将$arr按升序排列

    $len = count($arr);

    $f = 3;// 定义因子

    $h = 1;// 最小为1

    while ($h < $len/$f){

        $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...

    }

    while ($h >= 1){  // 将数组变为h有序

        for ($i = $h; $i < $len; $i++){  // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 （算法的关键

            for ($j = $i; $j >= $h;  $j -= $h){

                if ($arr[$j] < $arr[$j-$h]){

                    $temp = $arr[$j];

                    $arr[$j] = $arr[$j-$h];

                    $arr[$j-$h] = $temp;

                }

                //print_r($arr);echo '<br/>'; // 打开这行注释，可以看到每一步被替换的情形

            }

        }

        $h = intval($h/$f);

    }

    return $arr;

}

$arr = array(14, 9, 1, 4, 6, -3, 2, 99, 13, 20, 17, 15, 3);

$shell = shell_sort($arr);

echo '<pre>';

print_r($shell);

/**

 *

Array

(

[0] => -3

[1] => 1

[2] => 2

[3] => 3

[4] => 4

[5] => 6

[6] => 9

[7] => 13

[8] => 14

[9] => 15

[10] => 17

[11] => 20

[12] => 99

)

)

 *

 */

?>

巴特西

php实现希尔排序

最新文章

热门文章