改进的插入排序——二分法插入排序

前两天买了本《算法导论》,昨天刚看插入排序,看到例子,插入排序就类似于摸牌,摸出一张然后再插入到对应的位置。想起前些日子国庆在家玩牌的经历,摸牌时是这么个回事,但是又不同,现实中摸牌我们总是能很快的找到指定的位置,比如拿张5基本就能很快确定中间偏右的位置,因为手中的牌已经是有顺序的了。我想到了二分法也许可以在寻找位置时减少比较。

于是乎今天努力把这个算法实现,先拆分插入排序和二分法两个算法实现,然后再归纳起来:

1. 插入排序:

<?php
    // 插入排序
    function insert_sort($arr) {
        $len = count($arr);
        for($i=1; $i < $len; $i++) {
            $current = $arr[$i];
            $j = $i-1;
            while ($j >=0 && $arr[$j] > $current) {
                $arr[$j+1] = $arr[$j];
                $j--;
            }

            if($j + 1 != $i) {
                $arr[$j+1] = $current;
            }
        }

        return $arr;
    }

    $arr = [5, 3, 9, 7, 11];
    print_r(insert_sort($arr));
?>

2. 二分法查找:

<?php
    // 二分法查找
    function bin_search($search, $sortArr) {
        $low = 0;
        $high = count($sortArr) -1;
        while ($low <= $high) {
            $middle = (int) (($low + $high) / 2);
            if($search == $sortArr[$middle]) {
                return $middle;
            } else if($search > $sortArr[$middle]) {
                $low = $middle + 1;
            } else {
                $high = $middle - 1;
            }
        }
        return -1;
    }
    $sortArr = [1, 2, 3, 4, 5, 6, 7, 8];
    $search = 8;
    echo bin_search($search, $sortArr);
?>

在验证插入排序算法是否正确时,通过网上搜索发现其实心里所想的那个算法就是二分法插入排序,不过还是先自己默写下来比对了,以下是正确测试了的二分法插入排序:

<?php
    function binsearch_insert_sort($arr) {
        $len = count($arr);
        for($i=1; $i < $len; $i++) {
            $current = $arr[$i];
            $high = $i - 1;
            $low = 0;
            $position = 0;
            while( $low <= $high) {
                $middle = (int) (($low + $high) / 2);
                if($current > $arr[$middle]) {
                    $low = $middle + 1;
                    $position = $middle + 1;
                } else {
                    $high = $middle - 1;
                    $position = $middle;
                }
            }

            $j = $i-1;
            while ($j >= $position) {
                $arr[$j + 1] = $arr[$j];
                $j--;
            }
            $arr[$j + 1] = $current;
        }

        return $arr;
    }

    $arr = [5, 3, 9, 7, 3, 15, 2, 7, 11];
    print_r(binsearch_insert_sort($arr));
?>

比对了下网上算法基本算是一致了,分析了下在查找位置时,根据二分查找,最差也是lgn次便可找出位置,但插入移动位置并不会减少时间,最坏时仍是n(n-1)/2, ⊙(n∧2)次。

其实真实的摸牌更接近于链表结构式的数据存储,断开相邻两个在他们中间插入,减少了移动元素带来的操作,还有对于摸牌这种游戏,无非是A~K, 大小王这几种牌,接到一张时实际上我们很快可以估算大概位置,带有点概率查找的味道

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>