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
上一篇: JavaScript 字符串相关操作方法,详细讲解
下一篇: MySQL主从复制架构使用方法