返回首页 - Notes - 2013

希尔排序


算法描述

将数组分割成独立的 h 个子序列,然后对各个子序列分别应用插入排序算法


算法实现

Ruby

# 希排
class Array
  def shell_sort!
    len = self.length
    h = 1
    while h < len / 3
      h = 3*h + 1
    end

    while h >= 1
      h.upto(len - 1) do |i|
        i.downto(h) do |j|
          self[j], self[j - h] = self[j - h], self[j] if self[j] < self[j - h]
          j -= h
        end
      end
      h /= 3
    end
  end
end


# 测试
arr = (1..10).to_a.shuffle
p arr

arr.shell_sort!
p arr

PHP

<?php

// 希排
function shell_sort (&$arr) {
    $len = count($arr);
    $h = 1;
    while ($h < intval($len / 3)) {
        $h = 3*$h + 1;
    }

    while ($h >= 1) {
        for ($i = $h; $i < $len; ++$i) {
            for ($j = $i; $j >= $h; --$j) {
                if ($arr[$j] < $arr[$j - $h]) {
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j - $h];
                    $arr[$j - $h] = $temp;
                }
                $j -= $h;
            }
        }
        $h = intval($h / 3);
    }
}


// 打印数组
function print_arr ($arr) {
    echo '[';
    for ($i = 0; $i < count($arr) - 1; ++$i) {
        echo $arr[$i].' ';
    }
    echo $arr[count($arr) - 1];
    echo ']';
}


// 测试
$arr = range(1, 10);
shuffle($arr);
print_arr($arr);
echo "\n";

shell_sort($arr);
print_arr($arr);
echo "\n";

date : 2013-02-21、2014-11-24