用js写插入排序和选择排序

SHERlocked93 发布于2019-08-22 16:37 / 1605人阅读

摘要：总结一下，插入排序优于选择排序。插入排序可以提前终止内层循环，如果数组近乎有序，那么效率会很高。我的写的不是最好的，仅仅是解释概念，有兴趣的同学可以自己写一个更好的插入排序和选择排序。

我觉得作为前端学学算法也是有益处的吧，所以今天就先来讲讲最基础的排序算法。提升我们程序员的内功~

插入排序

插入排序是n^2的基础排序方法，大致思想是假设一个数组的前n个元素已经有序，然后考虑把第n+1个未排序的元素给插入到有序数组中去。现将n+1和第n个元素比较，如果n+1比n小，那么就交换一下位置。之后我们要排序的元素就在n这个位置上了，接着我们继续比较n和第n-1个元素的大小。如此反复，直到我们要插入的元素找到适合他的位置。
下面来示范一下
6--7--8--9--3--1--4--6--3--8--9--5
6--7--8--9已经有序，我们要插入的元素是n=4这个元素3。比较9和3的大小，9比3大。交换一下位置
6--7--8--3--9，就变成了这个样子。接着比较8和3的大小，8比3大，交换一下位置
6--7--3--8--9，继续比较7和3的大小，7比3大，交换一下位置
6--3--7--8--9，继续比较6和3的大小，6比3大，交换一下位置
3--6--7--8--9。到这里循环结束，就已经排好序了。接着比较第n=5的元素1应该插入的位置，如此往复就把数组给排好了序了。
一下是代码。

//写一个随机生成数组的函数
function randomArr(count) {
  var arr = []
  for (var i = 0; i < count; i++) {
    var number = Math.ceil(Math.random() * 5000)
    arr.push(number)
  }
  return arr
}
// 交换元素位置的函数
function swap(arr, i, j) {
  var temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

var arr = randomArr(5000)
// 插入排序函数
function insertionSort(arr) {
    var length = arr.length
    // 第0个元素默认就是有序的，因为只有一个元素，所以从第一个元素开始。arr[i]就是要插入的那个元素
    for (var i = 1; i < length; i++) {
        // 从第i-1个元素往前都是已经排好序的元素。所以最后一个开始往前比较
        for (var j = i - 1; j >= 0; j--) {
            // 这里的j+1等于i这个元素。也就是arr[i] === arr[j+1]
            if (arr[j] > arr[j + 1]) {
                swap(arr, j + 1, j)
            } else {
                break
            }
        }
    }
    return arr
}
insertionSort(arr)

由于是两层for循环，所以它的时间复杂度是n^2级别的。
到这里其实还没有完，插入排序还是有可以优化的地方的。现在的这个插入排序函数要swap频繁的交换位置，我们可以这样

function insertionSort(arr) {
    var length = arr.length
    // 第0个元素默认就是有序的，因为只有一个元素，所以从第一个元素开始。arr[i]就是要插入的那个元素
    for (var i = 1; i < length; i++) {
        // **用一个变量保存要插入的元素**
        var value = arr[i]
        // 从第i-1个元素往前都是已经排好序的元素。所以最后一个开始往前比较
        for (var j = i - 1; j >= 0; j--) {
            // 这里的j+1等于i这个元素。也就是arr[i] === arr[j+1]
            if (arr[j] > value) {
                // 如果比要插入的元素大，把值arr[j]往右移一位
                arr[j+1] = arr[j]
                // 边界条件，直到j等于0的时候终止循环，将value赋给arr[0]，结束循环
                if (j === 0){arr[j] = value; break}
            } else {
                // 否则把value赋给arr[j]循环结束
                arr[j] = value
                break    
            }
        }
    }
    return arr
}

虽然插入排序是n^2级别的算法，但是在一个近乎有序的数组里去实现插入排序，那么他的效率会变的非常高。

因为插入排序可以提前break掉内层循环。

有兴趣可以写一个生成近乎有序数组的函数去实验一下。

// 近乎有序数组
function nearlySorted(arr) {
  return arr
}

选择排序

选择排序就是在循环中不停的选择最小的元素，然后交换位置。
下面来示范一下
6--7--8--9--3--1--4--6--3--8--9--5
找到数组中最小的元素1，然后记录1的位置是5。接着交换位置变成
1--7--8--9--3--6--4--6--3--8--9--5
接着在剩下的数组里7--8--9--3--6--4--6--3--8--9--5找到最小的元素3，记录下它的下标位置是4，然后交换位置变成
1--3--8--9--7--6--4--6--3--8--9--5。如此往复直到排好序。

function randomArr(count) {
  var arr = []
  for (var i = 0; i < count; i++) {
    var number = Math.ceil(Math.random() * 5000)
    arr.push(number)
  }
  return arr
}
function swap(arr, i, j) {
  var temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

var arr = randomArr(5000)

function selectionSort(arr) {
  var length = arr.length
  var value, pos
  for (var i = 0; i < length; i++) {
    value = arr[i]
    pos = i
    for (var j = i; j < length; j++) {
      var cur = arr[j]
      if (value > cur) {
        value = cur
        pos = j
      }
    }
    swap(arr, i, pos)
  }
  return arr
}
selectionSort(arr)

到此两个基础排序就实现了。总结一下，插入排序优于选择排序。

插入排序可以提前终止内层循环，如果数组近乎有序，那么效率会很高。而选择排序无法提前终止循环。
不过最好的排序算法还是nlogn级别的算法。如归并排序和快速排序。
我的写的不是最好的，仅仅是解释概念，有兴趣的同学可以自己写一个更好的插入排序和选择排序。

私有云服务器托管用php实现插入排序插入排序实现插入排序直接插入排序

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

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

JS中可能用得到的全部的排序算法

本篇有7k+字, 系统梳理了js中常见的12种排序算法。除了基本排序算法，文章还包含了希尔排序、堆排序、桶排序等较为复杂的排序实现，如果喜欢请点赞支持~谢谢. 原文: http://louiszhai.github.io/20... 导读排序算法可以称得上是我的盲点, 曾几何时当我知道Chrome的Array.prototype.sort使用了快速排序时, 我的内心是奔溃的(啥是快排, 我只知道...

verano 2019-08-20 15:08 评论0 收藏0
JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，...

canger 2019-08-26 10:15 评论0 收藏0
基于 Javascript 排序算法

摘要：适用于数据比较少或基本有序的情况。插入排序时间复杂度为，空间复杂度为，属于稳定排序。算法适用于少量数据的排序。就像下图这样，可以理解桶的意思下图是整个排序过程示意图基数排序时间复杂度为，空间复杂度为，属于稳定排序。写在前面个人感觉：javascript对类似排序查找这样的功能已经有了很好的封装，以致于当我们想对数组排序的时候只需要调用arr.sort()方法，而查找数组元素也只需要...

tommego 2019-08-23 11:47 评论0 收藏0
排序算法分析总结（附js实现）

摘要：本文对一些排序算法进行了简单分析，并给出了的代码实现。平均时间复杂度不好分析，它是冒泡排序是稳定的排序算法。冒泡排序是原地排序算法原地排序指的是空间复杂度是的排序算法。归并排序，会将数组从中间分成左右两部分。本文对一些排序算法进行了简单分析，并给出了 javascript 的代码实现。因为本文包含了大量的排序算法，所以分析不会非常详细，适合有对排序算法有一定了解的同学。本文内容其实不...

liaoyg8023 2019-08-23 17:11 评论0 收藏0
用JavaScript实现插入排序

摘要：实现插入排序插入排序是一种非常简单的算法，最适合大部分已经被排好序的数据。由此才有了这个名字插入排序。插入排序的最坏情况是输入的数组是按逆序排序的。总结当输入的数组已经大部分被排好序时，插入排序的效果最佳。翻译：疯狂的技术宅https://medium.com/@jimrottin... 本文首发微信公众号：前端先锋欢迎关注，每天都给你推送新鲜的前端技术文章插入排序的工作原理...

LittleLiByte 2019-08-26 13:44 评论0 收藏0