算法-经典排序算法(Ⅰ)

发表于   |   分类于   |  

最近又学了一章算法课，经典的几个 『O(n²)』 复杂度的算法比较。主要是 冒泡排序、插入排序、希尔排序、选择排序的比较

指数是什么

指数其实就是幂运算中的一个参数 aⁿ(a≠0) 其中 a 为「底数」， n 为「指数」。指数位于底数的右上角，这个表达式表示 「n」个「a」相乘

对数是什么

对数其实来源于指数，但是却是在指数之前先发明的，这群神人…

对数是幂运算的逆运算。 如果 N = aⁿ(a > 0, a ≠ 1) 也就是「a」的「x」次方等于「N」，那么X就是N的（以a为底数）的对数，记为： x = ㏒αN

还有个『常用对数』 是10为底的对数。

『排序算法』衡量维度

执行效率：

  • 对于执行效率衡量一般是进行复杂度分析：『最好情况复杂度』、『最坏情况复杂度』、『平均情况复杂度』
  • 一般排序算法会有一些数据的交换或者移动，这些变动次数也可以是衡量标准之一

内存消耗：

  • 对于内存的消耗可以通过『空间复杂度分析』来衡量。
  • 也可以通过原地算法来衡量。维基上的解释是：原地算法（in-place algorithm）基本上不需要额外辅助的数据结构,然而,允许少量额外的辅助变量来转换数据的算法。 在这里就是是指空间复杂度为 『O(1)』的排序算法。

稳定性：

  • 排序算法的稳定性是指在碰到相同值的情况，算法不会改变他们的先后顺序。举个例子：1,2,3,2;排序后2个2的顺序不会改变，谁在前就是在前。
  • 为什么需要稳定性？举个例子：假如当前班级需要分座位了。规则①首先按得分排，得分高的坐第一排，②得分相同的按照身高来排序，身高矮的坐第一排。再假设现在有4个人
    1
    2
    3
    4
    5
    score      length
    90         170cm
    80         160cm
    90         150cm
    90         180cm

那么我们可以先按照身高来排序，得到

1
2
3
4
150cm      90
160cm      80
170cm      90
180cm      90

然后再借助稳定的排序算法对得分进行排序就可以了，因为是稳定的 所以他们不会发生前后的移位。试想如果是不稳定的算法，在值相同的时候发生移位，有可能会导致最后的170 和 180交换也就不满足条件了。

冒泡排序

冒泡排序：Bubble Sort

根据 维基百科-冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。

排序过程：

冒泡其实就是类似气泡上浮的过程。每轮循环找到想要的值上浮到数据中它应该在的位置。

1.从第一个开始，每次取相邻的2个数比较，满足条件就交换他们的位置，然后继续取相邻比较。一轮循环结束就会确定一个值的位置。
2.然后从头在开始上一步操作，直到没有一组数据需要比较

PHP实现伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
$num = [
    6, 5, 4, 3, 2, 1
];
function bubbleSort($arr)
{
    $count = count($arr);
    // 外层分割已排序和未排序的数据
    for ($i = 0; $i < $count; $i++) {
        // 内层用来在未排序的数据中查找指定值
        // -1 是为了防止越界 比较的时候会和 j + 1比较
        for ($j = 0; $j < $count - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
            }
        }
    }
    var_dump($arr);
}
bubbleSort($num);

还有一种写法不知道该不该叫冒泡

就是每次从左边取一个数据定住，然后依次和剩余的数据比较，符合条件就交换，这样一轮下来这个『定住的位置』就是某个数据该待的位置…(好吧我也不知道怎么讲 上代码吧)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function bubbleSort2($arr)
{
    $count = count($arr);
    for ($i = 0; $i < $count; $i++) {
    	// 这样就不需要考虑数组越界的问题
        for ($j = $i + 1; $j < $count; $j++) {
            if ($arr[$i] > $arr[$j]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$i];
                $arr[$i] = $tmp;
            }
        }
    }
    var_dump($arr);
}

对于上面的代码会有个问题，当数据本来就是有有序 如 [1, 2, 3, 4, 5, 6],也是需要执行完2层嵌套循环。很浪费，所以可以改进下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function bubbleSort($arr)
{
    $count = count($arr);
    // 外层分割已排序和未排序的数据
    for ($i = 0; $i < $count; $i++) {
        // 声明一个是否有数据交换的标识，当没有数据交换的时候其实就等于全部都是有序的了
        $flag = false;
        // 内层用来在未排序的数据中查找指定值
        // -1 是为了防止越界 比较的时候会和 j + 1比较
        for ($j = 0; $j < $count - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
                $flag = true;
            }
        }
        // 如果没有数据交换=有序 就可以退出循环了
        if (! $flag) {
            break;
        }
    }
    var_dump($arr);
}

冒泡排序总结：

1.执行效率：根据上面的改进最好情况复杂度为 O(n) 也就是在数据是有序的状态下。 最坏时间复杂度为O(n²),也就是在数据从头到尾完全无序的情况下。平均时间复杂度为O(n²)

2.内存消耗:因为他的数据交换只涉及常量级别的临时空间，所以冒泡的空间复杂度是O(1)

3.稳定性：在冒泡中需要满足大于或者小于的条件才交换，不存在等于的条件，所以2个相等的值是不会交换的，也就不会改变他们的前后顺序。是稳定的排序算法。

插入排序

插入排序：Insertion Sort

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

动态图如下：

insertion_sort

排序过程：

1.首先把数据分为2个区间，『已排序区间』和『未排序区间』。
2.从未排序区间中取出一个值，然后遍历已排序区间。
3.对已排序区间进行从后往前顺序遍历，然后通过移动已经排序区间元素的位置，把新值插入到已排序区间中合适位置

PHP实现伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function insertionSort($arr)
{
    $count = count($arr);
    // 从1开始，假设下标0的元素已经放进已排序区间
    for ($i = 1; $i < $count; $i++) {
        $value = $arr[$i];
        for ($j = $i - 1; $j >=0; $j--) {
            if ($arr[$j] > $value) {
                // 这里其实只是通过赋值操作来代替移动一位
                // 所以打印出来会出现 $arr[$j] == $arr[$j + 1] 不过这个不要紧
                // $arr[$j + 1] 其实就是$arr[i] 的值，而$arr[$i]的值已经提前赋值给了$value
                // 通过这一步操作其实就实现了把元素后移的效果。
                $arr[$j + 1] = $arr[$j];
            } else {
                // 因为上面每次移动都会把当前的j位置空出来
                break;
            }
        }
        // 这里注意要 j + 1因为上面的循环j=0的时候是满足条件的会进入循环体
        // 在循环结束后j--变为了-1，所以这里要+1才能回到0下标
        $arr[$j + 1] = $value;
    }
    var_dump($arr);
}

插入排序总结：

1.执行效率：最好情况复杂度为 O(n) 也就是在数据是有序的状态下。 最坏时间复杂度为O(n²),也就是在数据从头到尾完全无序的情况下。平均时间复杂度为O(n²)，因为对于类似数组的实现，每次插入一个数的平均时间复杂度是O(n),移动重复了N次插入，所以插入排序的平均时间复杂度为O(n²)

2.内存消耗:因为他的数据交换只涉及常量级别的临时空间，并不需要额外的内存空间，所以插入排序的空间复杂度是O(1)

3.稳定性：是稳定的，遇到相同的值并不会改变他们的前后顺序。

希尔排序

希尔排序：(Shell Sort) 是插入排序的一种更高效的改进版本。

他是在插入排序的基础上进行了改进，通过提高步长来减少插入排序的比较移位操作来提供效率。在某些情况下可以把性能提高到 O(n㏒²n),比较插入排序的 O(n²)有了很大的提高。

排序过程：

1.选择较大步长，一般使用待排序的元素个数除2来获得当前的步长 gap
2.然后从头开始，单位步长内的数据算一个小组 最终会有 gap 个小分组
3.然后依次对这些小分组进行 插入排序 操作。
4.然后重复上面3步操作，使用上一步的步长继续除2来得出新的步长。一直到步长为1
5.此时希尔排序恢复到普通的插入排序，不过大部分的数据经过上面已经很有序了。最后进行一次全部的插入排序就完成了。

大概图如下：

shell_sort

PHP实现伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function shellSort($arr)
{
    $count = count($arr);
    // 最外层循环控制增量步长
    // 向上取整的话当是小数的时候 会得出1，
    // 然后1就死循环了 1 / 2 向上取整还是1...
    for ($gap = floor($count / 2); $gap >= 1; $gap = floor($gap / 2)) {
        // 这里的2层循环就是插入排序了和插入排序代码是一样的
        // 只不过普通的插入排序步长是1，这里换成计算出来的步长gap即可
        for ($i = $gap; $i < $count; $i++) {
            $value = $arr[$i];
            for ($j = $i - $gap; $j >= 0; $j = $j - $gap) {
                if ($arr[$j] > $value) {
                    $arr[$j + $gap] = $arr[$j];
                } else {
                    break;
                }
            }
            $arr[$j + $gap] = $value;
        }
    }
    var_dump($arr);
}

希尔排序总结：

1.执行效率：

  • 最好情况复杂度为 O(n) 选择合理的步长也就是Hibbard增量（1, 3, 5, 7）。
  • 最坏时间复杂度也受步长影响。在最坏情况下的最坏复杂度是O(n²),也就是在数据增量为1的时候，退化成普通的插入排序。而插入排序最坏时间复杂度是 O(n²)，所以希尔排序最坏时间复杂度是O(n²)。 在最坏情况下的最好复杂度是使用合理步长Hibbard增量（1, 3, 5, 7）可以把效率提高到O(n㏒²n)。(我自己也快晕了…就是最坏情况没法定和步长有关系)
  • 平均时间复杂度也受步长的影响。总体平均复杂度为 O(n㏒²n)。不过也是各种争论。

2.内存消耗:它和插入排序一样，数据交换只涉及常量级别的临时空间，并不需要额外的内存空间，所以希尔排序的空间复杂度是O(1)

3.稳定性：是不稳定的，因为每次的步长取小分组，有可能在中间操作因为步长区间的问题，导致某些相同的值已经换了位，所以是不稳定的。

选择排序

选择排序：Selection Sort

选择排序是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

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

动态图如下：

selectionSort

排序过程：

1.把待排序数据分为2个区间，已排序区间和未排序区间
2.每次从未排序区间中找到最小值（或最大值）放入已排序区间末尾
3.重复直到没有数据

PHP实现伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function selectionSort($arr)
{
    $count = count($arr);
    // 这里使用count - 1 因为当剩最后2个的时候，倒数第二个排好了，剩下的那个就是末尾的元素
    // 无序在遍历了，所有才有 n 个元素的选择排序 最多进行 n - 1次遍历的结论
    for ($i = 0; $i < $count - 1; $i++) {
        $min = $i;
        for ($j = $i + 1; $j < $count; $j++) {
            if ($arr[$min] > $arr[$j]) {
                $min = $j;
            }
        }
        if ($j != $min) {
            $tmp = $arr[$i];
            $arr[$i] = $arr[$min];
            $arr[$min] = $tmp;
        }
    }
    var_dump($arr);
}

选择排序总结：

1.执行效率：根据上面的改进最好情况复杂度为 O(n²)，因为即使数据是有序的，它每次都要遍历完内层循环才能确定谁是最小值，所以他的复杂度是O(n²)。 最坏时间复杂度为O(n²)也一样，不论数据是否有序都要遍历完内层循环。平均时间复杂度为O(n²)，这个就不用说了。

2.内存消耗:因为他的数据交换只涉及常量级别的临时空间和固定的赋值，所以选择排序的空间复杂度是O(1)

3.稳定性：是不稳定的。举个例子假如有数据 [1, 2, 2, 1].因为他每次都是找到最小的值然后交换，这样当第二次循环找到最小值还是1，然后1就和第一个蓝色的2交换了位置，可以发现，蓝色的2和红色的2位置发生了改变。 所以选择排序是不稳定的算法。

冒泡排序 VS 插入排序

冒泡排序和插入排序虽然都是O(n²)的算法，但是在平时使用中，确实插入排序使用的比冒泡多。

因为在冒泡中，当找到满足条件的时候会进行数据交换，也就是下面这段代码

1
2
3
4
5
6
7
if ($arr[$j] > $arr[$j + 1]) {
    $tmp = $arr[$j];
    $arr[$j] = $arr[$j + 1];
    $arr[$j + 1] = $tmp;
    $flag = true;
}

而插入排序在满足条件的时候只是做数据的后移 如下代码

1
2
3
4
5
if ($arr[$j] > $value) {
    $arr[$j + 1] = $arr[$j];
} else {
    break;
}

所以从理论上来说交换数据需要3步操作，而后移需要一步操作。再假设每一步都是1个单位执行时间，那么冒泡需要3个单位执行时间，插入需要1个执行时间。所以我们更倾向于使用插入排序。

总结

最好复杂度 最坏复杂度 平均复杂度 空间复杂度 算法稳定性
冒泡排序 O(n) O(n²) O(n²) O(1) Yes
插入排序 O(n) O(n²) O(n²) O(1) Yes
选择排序 O(n²) O(n²) O(n²) O(1) NO
希尔排序 O(n) O(n²) / O(n㏒²n) ? O(1) NO

在实际中冒泡和选择排序确实很少用到，他们更多是拿来开拓思维。

-------------The End-------------