JS实现三种简单排序(冒泡排序、选择排序、插入排序)

2020-10-7 22:19:40
学习记录
382

JS实现三种简单排序(冒泡排序、选择排序、插入排序)

最近在学习 JavaScript 的数据结构和算法,以前没有接触过排序算法,经过学习后,我有一些收获,因此我打算写文章记录一下我当时的一些想法,并把排序算法原理记录一下

1. 冒泡排序

​ 冒泡排序是简单排序中的最简答的一种排序算法,其原理也很简单。

原理说明

当给定一组数字后,指针依次与后一个元素比较大小,如果当前元素大于后一个元素,则两者交换位置,然后指针往下移动。经过指针走完一次之后,最大的值就被交换到了最后面,接下来只需要对剩余的元素减一个数组再次进行遍历即可。

要点分析

  1. 双层循环
  2. 外层循环控制每次内层循环需要遍历到最大长度。(因为经过一次内层遍历可以把一个元素放置在正确位置,因此下次内层循环的最大长度只需要数组长度减1)
  3. 内层循环控制找出最大的数字并交换到数组最后面。

代码实现

function bubbleSort(arr){ let length = arr.length,tmp; while(--length>0){//因为内层元素不能越界,需要比较下一个元素,当比较到长度减1的位置的时候,其实最后一个元素已经比较好了。 for(let i =0;i<length;i++){ if(arr[i]>arr[i+1]){ tmp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = tmp; } } } return arr; }

1391679-20180618163321525-1936669878

2. 选择排序

原理说明

写选择排序的时候,有点忘了原理了,当时人总是学了,会了然后再忘。。。咳咳题外话,记录一下原理

选择排序思想是,先从数组中取出来一个元素,把这个元素作为最小的。然后分别把这个元素和其他元素做比较,找出实际最小的那个元素,然后进行交换。经过一次循环对比,就可以把最小的放到第一位。接下来就是再次取出来一个,继续上面的比较。

要点分析

  1. 也是两层循环,需要定义一个变量来储存最小值的指针位置
  2. 外层循环控制每次的最小元素
  3. 内层循环控制该元素和其他元素做对比,找出真正最小的元素,改变最小指针位置
  4. 内层循环结束后,紧接着需要把最小的放到当前外层循环的位置。

代码实现

function selectionSort(arr){ let tmp,minPoint,length=arr.length; for(let i = 0;i<length;i++){ minPoint = i; let k = i; while( ++k < length ){ if(arr[k]<arr[minPoint]){ minPoint = k; } } if(minPoint != i){ tmp = arr[minPoint]; arr[minPoint] = arr[i]; arr[i] = tmp; } } return arr; }

3. 插入排序

原理说明

插入排序原理很简单,假设元素左侧是有序的,然后挑出来一个元素,把这个元素和前面的元素做对比,如果前面的元素大于这个元素,就把前面的元素往后移动一个位置,一直这样比较,最后找到一个空位置,插入即可。(默认第0个元素一个元素就是有序的)

要点分析

  1. 首次一个元素就是有序的,从第二个元素开始向前面插入。
  2. 比较的时候,如果比较的元素比待插入的元素大,就把比较的元素往后移动一个位置,这个后移是最关键的!!!!
  3. 循环上面的操作,再比较下一个元素,最后有两种情况,一种找到了一个比待插入元素小的元素,直接退出循环,在循环后面把带插入元素插入该元素后面,另一种情况,经过比较后,没有找到一个比待插入元素小的,也就是待插入的元素是有序数组中最小的,就把他插入数组最前面

代码实现

function insertSotr(arr){ let length = arr.length; for(let i=1;i<length;i++){ let k =i; let tmp = arr[k]; while(tmp < arr[k-1]&&k>0){//如果待插入的元素比前面一个元素小,或者已经查找k已经交换完了。 arr[k] = arr[k-1];//这里把大的元素往后移动 k--; } arr[k] = tmp;//这里是上面的循环走完了,可能是因为k已经是0了,或者找到比tmp小的元素了,就可以把这个 } return arr; }

1391679-20180618165919523-196396537

图片引自https://www.cnblogs.com/xaimicom/p/9189471.html

avatar

Sky(小新)

个人签名: 提升能力,创造价值!

江苏-南京
skylpz@qq.com