欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JS实现高级排序——(希尔排序、快速排序)

程序员文章站 2022-06-22 20:27:49
希尔排序、快速排序是最常见也是最常用的高级排序,希尔排序的出现打破了排序效率不可以超过O(N2)的定论,具有极其高的意义。在希尔排序后出现了很多更快的高级排序,但是相比之下,最重要的还是快速排序。下面我将对着两种高级排序进行思路、图解、代码、效率等的分析与讲解。如果还对数组的初始化存在疑问的可以看我之前发布的简单排序,里面已经一一道出了,下面我就不再写了。传送门:简单排序一、希尔排序1.希尔排序的思路希尔排序是插入排序的升级版设置一个增量,然后根据增量进行分组,每个分组内进行插入排序,尽可能让...

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

一、希尔排序

1.希尔排序的思路

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

2.希尔排序图解
注:希尔排序的初稿增量一般为长度的一半(向下取整)
JS实现高级排序——(希尔排序、快速排序)
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.快速排序图解
JS实现高级排序——(希尔排序、快速排序)
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