希尔排序、快速排序是最常见也是最常用的高级排序,希尔排序的出现打破了排序效率不可以超过O(N2)的定论,具有极其高的意义。在希尔排序后出现了很多更快的高级排序,但是相比之下,最重要的还是快速排序。下面我将对着两种高级排序进行思路、图解、代码、效率等的分析与讲解。
如果还对数组的初始化存在疑问的可以看我之前发布的简单排序,里面已经一一道出了,下面我就不再写了。
传送门:简单排序
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.希尔排序的效率
希尔排序的效率
还有其他选择增量的方法,这里就不一一展开讲了。
总之, 我们使用希尔排序大多数情况下效率都高于简单排序, 甚至在合适的增量和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.
quick方法
测试快速排序
// 测试快速排序
list.quickSort()
alert(list)
6.快速排序的效率
快速排序最坏情况的效率:
快速排序的平均效率:
本文地址:https://blog.csdn.net/weixin_43324314/article/details/107311027
如对本文有疑问, 点击进行留言回复!!
androidx+viewpage+tablayout+json开发(加载图片和视频)
网友评论