JS实现高级排序——（希尔排序、快速排序）

希尔排序、快速排序是最常见也是最常用的高级排序，希尔排序的出现打破了排序效率不可以超过O(N2)的定论，具有极其高的意义。在希尔排序后出现了很多更快的高级排序，但是相比之下，最重要的还是快速排序。下面我将对着两种高级排序进行思路、图解、代码、效率等的分析与讲解。
如果还对数组的初始化存在疑问的可以看我之前发布的简单排序，里面已经一一道出了，下面我就不再写了。
传送门：简单排序

一、希尔排序

1.希尔排序的思路

• 希尔排序是插入排序的升级版
• 设置一个增量，然后根据增量进行分组，每个分组内进行插入排序，尽可能让较小的元素往前靠，较大的元素往后靠
• 增量依次递减，重复上述步骤，到最后增量为1时，即为原始的插入排序，只是这时候的顺序已经有了一定的顺序性，因此插入的次数少了很多。

2.希尔排序图解
注：希尔排序的初稿增量一般为长度的一半（向下取整）

3.希尔排序代码

// 希尔排序
ArrayList.prototype.shellSort = function () {
//  获取数组长度
var length = this.array.length

// 初始化增量gap（间隔）
var gap = Math.floor(length / 2)

// while循环（让gap不断减小）
while (gap >= 1) {
// 以gap为间隔，进行分组，然后进行插入排序
for (var i = gap; i < length; i++) {
  var temp = this.array[i]
  var j = i
  while (this.array[j - gap] > temp && j > gap - 1) {
    this.array[j] = this.array[j - gap]
    j -= gap
   }

   // 将j位置赋值为temp
    this.array[j] = temp
  }
          
  // 改变增量
  gap = Math.floor(gap / 2)
  }
}

测试希尔排序

// 测试希尔排序
list.shellSort()
alert(list)

4.希尔排序的效率
希尔排序的效率

• 希尔排序的效率很增量是有关系的.
• 但是, 它的效率证明非常困难, 甚至某些增量的效率到目前依然没有被证明出来.
• 但是经过统计, 希尔排序使用原始增量, 最坏的情况下时间复杂度为O(N²), 通常情况下都要好于O(N²)

还有其他选择增量的方法，这里就不一一展开讲了。

总之, 我们使用希尔排序大多数情况下效率都高于简单排序, 甚至在合适的增量和N的情况下, 还好好于快速排序.

二、快速排序

1.快速排序的思路

• 快速排序可以说是冒泡排序的升级版，思想是分而治之。
• 步骤是先找到一个基准值（枢纽），然后把小于基准的放左边，大于基准的放右边。再对左右分别排序。
• 左右分别排序的过程也是先找到一个基准，重复第二步，然后一直细分到不能再细分，到最后不就是相邻两个元素进行冒泡排序了吗？
• 快速排序的效率高是因为快速排序可以在一次循环中(其实是递归调用)找出某个元素的正确位置, 并且该元素之后不需要任何移动.

2.快速排序枢纽的选择

• 快速排序枢纽的选择有很多方式，有的直接选第一个元素作为基准，可是当第一个元素为数组的最小值的时候，效率会非常底下。

• 这里我采取获取中间值的方法去获取枢纽，即得到数组左右两端的值的索引，然后求出当前数组中心的索引，最后把三个数字进行比较排序，这样可以得到局部中间值。

3.快速排序图解

4.获取枢纽的代码

 // 1.选择枢纽
ArrayList.prototype.median = function (left, right) {
  // 取出中间位置
  var center = Math.floor((left + right) / 2)

  // 判断大小并交换位置
  if (this.array[left] > this.array[center]) {
    this.swap(left, center)
    }
  if (this.array[center] > this.array[right]) {
    this.swap(center, right)
    }
  if(this.array[left] > this.array[center]) {
  this.swap(left, center)
    }

  // 将center交换到right - 1的位置
  this.swap(center, right - 1)

  return this.array[right - 1]
  }

解析：这里获取center的值为枢纽，然后把枢纽放到 right - 1 的位置（此时以及确保 right > right - 1）

5.快速排序的实现

// 2.快速排序的实现
ArrayList.prototype.quickSort = function () {
  this.quick(0, this.array.length - 1)
  }

ArrayList.prototype.quick = function (left, right) {
  // 2.1结束条件
  if (left >= right) return 

  // 2.2获取枢纽
  var pivot = this.median(left, right)

  // 2.3定义变量，用于记录当前找到的位置
  var i = left
  var j = right - 1

  // 2.4开始交换
  while (i < j) {
    while (this.array[++i] < pivot) {}
    while (this.array[--j] > pivot) {}
    if (i < j) {
       //2.4.1交换数值 
      this.swap(i, j)
    } else {
        //2.4.2停止循环
      break
    }
  }

  // 2.5将枢纽放置正确的位置，i
  this.swap(i, right - 1)

  // 2.6分而治之（递归调用左右）
  this.quick(left, i - 1)
  this.quick(i + 1, right)

}

代码解析：

• 这里有两个函数: quickSort和quick.

  • 外部调用时, 会调用quickSort
  • 内部递归时, 会调用quick

• quick方法

  • 当确定枢纽后，用两个指针分别从两头开始查找
  • 2.1中，结束当前函数的条件是左右两个指针相等
  • 2.4中，++i、–j是因为在获取枢纽的时候，已经把左右中的顺序局部排好了，所以不需要多此一举让两端指针探查这两个的值
  • 2.5中，完成一趟查找，进行交换数值
  • 2.6中，递归调用，不断细化左右，细分左右。

测试快速排序

// 测试快速排序
list.quickSort()
alert(list)

6.快速排序的效率
快速排序最坏情况的效率：

• 当每次选择的枢纽都是最左边或者最后边的时候
• 那么效率等同于冒泡排序.
• 但因为我们是选择三个值的中位值，不可能出现最坏情况

快速排序的平均效率：

• 快速排序的平均效率是O(N * logN).
• 虽然其他某些算法的效率也可以达到O(N * logN), 但是快速排序是最好的.

本文地址：https://blog.csdn.net/weixin_43324314/article/details/107311027