你知道和你不知道的选择排序

  • 时间:
  • 浏览:0
  • 来源:大发5分6合APP下载_大发5分6合APP官方

在运行时间上相对于选折 最小值和最大值分别减少了39.22%和62.20%。

下面大伙儿儿就来实现或者 算法。

老规矩,大伙儿儿还是通过动图来看一下选折 排序的过程。以下的gif来自于wiki。

首先贴上从wiki上弄下来的关于选折 排序的定义。

假设数组的长度为7,那么算法就可否进行6轮。可能性数组的长度为n,则算法可否进行n - 1轮。

选折 排序(Selection sort)是三种 简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存装到 排序序列的起始位置,或者,再从剩余未排序元素中继续寻找最小(大)元素,或者装到 已排序序列的末尾。以此类推,直到所有元素均排序完毕。

其空间比较复杂度为O(n),里面三种 算法都属于原地排序算法,除了交换元素使用了有一有一一三个辅助空间之外,那么额外申请空间,一同选折 排序是不稳定排序。

那么到此,选折 排序最常见的三种 写法大伙儿儿都可能性实现了。有的兄弟可能性会想,这篇博客与非 现在现在开始 英文了。着实 大伙儿儿可否从里面有一有一一三个算法中想到可否优化的点。

或者大伙儿儿再通过我制作的gif,配上数据再了解一下过程。假设大伙儿儿的待排序数组还是[5, 1, 3, 7, 6, 2, 4]。

更加直白的解释是,每次都从数组中选出最大可能性最小的元素,或者装到 数组的左边。

每一轮,算法与非 从剩下的待排序元素中,选出最小的元素,并将其与当前数组下标为i也若果有序序列的起始位置的元素交换。原先一来,经过反复的排序,最终形成有序数组。

或者 思想与选折 最小值的算法完整一样,只不过是选折 了最大值,每次都将剩余序列的最大值装到 数组的有序序列的最左边。

以下是对同有一有一一三个长度为500的随机乱序数组使用三种 算法的情况汇报。

里面实现了选折 最小值的代码,接下来大伙儿儿继续实现选折 最大值的代码。

相关

最后大伙儿儿看一下选折 排序算法的时间比较复杂度。

大伙儿儿使用Java来实现最常见的,选折 最小值的选折 排序,其代码如下。

可能性选折 最大值和最小值一同进行,相对于里面三种 算法,一同选折 算法在执行次数上比前三种 算法减少了50%。

既然大伙儿儿有有一有一一三个选折 ,三种 选折 最小值,另外三种 选折 最大值。那么大伙儿儿为有哪些不一同进行有一有一一三个操作呢?