PHP回顾--插入排序(包含希尔排序)
2019-03-01| 程成| 183| 0| PHP技术

一、定义


插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,是一种稳定的排序方法。


希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。


视觉直观感受7种常用排序算法

希尔排序效果图


上面解释来源于百度百科。先抛出个结论:你可以将希尔排序理解为 预排序的插入排序,后面会解释两者具体的关系。



二、排序演示


1、插入排序



下标

0

1

2

3

4

5

6

7

数据

9

3

4

2

6

7

5

1



插入排序是通过插入的方式进行排序的。这里我们进行升序排序。我们从第二个元素开始比较,因为3比第一个元素9小,所以3和9进行交换位置。


下标

0

1

2

3

4

5

6

7

数据

3

9

4

2

6

7

5

1


交换完成后,进行下一次比较,这时候4和9比较,4比9小,然后再交换位置,之后4和3进行比较,4比3大所以停止交换。同理2也是这个原理比较。


下标

0

1

2

3

4

5

6

7

数据

2

3

4

9

6

7

5

1


然后取下一个元素6比较,比9小和9进行交换;再往前和4比,比4大不交换。

这时候就不需要和4之前的元素比较了,因为这时候6之前的数组已经是有序的了。一直这样排序下去直到最后一个元素,这样数组久排序完成了。


以上就是插入排序的实例演示。


当算法都是O(N2)的时间级别。插入排序和快速排序比冒泡快一倍,比选择排序略快一点。



2、希尔排序


但是当你数组是降序有序的数组时,这个时候你想用插入排序进行升序排序,这时候,时间复杂度十分高的。

为了避免出现这种情况,所以就有了希尔排序。


举个例子,我的数组如下:


下标

1

2

3

4

5

6

7

8

9

数据

9

8

7

6

5

4

3

2

1


现在要改成升序排序,这是极端情况。希尔排序如何实现的?简单说就是将数组先进行一个预排序。

(注意这里数组下标从1开始,便于后面理解。)


这里希尔排序做的是先将数组下标是1,4,7这三个数进行一下预排序。然后将2,5,8,三个数进行一下预排序,最后将你的3,6,9进行一下预排序,然后再将你的数组进行一下插入排序。这就是希尔排序做的事情,先跳着将你的数组进行一个预排序,这里是极端情况,在进行预排序后数组已经有序了,但是这也是极少数情况。


希尔排序并不是说我先通过一个固定的gap间隔值来进行预排序一趟之后就按照以前的插入排序进行排,这里是不断的缩小你的间隔值来不断的接近之前间隔为1的插入排序,这到最后间隔值变成1,也就是完全和以前的插入排序一样了。


其他方面其实和插入排序完全一样,插入排序是读取的你当前数字的下一个数字,但是希尔排序读取的就是你当前数字距离为gap的数字。


 在这里读取数据的时候,我选择的是从数组后边向前读,也可以从前往后读。然后整个程序最巧妙的地方在于for循环中的i++,在上边的程序中我也标注出来了,为什么说他巧妙。


下标

1

2

3

4

5

6

7

8

9

数据

3

2

1

6

5

4

9

8

7


图里红色的数据是间隔为gap的值,绿色和蓝色也都是,也就是说,你需要将下标为0、3、6的三个数据进行比较,之后需要将绿色下标为1、4、7的数据进行比较,如果是按当前的方法的话,进行完第一个轮排序之后,也就是红色数据比较完之后,你就找不到你的绿色第一个数据,还需要一些中间值进行保存数据,但是这里用i++的思想是,首先让你0和3比较,比较完之后不会继续去找6,而是去让1和4比较,之后是2和5比较,然后当所有都结束之后,开始让3和6比较,4和7比较,其实这里我解释多了之后反倒很难理解自己稍微一思考就能明白。



三、代码实现


function insertSort($arr) {
        $len=count($arr);
        for($i=1; $i<$len; $i++){
            $tmp = $arr[$i];
            //内层循环控制,比较并插入
            for($j=$i-1;$j>=0;$j--) {
                if($tmp < $arr[$j]) {
                    //发现插入的元素要小,交换位置,将后边的元素与前面的元素互换
                    $arr[$j+1] = $arr[$j];
                    $arr[$j] = $tmp;
                } else {
                    //如果碰到不需要移动的元素,由于是已经排序好是数组,则前面的就不需要再次比较了。
                    break;
                }
            }
        }
        return $arr;
    }



×
作者:程成
QQ:492245711