程序员内功修炼之学好算法和数据结构（一）排序基础、选择排序、插入排序、希尔排序

Broadview

2019-06-26

关注关注

一、排序基础（`重要`）

1.1 为什么要学习O(n^2)的排序算法？

编码简单，易于实现，是一些简单情景的首选。
在一些特殊情况下，简单的排序算法更有效。
简单的排序算法思想衍生出复杂的排序算法，在这个过程中可以加深理解从而想出更复杂的解决方法，体现一种思考的渐进过程。
作为子过程，改进更复杂的排序算法（如插入排序改进复杂算法）。

1.2 排序算法的稳定性

1.2.1 稳定性

原本键值一样的元素排序后相对位置不变，那么该排序算法是稳定的；否则是不稳定的。

举个例子：

对五个同学（A,B,C,D,E）进行成绩排序，他们的成绩分别为：90，88，79，88，92，按成绩从高到低排（92,90,88,88,79）：

E,A,B,D,C——稳定的（B,D的相对位置没有变化）
E,A,D,B,C——不稳定的（B,D的相对位置发生了变化）

1.2.2 排序算法稳定的意义

排序算法如果是稳定的，从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。

举个例子：

一个班的学生已经按照学号大小排好序了，现在要求按照年龄从小到大再排个序，如果年龄相同的，必须按照学号从小到大的顺序排列。

那么问题来了，如果选择的年龄排序方法如果是不稳定的，排序完了后年龄相同的一组学生学号就乱了，就得把这组年龄相同的学生再按照学号拍一遍。如果是稳定的排序算法，就只需要按照年龄排一遍就好了。

如果排序算法是稳定的，元素交换的次数可能会少一点。这样看来稳定的排序算法是节省了时间，稳定性的优点就体会出来了。

1.3 辅助函数文件Helper.php

/**
 * 只有引用才能改变原理数组中的值
 *
 * @param $x
 * @param $y
 */
function swap(&$x, &$y) {
    $t = $x;
    $x = $y;
    $y = $t;
}


/**
 * 功能：生成有n个元素的随机数组,每个元素的随机范围为[$rangeL, $rangeR]
 * 知识点：rand() 函数生成随机整数。
 * 提示：如果您想要一个介于 10 和 100 之间（包括 10 和 100）的随机整数，请使用 rand (10,100)。
 * 提示：mt_rand() 函数是产生随机值的更好选择，返回结果的速度是 rand() 函数的 4 倍。
 *
 * @param $n
 * @param $rangeL
 * @param $rangeR
 * @return mixed
 */

function generateRandomArray($n, $rangeL, $rangeR)
{
    //容错处理，当$rangeR<$rangeL时，交换它们值
    if ($rangeR < $rangeL) {
        $tmp = $rangeL;
        $rangeL = $rangeR;
        $rangeR = $tmp;
    }

    for ($i = 0; $i < $n; $i++)
            $arr[$i] = mt_rand($rangeL,$rangeR);
        return $arr;
}

/**
 * 功能：生成几乎有序的数组
 *
 * @param $n
 * @param $swapTimes
 * @return mixed
 */
function generateNearlyOrderedArray($n, $swapTimes){

    for($i = 0 ; $i < $n ; $i ++ )
            $arr[$i] = $i;
    //随机挑选几个元素进行交换
    for( $i = 0 ; $i < $swapTimes ; $i ++ )
    {
        $posx = mt_rand()%$n;
        $posy = mt_rand()%$n;
        //交换
        $temp = $arr[$posx];
        $arr[$posx] =  $arr[$posy];
        $arr[$posy] = $temp;
    }
    return $arr;
}

/**
 * 功能：判断一个数组是否为升序排序
 * @param $arr
 * @return bool
 */
function isSorted($arr)
{
    for ($i = 0; $i < count($arr)-1; $i++)
            if ($arr[$i] > $arr[$i + 1])
                return false;

    return true;
}

二、选择排序

2.1 选择排序

每次找剩下最小/大的元素，每次交换一对元素。(不稳定的排序算法)

举个例子：序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序是不稳定的排序算法。

2.2 算法描述

扫描整个序列，把当前最小的值与未排序序列的第一位进行交换。
扫描1（不包括1）之后的序列，把序列中最小的值与未排序的第一位进行交换。
扫描2（不包括2）之后的序列，把序列中最小的值与未排序的第一位进行交换。
…… 结束。

程序员内功修炼之学好算法和数据结构（一）排序基础、选择排序、插入排序、希尔排序

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。

2.3 范例代码

/**
 * 选择排序：每次找剩下最小元素，每次交换一对元素。
 *
 * @param $arr
 * @return mixed
 */
function selectionSort($arr){

    for($i = 0 ; $i < count($arr) ; $i ++){

        $minIndex = $i;
        for( $j = $i + 1 ; $j < count($arr) ; $j ++ )
            if( $arr[$j] < $arr[$minIndex] )
                $minIndex = $j;
        //交换
        swap($arr[$minIndex],$arr[$i]);
    }

    return $arr;
}

2.4 算法分析

2.4.1 比较操作

(n-1)+(n-2)+...+1=n(n-1)/2次。

2.4.2 交换操作

介于0和(n-1)次之间。最好情况是，已经有序，交换0次；最坏情况是，逆序，交换 n-1次。

交换次数比冒泡排序较少，由于交换所需CPU时间比比较所需的CPU时间多， n值较小时，选择排序比冒泡排序快。

2.4.3 时间复杂度

O(n^2)

2.4.4 应用场景

原地操作几乎是选择排序的唯一优点，当空间复杂度要求较高时，可以考虑选择排序；实际适用的场合非常罕见。

三、插入排序（`非常重要`）

3.1 插入排序

寻找元素arr[i]合适的插入位置，使索引数组中下标为 i 之前的元素有序 (稳定排序算法)

3.2 算法描述

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

程序员内功修炼之学好算法和数据结构（一）排序基础、选择排序、插入排序、希尔排序

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序。

3.3 范例代码（`推荐写法3`）

/**
 * 插入排序：寻找元素arr[i]合适的插入位置，使索引数组中下标为'i'之前的元素有序
 * 
 * @param $arr
 * @return mixed
 */
function insertionSort($arr)
{
    for( $i = 1 ; $i < count($arr) ; $i ++ ) {

        // 寻找元素arr[i]合适的插入位置
        // 写法1
//        for( $j = $i ; $j > 0 ; $j-- ){
//            if( $arr[$j] < $arr[$j-1] )
//                swap($arr[$j-1],$arr[$j]);
//            else
//                break;
//        }

        // 写法2,插入排序和选择排序最大区别是插入排序可以提前结束 # 写法2比写法1简洁
//        for( $j = $i ; $j > 0 && $arr[$j] < $arr[$j-1]; $j -- ){
//            swap( $arr[$j-1],$arr[$j]);
//        }

        //（推荐）写法3,保存副本，通过赋值取代交换，减少交换赋值次数，（上两种写法交换一次会有三次赋值），提升性能
        // (性能比前面写法高4倍左右)
        $e = $arr[$i];
        for ($j = $i; $j > 0 && $arr[$j-1] > $e; $j--)
            $arr[$j] = $arr[$j-1];
        // j保存元素e应该插入的位置
        $arr[$j] = $e;
    }

    return $arr;
}

3.4 算法分析

3.4.1 比较操作

如果目标是把n个元素的序列升序排列：

最好情况：序列已经是升序排列了，每插入一个元素，只需要考查前一个元素，需要进行的比较操作为n-1次即可，时间复杂度为O(n)。

最坏情况：序列是降序排列，插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，……，插入第n个元素，要考虑前 n - 1 个元素。

因此，比较次数是 1 + 2 + 3 + ... + (n - 1) = n(n-1)/2次，时间复杂度为O(n^2)。

3.4.2 交换操作

插入排序的赋值操作是比较操作的次数减去 n-1次，（因为n-1次循环中，每一次循环的比较都比赋值多一个，多在最后那一次比较并不带来赋值）。

3.4.3 时间复杂度

平均来说插入排序算法复杂度为 O(n^2)。

3.4.4 应用场景

插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，时间复杂度大致O(n)（有时比O(nlog(n))还要快），因此经常作为某些复杂算法的子算法达到改进目的。

插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充。

3.5 插入排序与选择排序算法差异

//选择排序
function selectionSort($arr){

    for($i = 0 ; $i < count($arr) ; $i ++){

        $minIndex = $i;
        for( $j = $i + 1 ; $j < count($arr) ; $j ++ )
            if( $arr[$j] < $arr[$minIndex] )
                $minIndex = $j;
        //交换
        swap($arr[$minIndex],$arr[$i]);
    }

    return $arr;
}

// 插入排序
function insertionSort($arr)
{
    for( $i = 1 ; $i < count($arr) ; $i ++ ) {
        $e = $arr[$i];
        for ($j = $i; $j > 0 && $arr[$j-1] > $e; $j--)
            $arr[$j] = $arr[$j-1];
        // j保存元素e应该插入的位置
        $arr[$j] = $e;
    }

    return $arr;
}

插入排序和选择排序最大区别是插入排序可以提前结束。插入排序在第二重循环可以提前结束（满足一定条件找到插入位置即可,假定第一个元素是有序的，也就是拿第一个元素的下一个元素与第一个元素进行比较，依此类推），理论上效率要比选择排序高。

四、更多关于O(n^2)算法

4.1 冒泡排序和希尔排序

选择排序
插入排序
冒泡排序（整体没有插入排序好，不推荐使用）
希尔排序（是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。）

4.2 希尔排序

4.2.1 希尔排序是基于插入排序的

是插入排序的一种更高效的改进版本可以使得性能提升至O(n(log^2n))(非稳定排序算法)。

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

4.2.2 算法描述

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

4.2.3 算法实现过程

将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]。

1、如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

2、将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：

排序之后变为：

3、最后以1步长进行排序（此时就是简单的插入排序了）。

4.2.4 范例代码

/**
 * 希尔排序
 * 经测试：希尔排序是普通插入排序的50倍,'改进版'插入排序的10倍
 * >> 每一次移动都表示“除以 2”
 *
 * @param $arr
 * @return mixed
 */
function shellSort($arr) {
    for ($gap = count($arr)>>1; $gap > 0; $gap>>=1)
        for ($i = $gap; $i < count($arr); $i++) {
            $temp = $arr[$i];
            for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap)
                $arr[$j + $gap] = $arr[$j];
            $arr[$j + $gap] = $temp;
        }
    return $arr;
}

PHP版源代码：`GitHub代码和测试数据`

未完待续：预写下一章：归并排序多种实现算法、快速排序及优化、双路/三路快速排序

排序算法稳定性排序算法插入排序希尔排序算法 param

程序员内功修炼之学好算法和数据结构（一）排序基础、选择排序、插入排序、希尔排序

一、排序基础（重要）

1.1 为什么要学习O(n^2)的排序算法？

1.2 排序算法的稳定性

1.2.1 稳定性

1.2.2 排序算法稳定的意义

1.3 辅助函数文件Helper.php

二、选择排序

2.1 选择排序

2.2 算法描述

2.3 范例代码

2.4 算法分析

2.4.1 比较操作

2.4.2 交换操作

2.4.3 时间复杂度

2.4.4 应用场景

三、插入排序（非常重要）

3.1 插入排序

3.2 算法描述

3.3 范例代码（推荐写法3）

3.4 算法分析

3.4.1 比较操作

3.4.2 交换操作

3.4.3 时间复杂度

3.4.4 应用场景

3.5 插入排序与选择排序算法差异

四、更多关于O(n^2)算法

4.1 冒泡排序和希尔排序

4.2 希尔排序

4.2.1 希尔排序是基于插入排序的

4.2.2 算法描述

4.2.3 算法实现过程

4.2.4 范例代码

未完待续：预写下一章：归并排序多种实现算法、快速排序及优化、双路/三路快速排序

相关推荐

一、排序基础（`重要`）

三、插入排序（`非常重要`）

3.3 范例代码（`推荐写法3`）