javascript数据结构-搜索排序算法

本博客参考于洛伊安妮·格罗纳编著的javascript数据结构与算法第三版及codeWay老师视频或其他博客资料，在此对此表示感谢!
github仓库：https://github.com/hzx17/

大O表示法

大O表示法：

在计算机中采用粗略的度量来描述计算机算法的效率，这种方法被称为“大O”表示法
在数据项个数发生改变时，算法的效率也会跟着改变。所以说算法A比算法B快两倍，这样的比较是没有意义的。
因此我们通常使用算法的速度随着数据量的变化会如何变化的方式来表示算法的效率，大O表示法就是方式之一。

常见的大O表示形式

|符号 | 名称|
|O（1） | 常数|
|O（log(n)） | 对数|
|O（n） | 线性|
|O（nlog(n)）| 线性和对数乘积|
|O（n²） | 平方|
|O（2n） | 指数|

不同大O形式的时间复杂度：

可以看到效率从大到小分别是：O（1）> O（logn）> O（n）> O（nlog(n)）> O（n²）> O（2n）

推导大O表示法的三条规则：

规则一：用常量1取代运行时间中所有的加法常量。如7 + 8 = 15，用1表示运算结果15，大O表示法表示为O（1）；
规则二：运算中只保留最高阶项。如N^3 + 3n +1，大O表示法表示为：O（N3）;
规则三：若最高阶项的常数不为1，可将其省略。如4N2，大O表示法表示为：O（N2）;

排序算法

这里主要介绍几种简单排序和高级排序：

简单排序：冒泡排序、选择排序、插入排序；
高级排序：希尔排序、快速排序；

冒泡排序

冒泡排序的思路

• 对未排序的各元素从头到尾依次比较相邻的两个元素大小关系；
• 如果左边的人员高，则将两人交换位置。比如1比2矮，不交换位置；
• 向右移动一位，继续比较2和3，最后比较 length - 1 和 length - 2这两个数据；
• 当到达最右端时，最高的人一定被放在了最右边；
• 按照这个思路，从最左端重新开始时，只需要走到倒数第二个位置即可；

冒泡排序的封装

这里均是在ArrayList类中封装的

ArrayList类

/* 封装列表项 */
function ArrayList () {
  // 属性
  this.items = []
  // 插入数组
  ArrayList.prototype.insert = function (item) {
    this.items.push(item)
  }
  // toSring
  ArrayList.prototype.toString = function () {
    return this.items.join(",")
  }
    // 将交换两个位置的方法抽取
  ArrayList.prototype.swap = function (m, n) {
    // 交换两个位置数据
    let temp = this.items[m]
    this.items[m] = this.items[n]
    this.items[n] = temp
  }
}

// 冒泡排序
ArrayList.prototype.bubbleSort = function () {
  // 递增排序
  let count = this.items.length // 内层交换次数
  for(let i = count-1; i>=0 ;i--  ) {
    for (let j =0 ; j<i ; j++) {
      if(this.items[j] > this.items[j+1]) {
        this.swap(j,j+1)
      }
    }
  }
  return this.toString()
}

选择排序

选择排序思路

• 选定第一个索引的位置比如1，然后依次和后面的元素依次进行比较；
• 如果后面的元素，小于索引1位置的元素，则交换位置到索引1处；
• 经过一轮的比较之后，可以确定一开始指定的索引1位置的元素是最小的；
• 随后使用同样的方法除索引1意外逐个比较剩下的元素即可；
• 可以看出选择排序，第一轮会选出最小值，第二轮会选出第二小的值，直到完成排序。

// 选择排序
ArrayList.prototype.selectionSort = function () {
  // 将数组长度提取出来
  let length = this.items.length
  // 记录最小值下标
  let minLoc = 0
  for(let j =0 ;j<length-1; j++) {
    minLoc = j
    // 内层循环
    for(let i = j ; i<=length -1 ;i++) {
      if(this.items[minLoc] >= this.items[i]) {
        minLoc = i
      }
    }
    this.swap(j,minLoc)
  }
  return this.items
}

插入排序

插入排序的思路

• 插入排序是简单排序中效率最高的一种排序。
• 插入排序思想的核心是局部有序。如图所示，X左边的人称为局部有序；
• 首先指定一数据X（从第一个数据开始），并将数据X的左边变成局部有序状态；
• 随后将X右移一位，再次达到局部有序之后，继续右移一位，重复前面的操作直至X移至最后一个元素。

// 插入排序
ArrayList.prototype.insertSort = function () {
  // 获取数组长度
  let length = this.items.length
  //外层循环
  for(let i = 1; i <length ; i++) {
    let temp = this.items[i]
    let tempLoc = i
    while(this.items[tempLoc-1] > this.items[tempLoc] ) {
      this.swap(tempLoc-1,tempLoc)
      // 内层循环
      if(tempLoc >1){
        tempLoc -=1 
      }
    }
  }
  return this.toString()
}

希尔排序

希尔排序是插入排序的一种高效的改进版，效率比插入排序要高。

希尔排序的历史背景

希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布；
希尔算法首次突破了计算机界一直认为的算法的时间复杂度都是O（N^2）的大关，为了纪念该算法里程碑式
的意义，用Shell来命名该算法；

插入排序的问题

假设一个很小的数据项在很靠近右端的位置上，这里本应该是较大的数据项的位置；
将这个小数据项移动到左边的正确位置，所有的中间数据项都必须向右移动一位，这样效率非常低；
如果通过某种方式，不需要一个个移动所有中间的数据项，就能把较小的数据项移到左边，那么这个算法的执行速度就会有很大的改进。

希尔排序的实现思路

• 希尔排序主要通过对数据进行分组实现快速排序；
• 根据设定的增量（gap）将数据分为gap个组（组数等于gap），再在每个分组中进行局部排序；
• 假如有数组有10个数据，第1个数据为黑色，增量为5。那么第二个为黑色的数据index=5，第3个数据为黑色的数据index = 10（不存在）
• 所以黑色的数据每组只有2个，10 / 2 = 5一共可分5组，即组数等于增量gap。
• 排序之后，减小增量，继续分组，再次进行局部排序，直到增量gap=1为止。随后只需进行微调就可完成数组的排序；

希尔排序的封装

// 希尔排序
ArrayList.prototype.shellSort = function () {
  // 获取数组长度
  let length = this.items.length
  // 初始化增量
  let gap = Math.floor(length / 2)
  // 使gap减小
  while(gap >= 1) {
    for ( let i= gap; i<length ;i++) {
      let temp = this.items[i]
      let j = i
      while(this.items[j-gap] > temp) {
        this.items[j] = this.items[j-gap]
        j -= gap
      }
      this.items[j] = temp
    }
    gap = Math.floor(gap / 2)
  }
  return this.toString()
}

快速排序

• 快速排序可以说是目前所有排序算法中，最快的一种排序算法。当然，没有任何一种算法是在任意情况下都是最优的。但是，大多数情况下快速排序是比较好的选择。

• 快速排序其实是冒泡排序的升级版；

• 快速排序的核心思想是分而治之，先选出一个数据（比如65），将比其小的数据都放在它的左边，将比它大的数据都放在它的右边。这个数据称为枢纽

快速排序的枢纽：

• 第一种方案：直接选择第一个元素作为枢纽。但是，当第一个元素就是最小值的情况下，效率不高；
• 第二种方案：使用随机数。随机数本身十分消耗性能，不推荐；
  优秀的解决方法：取index为头、中、位的三个数据排序后的中位数；如下图所示，按下标值取出的三个数据为：92，31，0，经排序后变为：0，31，92，取其中的中位数31作为枢纽（当（length-1）/2不整除时可向下或向上取整）：

快速排序的封装

// 快速排序算法
ArrayList.prototype.quickSort = function () {
  this.quick(0,this.items.length)
  return this.toString()
}
// 快速排序枢纽查找
ArrayList.prototype.meddlein = function (left,right){
   // 取出中位数
   let center = Math.floor( (left +right) / 2)
   // 比较大小确定中位数
   if(this.items[left] > this.items[center]) {
     this.swap(left,center)
   }
   if(this.items[center] > this.items[right]) {
     this.swap(center,right)
   }
   if(this.items[left] > this.items[center]) {
     this.swap(left,center)
   }
   this.swap(center,right-1)
   return this.items[right-1]
}
// 快速排序的递归
ArrayList.prototype.quick = function (left,right) {
  // 结束条件 
  if(left >= right)  return
  // 获取枢纽数
  let pivot = this.meddlein(left,right)
  // 定义变量
  let i = left
  let j = right-1
  while(i<j) {
    while(this.items[++i]  < pivot) {}
    while(this.items[--j] >pivot) {}
    if(i < j) {
      this.swap(i,j)
    }
  }
  this.swap(i,right-1)
  // 分而治之
  this.quick(left,i-1)
  this.quick(i+1,right)
}

封装测试

/* 测试排序算法 */
const arr = new ArrayList()

arr.insert(66)
arr.insert(88)
arr.insert(17)
arr.insert(2)
arr.insert(25)
arr.insert(68)
arr.insert(102)
arr.insert(5)
arr.insert(56)
arr.insert(33)
console.log(arr.toString())
// console.log("冒泡排序结果："+arr.bubbleSort())
// console.log("选择排序算法结果：" +arr.selectionSort())
// console.log('插入排序算法结果：',arr.insertSort())
// console.log('希尔排序算法结果：'+arr.shellSort())
console.log('快速排序算法结果：'+arr.quickSort())

这五种排序效率

冒泡排序的效率

上面所讲的对于7个数据项，比较次数为：6 + 5 + 4 + 3 + 2 + 1;
对于N个数据项，比较次数为：(N - 1) + (N - 2) + (N - 3) + … + 1 = N * (N - 1) / 2；如果两次比较交换一次，那么交换次数为：N * (N - 1) / 4；
使用大O表示法表示比较次数和交换次数分别为：O（ N * (N - 1) / 2）和O（ N * (N - 1) / 4），根据大O表示法的三条规则都化简为：O（N^2）;

选择排序的效率

选择排序的比较次数为：N * (N - 1) / 2，用大O表示法表示为：O（N^2）;
选择排序的交换次数为：(N - 1) / 2，用大O表示法表示为：O（N）;
所以选择排序的效率高于冒泡排序；

插入排序的效率

比较次数：第一趟时，需要的最大次数为1；第二次最大为2；以此类推，最后一趟最大为N-1；所以，插入排序的总比较次数为N * (N - 1) / 2；但是，实际上每趟发现插入点之前，平均只有全体数据项的一半需要进行比较，所以比较次数为：N * (N - 1) / 4；

交换次数：指定第一个数据为X时交换0次，指定第二个数据为X最多需要交换1次，以此类推，指定第N个数据为X时最多需要交换N - 1次，所以一共需要交换N * (N - 1) / 2次，平局次数为N * (N - 1) / 2；

虽然用大O表示法表示插入排序的效率也是O（N^2），但是插入排序整体操作次数更少，因此，在简单排序中，插入排序效率最高；

希尔排序

希尔排序的效率和增量有直接关系，即使使用原稿中的增量效率都高于简单排序。

快速排序

快速排序最坏情况下的效率：每次选择的枢纽都是最左边或最右边的数据，此时效率等同于冒泡排序，时间复杂度为O（n2）。可根据不同的枢纽选择避免这一情况；
快速排序的平均效率：为O（NlogN），虽然其他算法效率也可达到O（NlogN），但是其中快速排序是最好的。