漫画:什么是选择排序算法?

选择排序是一种简单直观的算法,今天我们聊聊选择排序的思想,代码以及复杂度

排序思想

一天,小一尘和师傅下山去了,在集市中路经一个水果摊,只见水果摊上摆着色泽基本相同但大小不一的苹果

image-20230213173955468

image-20230213174008490

image-20230213174020361

师傅答应后,小一尘就去水果摊前买苹果了

他拿了一个袋子,从众多苹果中挑了一个最大的装入袋子,然后又从剩下的苹果中挑出了最大的放入口袋,就这样挑了几个苹果然后结账

小一尘买完苹果后,走到师傅面前

image-20230213174034090

image-20230213174045866

image-20230213174059645

慧能:这其实就是选择排序的思想,选择排序就是不断地从未排序的元素中选择最大(或最小)的元素放入已排好序的元素集合中,直到未排序中仅剩一个元素为止。

买个苹果也不忘给我传授知识,一尘心里甚是感激

排序代码

image-20230213174110770

image-20230213174127248

一尘眉头一紧

心中想到:

初始时肯定给我一个无序数组

image-20230213174141782

我先从这些元素中选出一个最小的(或最大的),和第一个元素进行交换,这样第一个元素就是最小的,第一个元素位置就变成有序区间了

image-20230213174151765

同理,在剩下的无序区间选择最小的元素,将最小元素与无序区间的第一个元素进行交换,交换后原来无序区间的第一个元素就变为有序区间的最后一个元素了,有序区间递增一

image-20230213174202657

以此类推,全部元素就可以通过这样不断地选择以及交换排完序

那如何选出最小的一个元素呢?

很容易想到:先随便选一个元素假设它为最小的元素(默认为无序区间第一个元素),然后让这个元素与无序区间中的每一个元素进行比较,如果遇到比自己小的元素,那更新最小值下标,直到把无序区间遍历完,那最后的最小值就是这个无序区间的最小值

image-20230213174214088

image-20230213174227219

想到这里,一尘已经胸有成竹了,随手写出了如下代码

image-20230213174240406

image-20230213174253092

时间复杂度

image-20230213174305360

这段代码的时间复杂度不难,和冒泡排序,插入排序的非常像,一尘心里想到

image-20230213174318605

设有 n 个元素(n = arr.length)

代码执行的时间都花费在内层for循环中的比较语句和外层for循环里的交换语句

外层for循环执行 n-1 次,那么交换(swap)就执行 n-1 次,时间复杂度为O(n)

内层for循环中的比较语句执行多少次呢?

i = 0 时,比较 n – 1 次

i = 1 时,比较 n – 2 次

i = n-2 时,比较 1 次

则一共比较了

image-20230213174330555

image-20230213174343141

稳定性

image-20230213174354133

image-20230213174406752

image-20230213174418398

image-20230213174429007

image-20230213174439621

image-20230213174450786

一尘和师傅提着苹果走向了回家的路

发表回复

后才能评论