enter image description here

讲解

enter image description here

步骤0 为初始状态,此时所有元素均属于未排序部分。

在步骤1 中,我们找出未排序部分最小值的位置(minj=6),然后将该位置的元素A6 与未排序部分的起始元素A0 进行交换。这样一来,已排序部分就增加了一个元素。

在步骤2 中,找出未排序部分最小值的位置(minj=5),然后将该位置的元素A5与未排序部分的起始元素A1 进行交换。后面的步骤同理,从数组开头按由小到大的顺序逐个确定每个位置的值。

实现选择排序法时需要的主要变量如图3.7 所示。

enter image description here

在每一轮i 的循环中,通过j 自增来遍历A[i] 到A[N-1],从而确定minj。确定minj 后,让起始元素A[i] 与最小值元素A[minj] 进行交换。

考察

假设现在有一组由数字和字母组成的数据,我们试着用选择排序法对其进行升序排列。在如图3.8 所示的例子里,我们“以数字为基准”进行排序,该排序数组中2 个元素带有数字“3”,初始状态下其顺序为3H → 3D。

enter image description here

我们会发现,排序结束后这两个元素的顺序反了过来,变成了3D → 3H。也就是说,由于选择排序法会直接交换两个不相邻的元素,所以属于不稳定的排序算法。

然后再来看看选择排序法的复杂度。假设数据总数为N,那么无论在何种情况下,选择排序法都需要进行(N-1)+(N-2)+…+1=(N²-N)/2 次比较运算,用于搜索未排序部分的最小值。因此该算法的复杂度与N² 基本成正比,即复杂度数量级为O(N²)。

现在,让我们回过头来看看这三种排序算法(冒泡、选择、插入),比较一下它们的特征。

冒泡排序法与选择排序法相比,一个从局部入手减少逆序元素,一个放眼大局逐个选择最小值,二者思路大不相同。但是,它们又都有着“通过i 次外层循环,从数据中顺次求出i 个最小值”的相同特征。相对地,插入排序法是通过i 次外层循环,直接将原数组的i 个元素重新排序。另外,不含flag 的简单冒泡排序法和选择排序法不依赖数据,即比较运算的次数(算法复杂度)不受输入数据影响,而插入算法在执行时却依赖数据,处理某些数据时具有很高的效率。

参考答案

enter image description here

评论

本文目前还没有评论……

我要评论

需要登录后才能发言
登录未成功,请修改提交。