排序算法
2019-12-06 本文已影响0人
kevin5979
排序算法详细介绍点击这里
部分排序代码实现
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
</head>
<body>
<script>
function ArrayList() {
//属性
this.array = []
//方法
//insert方法
ArrayList.prototype.insert = function (item) {
this.array.push(item)
}
//toString方法
ArrayList.prototype.toString = function () {
return this.array.join('-')
}
//交换两个数据的位置
ArrayList.prototype.swap = function (m, n) {
var temp = this.array[m]
this.array[m] = this.array[n]
this.array[n] = temp
}
//简单排序算法 《 时间复杂度 O(n^2) 》
//1.冒泡排序 《 比较次数: O(n^2) 交换次数:O(n^2) 》
ArrayList.prototype.bubbleSort = function () {
var length = this.array.length
for (var i = length - 1; i >= 0; i--)
for (var j = 0; j < i; j++) {
if (this.array[j] > this.array[j + 1]) {
//交换位置
this.swap(j, j + 1)
}
}
}
//2.选择排序 《 比较次数: O(n^2) 交换次数:O(n) 》
ArrayList.prototype.selectionSort = function () {
var length = this.array.length
for (var i = 0; i < length - 1; i++) {
var min = i //记录最小值下标
for (var j = min + 1; j < length; j++) {
if (this.array[min] > this, array[j]) {
min = j
}
if (min != i) {
this.swap(min, i)
}
}
}
}
//3.插入排序(效率比冒泡、选择高) 《 比较次数: O(n^2) 交换次数:O(n) 》
ArrayList.prototype.insertionSort = function () {
var length = this.array.length
for (var i = 1; i < length; i++) {
var temp = this.array[i]
var j = i
while (this.array[j - 1] > temp && j > 0) {
//依次往后
this.array[j] = this.array[j - 1]
j--
}
//插入temp
this.array[j] = temp
}
}
//高级排序算法
//1.希尔排序《 最坏为O(n^2),通常情况要好于O(n^2) 》
ArrayList.prototype.shellSort = function () {
var length = this.array.length
//初始化增量
var gap = Math.floor(length / 2)
//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)
}
}
//2.快速排序(最快) 《 平均复杂度 O(n * log()n) 》
//2.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[left] > this.array[right]) {
this.swap(left, right)
}
if (this.array[center] > this.array[right]) {
this.swap(center, right)
}
//将center换到 right - 1 的位置
this.swap(center, right - 1)
return this.array[right - 1]
}
//2.2方法的实现
ArrayList.prototype.quickSort = function () {
this.quick(0, this.array.length - 1)
}
//2.2递归函数
ArrayList.prototype.quick = function (left, right) {
//结束条件
if (left >= right) return
//获取枢纽
var pivot = this.median(left, right)
//定义变量记录当前位置
var L = left
var R = right
//进行交换
while (true) {
while (this.array[++L] < pivot) { }
while (this.array[--R] > pivot) { }
if (L < R) {
this.swap(L, R)
} else {
break
}
}
//将枢纽放置在正确的位置
this.swap(L, right - 1)
//分而治之
this.quick(left, L - 1)
this.quick(L + 1, right)
}
}
</script>
</body>
</html>
END
