[关闭]
@liweiwei1419 2019-01-25T08:56:46.000000Z 字数 3949 阅读 1286

【算法日积月累】1-选择排序

选择排序 算法




“算法”的入门,从“排序算法”开始,希望通过“排序算法”这一部分的学习,能够让我们认识到“算法”的威力,“算法”不仅仅只存在与我们的面试中(那时只是因为我不知道“算法”而已),“算法”无处不在,“算法”很有用。

下面是一些说明:

1、会直接使用“空间复杂度”和“时间复杂度”的概念,不妨先有个印象,实在纠结的话,可以去翻翻书,“空间复杂度”和“时间复杂度”最多的应用就在于比较不同算法的优劣;

2、“排序算法”这一章节为了方便说明,使用的例子都是以“整数数组”为例,并且是“升序排序”,学习过 Java 语言的朋友就知道,待排序的也可以是对象,只要实现了相关的接口,实现了相应的比较规则,就可以进行排序。

我们选择“选择排序”作为算法入门的开篇。理由如下:

1、“选择排序”算法的思想十分简单,非常接近我们的思维方式:先找最小的数、再找第 2 小的数,依次类推,最后剩下的就是数组中最大的元素;

2、“选择排序”的实现也很简单。

“选择排序”的思想:减而治之

“选择排序”的思想说起来是很简单的,就是把一个问题划分成两个部分:

1、其中一个部分是一个比原始问题小很多的,很容易解决的问题;

2、另一个部分是原始问题的一个子问题,与原始问题的区别就是,这个子问题比原问题看起来少了那么一些。

这就好比“愚公移山”,“移山”这个庞大的工程,在愚公看来,他每次一凿一斧头,虽然看起来微不足道,但是山就那么大,山上的石头不会越挖越多,每次挖一点,子子孙孙挖下去,山总会被挖完。“减而治之”就是这么一个朴素的思想。

应用于“选择排序”,即我们每一次把数组中的元素看一遍,找到一个最小的数,这个数就一定是排好序后放在第 1 个的数,那么我们在剩下的数里就继续找最小的数,一直这样做下去,每一轮看的数都比前一轮看的数的数量少 1,未排定的数会越来越少,直至没有。

这是一个很重要的思想,算法中的使用得“递归”正是“减而治之”的体现。

通过具体例子理解“选择排序”的思想

思想:不断地选择剩余元素之中的最小者。

image-20190111200853617

“选择排序”算法的特点

1、每一轮交换都能排定一个元素,交换的总次数是固定的;

说明:“交换的总次数”等于“元素的总数 - 1”,因此算法的时间复杂度取决于比较的次数;

2、运行时间和输入无关,即:一个“已经有序”的数组、一个所有的元素都相等的数组、一个元素随机排列的数组所用的排序时间是一样的;

说明:后续我们会编写一些测试用例,比较不同的算法在不同的测试用例上的运行时间。这些测试用例中,就有以下 种。

(1)一个“已经有序”的数组:例如:[4, 5, 6, 8, 9, 10],以后我们学习的排序算法中,就有一种算法名叫“插入排序”就能检测出数组是不是有序的,极端情况下,“插入排序”算法看一遍数组中的元素,就知道数组已经有序了,后续就什么都不用做了。而“选择排序”得一遍又一遍看数组的元素好几遍,“几乎是”有多少个数,就会看数组多少遍,每一遍选出当前没有排定元素中的最小者;

(2)一个所有的元素都相等的数组,例如:[6, 6, 6, 6, 6, 6]

(3)一个元素随机排列的数组,就是我们一般意义下,杂乱无序的数组,例如:[8, 18, 10, 6, 5, 4, 20]

3、数据移动是最少的。

这点应该说是“选择排序”的优点了,如果我们的排序任务对交换操作非常敏感,不妨考虑“选择排序”。

例如:我们待排序的是码头上的集装箱,交换集装箱的成本是很高的,此时“选择排序”就是最好的选择。

小贴士:这一部分内容不需要记住,等到后面接触了“插入排序”、“归并排序”、“快速排序”等其它排序算法以后,再与“选择排序”进行比较,就不难理解了。

“选择排序”算法实现

Python 实现1:

  1. def swap(nums, idx1, idx2):
  2. if idx1 == idx2:
  3. return
  4. temp = nums[idx1]
  5. nums[idx1] = nums[idx2]
  6. nums[idx2] = temp
  7. def select_sort(nums):
  8. """
  9. 选择排序,记录最小元素的索引,最后才交换位置
  10. :param nums:
  11. :return:
  12. """
  13. l = len(nums)
  14. for i in range(l):
  15. min_index = i
  16. for j in range(i + 1, l):
  17. if nums[j] < nums[min_index]:
  18. min_index = j
  19. swap(nums, i, min_index)

说明:交换两个数组中的元素,在 Python 中有更简单的写法,这是 Python 的语法糖,其它语言中是没有的。

Python 实现2:主体部分和“Python 实现1”是一样的。

  1. def select_sort(nums):
  2. """
  3. 选择排序,记录最小元素的索引,最后才交换位置
  4. :param nums:
  5. :return:
  6. """
  7. l = len(nums)
  8. for i in range(l):
  9. min_index = i
  10. for j in range(i + 1, l):
  11. if nums[j] < nums[min_index]:
  12. min_index = j
  13. nums[i], nums[min_index] = nums[min_index], nums[i]

这就是“选择排序”算法。

如果你看到自己编写的程序不正确,可以在程序中增加打印输出,帮助你调试程序:

image-20190111201433272

时间复杂度与空间复杂度

时间复杂度:

分析:第 1 轮要看 个元素;

第 2 轮要看 个元素;

第 3 轮要看 个元素;

……

轮要看 个元素;

对它们求和,用等差数列的通项公式。不过其实你也不用计算它,“时间复杂度”的计算我们只看次数最高的,所以“选择排序”是平方时间复杂度。

空间复杂度:

分析:我们在交换两个数组元素位置的时候,使用了 个辅助的空间。

热身练习

是不是觉得很简单,后面难度会一点一点加上来。此时,我们不妨做一些热身的练习,我们后面会用到。这些练习只是减轻一点我们后面编写测试用例的工作量,自己设计函数参数就好。

练习1:编写三个函数,分别生成上文中提到的 种类型的数组,要求能够自定义生成数组的大小,这样我们以后编写测试用例的时候,就可以使用这些函数了。

练习2:编写一个函数,判断一个数组是否是升序排序。这个函数用于判断我们的算法是否正确。

补充知识

以下补充的知识是针对零基础的朋友们的,因为我也是零基础过来的,觉得这些东西可以说一下。

1、交换两个变量的值

交换两个变量的值,在排序中是常见的操作,并且也是程式化的,特别好记。先给出 Java 的写法,再给出 Python 的写法,最后给出“不是人的写法”。

Java 写法:

  1. int temp = a;
  2. a = b;
  3. b = temp;

说明:这段代码其实很好理解,要交换两个变量的值,给要让变量 a 把位置让出来,即 int temp = a,然后把另一个变量 b 的值复制给 a,即 a = b,最后把之前 a 放在 temp 里的值赋给 b。这么说比较拗口,但其实我每次写这段代码的时候,都不用想这个过程的。因为这段代码有规律可循:首先引入一个辅助变量 temp,这是必要的,然后就开始“首尾相接”了,你们看一下,是不是这个特点,最后接回 temp,记住这个规律就可以了。在 Python 中是这样写的:

Python 写法1:

  1. temp = a
  2. a = b
  3. b = temp

不过,Python 是一门神奇的编程语言,它提供了语法糖。

使用 Python 语法糖交换两个变量的值

  1. a, b = b, a

就可以交换两个变量的值,不妨动手验证一下:

image-20190112140336597

是不是很酷,Python 的写法有的时候更像伪代码,更符合人的思维,但我没有说 Python 更好的意思。其实 Python 解释器在后台也是引入了辅助变量完成两个变量的交换。其实,交换两个变量的值,有更高效的做法,下面给出两个交换变量的代码,这两种方法都不用引入辅助变量,相信聪明的你一定不难理解。

基于加减法交换两个变量的值

image-20190112141022074

基于异或运算交换两个变量的值

image-20190112141224873

这里利用到了异或运算的特点:异或运算可以理解成不进位的加法。那么一个数两次异或同一个数,就和原来的数相等。上面基于异或运算交换两个变量的值就利用这个性质。如果你还不熟悉异或运算,不妨查阅一些资料。

2、Java 和 Python 语言中比较器的实现

前面我们说到了,我们为了突出排序算法的思想,将所有的例子仅限在数组排序中。事实上 Java 和 Python 这些面向对象的编程语言都支持对象的排序,只要给它们定义相应的比较规则即可。有两种方式,Python 和 Java 都是支持的:

(1)为对象添加用于比较的函数

  1. def __cmp__(self, other):
  2. pass

定义这个魔法函数,就可以使用对象集合进行排序了。

如果你觉得给对象添加用于比较的函数,这种做法的侵入性比较强(因为修改了类),那么你可以在排序的方法中,传入比较规则。

(2)在排序的方法中,传入比较规则

3、注意到我们每一轮都要在剩下没有排定的数中,找到一个最小的数,我们都会把剩下的数看一遍,以后我们会接触到一个很常用的数据结构,叫“最小堆”,“最小堆”可以很快地告诉我们一个集合中的最小者,于是“选择排序” + “堆”就成为了“堆排序”。

(完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注