深入理解排序算法(一):插入排序、冒泡排序、选择排序

写在前面:开始系统地梳理知识,暂且先把一些想法记录下来,后续有时间再做进一步整理和完善,比如展开文字、配以实例和图片等。

排序算法是最常用的算法之一,分析排序算法的三个重要指标:时间复杂度、空间复杂度以及稳定性。

基于比较的排序算法时间复杂度一般在O(nlogn)到O(n2)之间。

空间复杂度为O(1)的排序称为就地(in-place)排序,或者原址排序,非就地排序的空间复杂度一般为O(n)。

稳定性指的是序列中相等的元素在排序后的前后位置是否会发生变化,如果不变则排序算法是稳定的(stable),否则为不稳定。

排序可以按从小到大,也可以按从大到小的顺序排列,后面我们在讨论和实现算法时都以前者为准。

插入排序、冒泡排序、选择排序是三种最简单直接的排序算法,都是基于比较+交换,由内外两层循环实现,其中外循环次数为n-1,内循环次数跟外循环的循环变量相关,平均时间复杂度为O(n2),空间复杂度为O(1)。

一、插入排序

插入排序算法跟我们玩扑克牌时的处理方法类似,它依次处理每个待排序的元素,将其与前面已经排好序的子序列进行比较,然后插到正确的位置。

算法用C++实现如下:

插入排序的最佳时间复杂度为O(n),这种情况序列本身是按正序排列。

插入排序是稳定的,因为只有当后面的元素小于前面的元素是才会发生交换,如果相等,则相对位置不会发生改变。

在实际应用中,有一种动态的插入排序,所谓动态指的是元素是动态的增加的,即已有序列是排好序的,新增加的元素将被插入到合适的位置,使得插入后继续保持有序。既然已有序列是有序的,那么在寻找插入位置时就可以使用二分查找法,以提高插入效率。在C++中,可以使用upper_bound函数寻找插入位置。

二、冒泡排序

冒泡排序的思路是从序列后端开始,依次比较相邻的两个元素,如果后面的元素比前面的元素小,就将其交换到前面,每一趟都会挑出当前未排序子序列中最小的元素放到前面,整个过程就像水底的气泡浮到水面一样,故形象的称为冒泡排序。

算法用C++实现如下:

可以看到,外循环仍然为n-1次,内循环从最后一个元素开始,依次与前面的元素比较,由于最前面的是已经排好序的,所以内循环的结束条件跟外循环的循环变量相关。

插入排序每一趟内循环是为当前由外循环所固定的目标元素寻找合适的位置,也就是说有一个固定的待排序元素。而冒泡排序则不是,它的每一趟内循环是为了找到当前子序列中的最小元素,所以没有固定目标,必须两两相互比较,这也就体现到内循环的结束条件处理上,同时也就导致了冒泡排序的最佳、最差、平均时间复杂度均为O(n2)。

冒泡排序也是稳定的,因为当两个元素相等时不会发生交换。

三、选择排序

选择排序的思路是每一趟排序都从子序列中选出最小的元素将其放到前面的正确位置上(与该位置的元素进行交换)。

选择排序可以看作是冒泡排序的改进,因为冒泡排序交换的次数太多,选择排序则是找到正确元素的索引后,最后才进行交换。

算法用C++实现如下:

这里为了跟冒泡排序对比,特意将内循环的循环过程写得跟冒泡排序一样,实际上内循环也可以从前往后遍历,因为最终都是为了找到最小元素的位置而已,而且这样更符合我们的思维习惯,见下面的代码:

选择排序不是稳定的,因为在发生交换时,可能会改变相等元素的相对位置,比如{2,2,1}这样的序列,第一次交换就会把排在前面的2给挪到后面。而插入排序、冒泡排序的交换只发生在相邻的不相等元素之间,所以不会改变相等元素的相对位置。

对于插入排序,也可以像选择排序这样,先找到正确的插入位置后,再进行交换。不过这样修改后,也会变成不稳定的。

实际上,稳定性跟序列的数据结构有很大关系,如果序列的数据结构采用链表,选择排序将变成稳定的,因为我们不需要通过交换来改变元素顺序,而可以直接改变指针将元素插入到正确位置。

分享到

发表评论

电子邮件地址不会被公开。 必填项已用*标注