用 Javascript 实现冒泡排序 快速排序算法

2,936 阅读4分钟
原文链接: viviier.com

模拟数组

介绍

在学习算法之前,我们事先定义好一个测试用的数组并添加了一些常规数组操作的函数。插入数组数据,删除数组数据,显示数组数据,交换数组元素等等。

实现

class cArray {
  constructor(num) {
    this.num = num
    this.pos = 0
    this.dataStore = new Array(num)
  }
  
  setData() {
    for(let i = 0; i < this.num; i++) {
      this.dataStore[i] = Math.floor(Math.random() * (this.num + 1))
    }
  }
  
  clear() {
    for(let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = 0
    }
  }
  
  insert(elm) {
    this.dataStore[this.pos++] = elm
  }
  
  swap(arr, index1, index2) {
    let temp = arr[index1]
    arr[index1] = arr[index2]
    arr[index2] = temp
  }
  
  toString() {
    let restr = ''
    for(let i = 0; i < this.dataStore.length; i++) {
      restr += this.dataStore[i] + ' '
      if( i > 0 && i % 10 === 0) {
        restr += '\n'
      }
    }
    return restr
  }
}

我们来测试一下:

let nums = 10
let myNums = new cArray(nums)
myNums.setData()
console.log(myNums.toString())  // "5 4 8 0 1 2 0 6 8 9 "

冒泡排序

介绍

对数组进行冒泡排序,数组会比较相邻的数据,条件判断后进行互换操作

例子

简单例子

我们有一个列表:
B H E D A ( B > H ? yes -> B保持不动,继续判断H, H > E ? no -> H和E互换位置,继续判断H.. .)
经过第一次排序后,这个列表变成:
B E D A H ( 第一阶段B和H判断完后,继续用重复相同方式判断E )
经过第二次排序后,这个列表变成:
B D A E H
经过第三次排序后,这个列表变成:
B A D E H
经过第四次排序后,这个列表变成:
A B D E H bubble sort end<

实现
bubbleSort() {
  
  /*
   * @获取当前数组的长度
   *  以及定义一个temp作为储存器
   */
  let numsElm = this.dataStore.length
  let temp
  
  /*
   * @第一个循环,获取数组的总长度,每遍历一次,数组长度减一,直到数组长度小于2
   * @第二个循环,获取当前需要遍历的数组长度,从零开始全部遍历,这里的inner当做是数组的索引,如果判断失败,那么继续下一个inner的判断
   * @判断,当前第inner个元素的值是否大于inner + 1 的值,如果是就交换(否则就进行 下一个索引的判断)
   * @就想把里面的每一个数都跟数组里的每一个数做一个比较,如果当前判断失败,那么进行下一个,第一个数比较完成后,将数组长度-1也就是最后一个数值固定,然后继续遍历比较
   */
  for(let outer = numsElm; outer >= 2; outer--) {
    for(let inner = 0; inner < outer - 1; inner++) {
      if( this.dataStore[inner] > this.dataStore[inner + 1]) {
        this.swap(this.dataStore, inner, inner + 1)
      }
    }
  }
}

我们来测试一下:

let nums = 10
let myNums = new cArray(nums)
myNums.setData()
console.log(myNums.toString())  // "9 10 10 3 4 3 6 6 2 1 "
myNums.bubbleSort()
console.log(myNums.toString())  // "1 2 3 3 4 6 6 9 10 10 "

快速排序

介绍

对数组进行快速排序,设置一个基准后,数组排序会围绕基准进行,将列表中所有小于基准值的元素放在基准值前面,所有相等或大于基准值的元素放在基准值的后面,然后对两个自序列重复进行上面步骤,最后和基准值合并。

例子

简单例子

我们有一个列表:
9 4 10 3 1 1 0 10 8 3
原始数组,基准值为9
4 3 1 1 0 8 3 9 10 10
数组元素按小于基准值和大于基准值分组,然后再次将数组按基准值分组,左边的基准值是4,右边的基准值是10,然后合并数组。
3 1 1 0 3 4 8 9 10 10
再次分割后,又出现了按照4为基准的子序列,左边有大于1的length,以3为基准值继续分割,右边只有一个元素,因此下一次排序,右边返回空[],而按照10为基准的子序列只有一个元素,所以返回空[],,然后合并数组。
1 1 0 3 3 4 8 9 10 10
再次分割,以3为基准值,左边length大于1,因此以1为基准值继续分割,右边length为1,因此下一次排序,返回空[],然后合并数组。
0 1 1 3 3 4 8 9 10 10
再次分割,以1为基准值,左边length为1,下次排序返回空[],右边length为1,下次排序返回空,然后合并数组。

实现
quickSort(arr) {
  /*
   * @判断传递进来的数组长度是否需要分割
   * @定义左边数组,定义右边数组,定义基准值为数组的第一个元素
   * @i的索引从1开始,是因为第一个(0)作为了基准值,然后循环遍历
   * @判断当前元素arr[i]大于或者小于基准值,小于放在left数组里,大于放在right数组里
   * 判断完成后利用递归继续将分隔出来的子数组进行轮询分隔,然后通过concat合并数组,返回新数组
   */
  if(arr.length <= 1) return arr
  
  let left = []
  let right = []
  let pivot = arr[0]
  
  for(let i = 1; i < arr.length; i++) {
    if(arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return this.quickSort(left).concat(pivot, this.quickSort(right))
}

我们来测试一下:

let nums = 10
let myNums = new cArray(nums)
myNums.setData()
console.log(myNums.toString())  // "9, 5, 7, 2, 1, 1, 2, 13, 132, 68 "
console.log(myNums.quickSort(myNums.dataStore).toString())  // "1, 1, 2, 2, 5, 7, 9, 13, 68, 132 "