冒泡排序、插入排序、选择排序

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

例子

假设要对一组数据排序（数组）：4，5，6，3，2，1

冒泡过程（由小到大排序，每次冒泡实质就是拿出最大的元素放到数组末尾）：

第一次冒泡：

1、拿 4 和 5 对比，4 < 5 所以不做元素互换操作，此时数组为 4，5，6，3，2，1

2、拿 5 和 6 对比，5 < 6 所以不做元素互换操作，此时数组为 4，5，6，3，2，1

3、拿 6 和 3 对比，6 > 3 所以将 6 和 3 位置互换，此时数组为 4，5，3，6，2，1

4、拿 6 和 2 对比，6 > 2 所以将 6 和 2 位置互换，此时数组为 4，5，3，2，6，1

5、拿 6 和 1 对比，6 > 1 所以将 6 和 1 位置互换，此时数组为 4，5，3，2，1，6

经过这次冒泡，元素 6 的位置就是最终排序后的位置了。

第二次冒泡的过程中，因为数组最后一个元素已经是最大的元素，因此我们只需要对开头的 5 个元素排序即可。

第二次冒泡，此时数组为 4，5，3，2，1，6 ：

1、拿 4 和 5 对比，4 < 5 所以不做元素互换操作，此时数组为 4，5，3，2，1，6

2、拿 5 和 3 对比，5 > 3 所以交换这两个元素的位置，此时数组为 4，3，5，2，1，6

3、拿 5 和 2 对比，5 > 2 所以交换这两个元素的位置，此时数组为 4，3，2，5，1，6

4、拿 5 和 1 对比，5 > 1 所以交换这两个元素的位置，此时数组为 4，3，2，1，5，6

到此，第二次冒泡结束（因为数组末尾的元素在第一次冒泡的时候已经确定的了），经过这次冒泡，倒数第二个元素也确定了下来。

我们一共有 6 个元素，所以还需要进行 4 次冒泡操作才能得到最后的排序结果。

冒泡排序优化

因为我们在冒泡过程中，实际上是对比相邻的两个元素，如果 $arr[$i] > $arr[$i + 1]，那么交换这两个元素的位置。

也就是说，如果一次冒泡过程中，完全没有发生数据交换，说明数组里面的数组都是从小到大有序的。这个时候我们就可以直接退出冒泡过程了。

PHP 实现

$array = [1, 5, 3, 7, 9, 4, 20, 100, 55, 67, 66];

function bubble_sort($arr)
{
    $n = count($arr);
    if ($n == 1) return $arr;

    // 是否有发生数据交换操作，如果一次冒泡中没有发生数据交换操作说明已经有序，可以直接退出冒泡过程
    $flag = true;

    // 冒泡操作
    for ($i = 0; $i < $n; $i++) {
        // $i 是已经排好序的元素个数，-1 是要拿 $arr[$j] 和 $arr[$j + 1] 比较，这样只要到前一个元素就可以处>理完全部数据
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
                $flag = false;
            }
        }

        if (!$flag) break;
    }

    return $arr;
}

var_export(bubble_sort($array));

问题

冒泡排序是否是原地排序算法？

冒泡的过程中，只有相邻数据位置互换，不需要开辟新的空间来进行操作，所以是原地排序算法。

冒泡排序是否是稳定的算法？

冒泡过程中，我们只在 $arr[$j] > $arr[$j + 1] 的时候，才互换位置，相等的两个元素，位置不会变动，所以是稳定的算法。

冒泡排序的时间复杂度是多少?

最好的情况下，数组已经有序，只需要进行一次冒泡即可，时间复杂度是 O(n)。

最坏的情况下，完全逆序，冒泡过程总遍历次数为 (n - 1) + (n - 2) + ... + 1，也就是 n*(n-1)/2，所以时间复杂度是 O(n²)。

插入排序

先看一个简单的问题。一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？很简单，我们只要遍历数组，找到数据应该插入的位置将其插入即可。我们可以通过这种方法保持集合中的数据一直有序。

插入排序的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

在插入排序中，我们会将数据列表划分为两个部分，一部分是有序区间，另一部分是无序区间。插入排序的过程就是，遍历无序区间里面的每一个元素，在有序区间里面遍历找到一个合适的位置进行插入，直到无序区间的数据全部插入到有序区间里面，这个时候数据列表就完全有序了。

初始状态下，一般会将第一个元素 $arr[0] 视作有序区间，然后 $arr[1...n-1] 为无序区间，我们会遍历 $arr[1...n-1] 中的每一个元素，拿来插入到有序区间中，直到遍历完无序区间的全部数据。

例子

假设要对一组数据排序（数组）：4，5，6，3，2，1，按顺序排序。

开始的时候，我们的有序区间是 $arr[0...0]，无序区间是 $arr[1...n-1]。

第一次遍历，我们拿到无序区间的第一个元素 5($arr[1])，将其与 4 对比，5 > 4，所以位置不变，因为有序区间只有一个元素，所以此次遍历结束。但是此时有序区间已经是 $arr[0...1]，无序区间是 $arr[2...n-1]。

第二次遍历，我们拿到无序区间的第一个元素 6($arr[2])，我们将其与有序区间的最后一个元素，也就是 5 对比，发现 6 比 5 大，是有序区间最大的元素，所以此次遍历结束。但是此时有序区间已经是 $arr[0...2]，无序区间是 $arr[3...n-1]。

我们这里是从有序区间的最后一个元素开始对比，但从有序区间第一个元素开始对比也是可以的。只是操作上稍有不同，如果从第一个元素开始对比，在我们找到合适的位置的时候，需要先将有序区间剩余的元素往后挪动即可。但是需要注意这种情况下对结果稳定性的影响，也就是说，这种情况下，我们比较的时候需要使用 >= 或 <= 这种包含相等情况的也进行位置互换操作。这样才能保证排序结果的稳定性。

如此遍历，直到无序区间的元素被全部遍历完毕。

PHP 实现

function insertion_sort($arr)
{
    $n = count($arr);
    if ($n <= 1) return $arr;

    // 0~$i-1 为有序区间
    // $i~$n-1 为无序区间
    for ($i = 1; $i < $n; $i++) {
        $value = $arr[$i];
        // 查找插入的位置
        for ($j = $i - 1; $j >= 0; $j--) {
            if ($arr[$j] > $value) {
                $arr[$j + 1] = $arr[$j]; // 数据移动
            } else {
                break;
            }
        }
        // 到这里的时候说明: 1. $arr[$j] <= $value(找到了插入的位置) 或 2. $j = -1 (循环终止，$value 是目前有序区间最小的数)
        $arr[$j + 1] = $value; // 插入数据
    }

    return $arr;
}

var_export(insertion_sort($array));

问题

插入排序是原地排序算法吗？

在插入排序的过程中，我们并不需要额外的存储空间，所以空间复杂度为 O(1)，也就是说，插入排序是一个原地排序算法。

插入排序是稳定的排序算法吗?

在插入排序中，对于值相同的元素，我们并不交换位置，可以保持原有的前后顺序不变，所以是稳定的排序算法。

插入排序的时间复杂度是多少？

最好的情况下，如果数据已经是有序的，我们并不需要移动任何数据，每次只需要比较一次就能确定插入的位置。这种情况下，时间复杂度是 O(n)。注意这里是从尾到头遍历已经有序的数据。

最坏的情况下，数据是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，需要移动数据的次数为 O(n²)，所以最坏情况时间复杂度为 O(n²)。

我们在数组中插入一个数据的平均时间复杂度是 O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n²)。

选择排序

选择排序和插入排序有点类似，在排序的过程中，数据也被划分成有序区间和无序区间。但是选择排序是每次从未排序的区间里面选择最小的元素，将其放到已排序区间的末尾。

PHP 实现

function selection_sort($arr)
{
    $n = count($arr);
    if ($n <= 1) return $arr;

    for ($i = 0; $i < $n - 1; $i++) {
        // 假设一开始最小的元素都是未排序区间的第一个元素，如果有更小的，则替换
        $min = $arr[$i];
        $minIndex = $i;
        // 选择最小元素，获取其值和下标
        for ($j = $i; $j < $n; $j++) {
            if ($arr[$j] < $min) {
                $min = $arr[$j];
                $minIndex = $j;
            }
        }
        // 将最小的元素跟未排序区间的第一个元素交换
        $arr[$minIndex] = $arr[$i];
        $arr[$i] = $min;
    }

    return $arr;
}

var_export(selection_sort($array));

问题

选择排序是原地排序算法吗？

在选择排序的过程中，只需要两个变量来存储最小元素的值和最小元素的下标，不需要其他额外的空间，所以是原地排序算法。

选择排序是稳定的算法吗？

由于每次选择排序会将最小元素跟未排序区间第一个元素互换，这个互换过程会改变原有数据的顺序，所以是不稳定的算法。

选择排序的时间复杂度是多少?

选择排序所需时间为 n + (n - 1) + ... + 1，即 n(n + 1)/2，所以时间复杂度是 O(n²)。

冒泡和插入时间复杂度一样，为什么插入排序更受欢迎？

因为每一次循环过程中，冒泡排序需要 3 个赋值操作，而插入排序只需要一个。

// 冒泡排序中数据的交换操作：
if (a[j] > a[j + 1]) { // 交换
    int tmp = a[j];
    a[j] = a[j + 1];
    a[j + 1] = tmp;
    flag = true;
}

// 插入排序中数据的移动操作
if (a[j] > value) {
    a[j + 1] = a[j]; // 数据移动
} else {
    break;
}

所以，虽然冒泡排序和插入排序在时间复杂度上是一样的，都是 O(n²)，但是如果我们希望把性能优化做到机智，那肯定首选插入排序。插入排序的算法思路也有很大的优化空间 => 希尔排序。

小结

冒泡排序、插入排序、选择排序对比

	是否是原地排序？	是否稳定？	最好最坏平均
冒泡排序	是	是	O(n) O(n²) O(n²)
插入排序	是	是	O(n) O(n²) O(n²)
选择排序	是	否	O(n²) O(n²) O(n²)

这三种时间复杂度为 O(n²) 的排序算法中，冒泡排序、选择排序，可能就纯粹停留在理论的层面了，学习的目的也只是为了开拓思维，实际开发中应用并不多，但是插入排序还是挺有用的。有些编程语言的排序函数实现原理会用到插入排序算法。

这三种排序算法，实现代码都非常简单，对于小规模数据的排序，用起来非常高效。但是在大规模数据排序的时候，这个时间复杂度还是稍微有点高，所以更倾向于使用时间复杂度为 O(nlogn) 的排序算法。