当前位置:首页 > PHP教程 > php应用 > 列表

php实现希尔排序算法的方法分析

发布:smiling 来源: PHP粉丝网  添加日期:2021-08-22 13:38:40 浏览: 评论:0 

这篇文章主要介绍了php实现希尔排序算法的方法,简单说明了希尔排序的原理,并结合实例形式分析了php实现希尔排序的具体操作技巧,需要的朋友可以参考下。

本文实例讲述了php实现希尔排序算法的方法,分享给大家供大家参考,具体如下:

虽然现在各种程序语言都有其各自强大的排序库函数,但是这些底层实现也都是利用这些基础或高级的排序算法。

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

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

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

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

  1. <?php 
  2. /** 
  3.  * 希尔排序 
  4.  */ 
  5. function shell_sort(array $arr){ 
  6.   // 将$arr按升序排列 
  7.   $len = count($arr); 
  8.   $f = 3;// 定义因子 
  9.   $h = 1;// 最小为1 
  10.   while ($h < $len/$f){ 
  11.     $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ... 
  12.   } 
  13.   while ($h >= 1){ // 将数组变为h有序 
  14.     for ($i = $h$i < $len$i++){ // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 (算法的关键 
  15.       for ($j = $i$j >= $h$j -= $h){ 
  16.         if ($arr[$j] < $arr[$j-$h]){ 
  17.           $temp = $arr[$j]; 
  18.           $arr[$j] = $arr[$j-$h]; 
  19.           $arr[$j-$h] = $temp
  20.         } 
  21.         //print_r($arr);echo '<br/>'; // 打开这行注释,可以看到每一步被替换的情形 
  22.       } 
  23.     } 
  24.     $h = intval($h/$f); 
  25.   } 
  26.   return $arr
  27. $arr = array(14, 9, 1, 4, 6, -3, 2, 99, 13, 20, 17, 15, 3); 
  28. $shell = shell_sort($arr); 
  29. echo '<pre>'
  30. print_r($shell); 
  31. /** 
  32. * 
  33. Array 
  34. ( 
  35. [0] => -3 
  36. [1] => 1 
  37. [2] => 2 
  38. [3] => 3 
  39. [4] => 4 
  40. [5] => 6 
  41. [6] => 9 
  42. [7] => 13 
  43. [8] => 14 
  44. [9] => 15 
  45. [10] => 17 
  46. [11] => 20 
  47. [12] => 99 
  48. ) 
  49. ) 
  50. * 
  51. */

Tags: php希尔排序算法

分享到: