-
原地排序(Sorted in place)。原地排序算法， 就是特指空间复杂度是O(1)的排序算法。我们今天讲的三种排序算法，都是原地排序算法。
-
排序算法的稳定性： 仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，我们还有一个重要的 度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等 元素之间原有的先后顺序不变。 我通过一个例子来解释一下。比如我们有一组数据2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。 这组数据里有两个3。经过某种排序算法排序之后，如果两个3的前后顺序没有改变，那我们就把这 种排序算法叫作稳定的排序算法;如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序 算法。
冒泡排序(Bubble Sort)：
(相邻元素交换顺序）
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)， 是一个原地排序算法。
第二，冒泡排序是稳定的排序算法吗? 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有 相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以 冒泡排序是稳定的排序算法。
第三，冒泡排序的时间复杂度是多少?
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以 最好情况时间复杂度是O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行n 次冒泡操作，所以最坏情况时间复杂度为O(n2)。
插入排序(Insertion Sort)
（第一个数是排序好的和后面是无序的数字，左边是排序好的，右边是没排序好的，从右边拿第一个数和左边倒叙循环判断插入到指定位置）
首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元 素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到 合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元 素为空，算法结束。
第一，插入排序是原地排序算法吗?
从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。
第二，插入排序是稳定的排序算法吗? 在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后 面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。 第三，插入排序的时间复杂度是多少? 如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里 面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复 杂度为O(n)。注意，这里是从尾到头遍历已经有序的数据。 如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数
2
据，所以最坏情况时间复杂度为O(n2)。 还记得我们在数组中插入一个数据的平均时间复杂度是多少吗?没错，是O(n)。所以，对于插入排 序来说，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复 杂度为O(n2)。
选择排序(Selection Sort)
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会 从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
选择排序是一种不稳定的排序算法。
网友评论