资讯专栏INFORMATION COLUMN

简明算法: 选择排序(javascript描述)

Miyang / 1392人阅读

摘要:懒惰了很久,人有点生锈,所以写个算法系列让自己脑筋活跃起来。所有范例一律从小到大排序选择排序比冒泡的改进是,不会频繁交换元素,而只是记录索引,最后再交换。

懒惰了很久,人有点生锈,所以写个算法系列让自己脑筋活跃起来。

(所有范例一律从小到大排序)

选择排序比冒泡的改进是,不会频繁交换元素,而只是记录索引,最后再交换。

选择排序

给定数组:

var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ];

算法描述:

首先设k=0,假定首元素既索引k代表最小元素,然后将第一个元素与第二个元素对比,如果第一个元素比第二个元素大,更改此时的索引k=1,既现在第二个元素是最小元素,此时:

k = 1;

将第二个元素与第三个元素对比,此时第二个元素比第三个元素小,保持原样不变;

k = 1;

重复上面的步骤,直到最后我们用倒数第二个元素与倒数第一个元素相比之后;经过第一轮排序,我们确定了最小元素的索引,然后与首元素交换位置,此时最小元素排列在数组首尾;

 k = 3;
  [list[0], list[3]] = [list[3], list[0]];

然后我们重复1,2,3步骤;经过第二轮我们会找到次小的元素索引,放到数组第二位;

k = 9;
 [list[1], list[9]] = [list[9], list[1]];

再次重复直到整个数组有序;

第1轮: [ 17, 26, 93, 54, 77, 31, 44, 88, 55, 20 ]
第2轮: [ 17, 20, 93, 54, 77, 31, 44, 88, 55, 26 ]
第3轮: [ 17, 20, 26, 54, 77, 31, 44, 88, 55, 93 ]
第4轮: [ 17, 20, 26, 31, 77, 54, 44, 88, 55, 93 ]
第5轮: [ 17, 20, 26, 31, 44, 54, 77, 88, 55, 93 ]
第6轮: [ 17, 20, 26, 31, 44, 54, 77, 88, 55, 93 ]
第7轮: [ 17, 20, 26, 31, 44, 54, 55, 88, 77, 93 ]
第8轮: [ 17, 20, 26, 31, 44, 54, 55, 77, 88, 93 ]
第9轮: [ 17, 20, 26, 31, 44, 54, 55, 77, 88, 93 ]

算法实现:

function select(list) {
  // 做length-1轮比较
  for (let i = 0; i < list.length - 1; i++) {
    // 假定k是最小元素
    let k = i;
    // 两两对比 找到比最小元素还小的索引
    for (let j = i + 1; j < list.length; j++) {
      if (list[j] < list[k]) {
        k = j;
      }
    }
    // 交换
    [list[i], list[k]] = [list[k], list[i]];
  }
}

// 测试
var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ];
select(list);
console.log(list);
// [ 17, 20, 26, 31, 44, 54, 55, 77, 88, 93 ]

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/93216.html

相关文章

  • 简明算法: 插入排序(javascript描述)

    摘要:懒惰了很久,人有点生锈,所以写个算法系列让自己脑筋活跃起来。所有范例一律从小到大排序插入排序的思路可以参考抓扑克牌假定我们已有的扑克牌已经有序,现在抓了一张新牌,我们需要插入到适当的位置以保持队列依然有序。 懒惰了很久,人有点生锈,所以写个算法系列让自己脑筋活跃起来。 (所有范例一律从小到大排序) 插入排序的思路可以参考抓扑克牌:假定我们已有的扑克牌已经有序,现在抓了一张新牌,我们需要...

    Guakin_Huang 评论0 收藏0
  • 简明算法: 冒泡排序(javascript描述)

    懒惰了很久,人有点生锈,所以写个算法系列让自己脑筋活跃起来。 (所有范例一律从小到大排序) 冒泡排序 给定数组: var list = [ 54, 26, 93, 17, 77, 31, 44, 88, 55, 20 ]; 算法描述: 将第一个元素与第二个元素对比,此时第一个元素比第二个元素大,交换他们,这样较大的元素就位于第二个位置了; list = [ 26, 54, 93, 17, 77...

    liukai90 评论0 收藏0
  • 常用排序算法JavaScript实现

    摘要:代码实现六堆排序算法简介堆排序是指利用堆这种数据结构所设计的一种排序算法。九计数排序算法简介计数排序是一种稳定的排序算法。计数排序不是比较排序,排序的速度快于任何比较排序算法。 赞助我以写出更好的文章,give me a cup of coffee? 2017最新最全前端面试题 1、插入排序 1)算法简介 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它...

    jerry 评论0 收藏0
  • 算法排序算法总结(JavaScript描述

    摘要:二代码简单选择排序一分析循环次,每一次的当前项与其之后的项作比较,找出其中最小的那个,与当前项交换。二代码希尔排序是一种改进版的插入排序,缩小增量排序。这样做的目的是因为,直接插入排序在序列基本有序时效率最高。 排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性 冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定 简单选择排序 O(n^2) O(n^2)...

    dkzwm 评论0 收藏0
  • Javascript算法——选择排序

    摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。这里主要介绍选择排序。一图胜千言算法描述选择排序是一种简单直观的排序算法,无论什么数据进去都是的时间复杂度。重复第二步,直到所有元素均排序完毕。 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。这里主要介绍选择排序。 一图胜千言: showImg(...

    yhaolpz 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<