html教程排序
ts
let binarySearch = (array, item) => {
let low = 0
let high = array.length - 1
let guess
while (low <= high) {
let mid = Math.round((low + high) / 2)
guess = array[mid]
if (guess == item) {
return mid
}
if (guess > item) {
high = mid - 1
} else {
low = mid + 1
}
}
return null
}
console.log(binarySearch([1, 3, 4, 5, 6, 7, 8, 9], 9))let binarySearch = (array, item) => {
let low = 0
let high = array.length - 1
let guess
while (low <= high) {
let mid = Math.round((low + high) / 2)
guess = array[mid]
if (guess == item) {
return mid
}
if (guess > item) {
high = mid - 1
} else {
low = mid + 1
}
}
return null
}
console.log(binarySearch([1, 3, 4, 5, 6, 7, 8, 9], 9))ts
function swap(arr, indexA, indexB) {
;[arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]]
}
function bubbleSort(arr) {
let len = arr.length
for (let i = 0; i < len; i++) {
//外层循环控制趟数
for (let j = 0; j < len - 1 - i; j++) {
//内层循环控制第i趟要比较的次数
if (arr[j] > arr[j + 1]) {
//相邻元素两两对比
swap(arr, j, j + 1)
}
}
}
return arr
}
console.log(
bubbleSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]),
)function swap(arr, indexA, indexB) {
;[arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]]
}
function bubbleSort(arr) {
let len = arr.length
for (let i = 0; i < len; i++) {
//外层循环控制趟数
for (let j = 0; j < len - 1 - i; j++) {
//内层循环控制第i趟要比较的次数
if (arr[j] > arr[j + 1]) {
//相邻元素两两对比
swap(arr, j, j + 1)
}
}
}
return arr
}
console.log(
bubbleSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]),
)ts
//节点类
function Node(element) {
this.item = element
this.next = null
}
//循环列表需要修改一下构造函数，和遍历时候的判断条件
//构造函数如下；希望从后向前遍历，又不想要建立双向链表，就使用循环链表。
function Llist() {
this.head = new Node('1')
this.head.next = this.head
this.remove = remove
this.insert = insert
this.find = find
this.display = display
//..........
}
function find(number) {
let current = this.head
while (current.item != number) {
current = current.next
}
return current
}
function insert(element, newElement) {
let preNode = this.find(element)
let current = new Node(newElement)
current.next = preNode.next
preNode.next = current
}
function remove() {
let current = this.head
console.log('remove')
//跳过两个，杀死一个
while (current.next.next != null && current.item != current.next.next.item) {
let temp = current.next.next
current.next.next = temp.next
current = temp.next
temp.next = null
}
return current
}
function display(flag, current) {
let crr = this.head
if (flag) {
while (crr.next.item != '1') {
console.log(crr.item)
crr = crr.next
}
} else {
//最后只剩两个直接输出
console.log(current.item)
console.log(current.next.item)
}
}
let Clist = new Llist()
//输入排序
for (let i = 1; i < 41; i++) {
Clist.insert(i.toString(), (i + 1).toString())
}
//先输出所有
Clist.display(1, null)
//通过remove返回最后杀死后的结果其中一个节点
Clist.display(0, Clist.remove()) //16,31//节点类
function Node(element) {
this.item = element
this.next = null
}
//循环列表需要修改一下构造函数，和遍历时候的判断条件
//构造函数如下；希望从后向前遍历，又不想要建立双向链表，就使用循环链表。
function Llist() {
this.head = new Node('1')
this.head.next = this.head
this.remove = remove
this.insert = insert
this.find = find
this.display = display
//..........
}
function find(number) {
let current = this.head
while (current.item != number) {
current = current.next
}
return current
}
function insert(element, newElement) {
let preNode = this.find(element)
let current = new Node(newElement)
current.next = preNode.next
preNode.next = current
}
function remove() {
let current = this.head
console.log('remove')
//跳过两个，杀死一个
while (current.next.next != null && current.item != current.next.next.item) {
let temp = current.next.next
current.next.next = temp.next
current = temp.next
temp.next = null
}
return current
}
function display(flag, current) {
let crr = this.head
if (flag) {
while (crr.next.item != '1') {
console.log(crr.item)
crr = crr.next
}
} else {
//最后只剩两个直接输出
console.log(current.item)
console.log(current.next.item)
}
}
let Clist = new Llist()
//输入排序
for (let i = 1; i < 41; i++) {
Clist.insert(i.toString(), (i + 1).toString())
}
//先输出所有
Clist.display(1, null)
//通过remove返回最后杀死后的结果其中一个节点
Clist.display(0, Clist.remove()) //16,31ts
function insertionSort(array) {
if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
console.time('插入排序耗时：')
for (let i = 1; i < array.length; i++) {
let stand = array[i]
console.log(`key=${stand}`)
let j = i - 1
while (j >= 0 && array[j] > stand) {
array[j + 1] = array[j]
console.log(`${array}`)
j--
}
array[j + 1] = stand
console.log(`第${i}轮遍历,最总结过${array}`)
}
console.timeEnd('插入排序耗时：')
return array
} else {
return 'array is not an Array!'
}
}
console.log(insertionSort([45, 23, 56, 778, 32, 5, 77, 4, 24]))
export {}function insertionSort(array) {
if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
console.time('插入排序耗时：')
for (let i = 1; i < array.length; i++) {
let stand = array[i]
console.log(`key=${stand}`)
let j = i - 1
while (j >= 0 && array[j] > stand) {
array[j + 1] = array[j]
console.log(`${array}`)
j--
}
array[j + 1] = stand
console.log(`第${i}轮遍历,最总结过${array}`)
}
console.timeEnd('插入排序耗时：')
return array
} else {
return 'array is not an Array!'
}
}
console.log(insertionSort([45, 23, 56, 778, 32, 5, 77, 4, 24]))
export {}ts
let LinkedList2 = (function () {
class Node {
constructor(element) {
this.element = element
this.next = null
}
}
//这里我们使用WeakMap对象来记录长度状态
const length = new WeakMap()
const head = new WeakMap()
class LinkedList2 {
constructor() {
length.set(this, 0)
head.set(this, null)
}
append(element) {
let node = new Node(element),
current
if (this.getHead() === null) {
head.set(this, node)
} else {
current = this.getHead()
while (current.next) {
current = current.next
}
current.next = node
}
let l = this.size()
l++
length.set(this, l)
}
insert(position, element) {
if (position >= 0 && position <= this.size()) {
let node = new Node(element),
current = this.getHead(),
previous,
index = 0
if (position === 0) {
node.next = current
head.set(this, node)
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
let l = this.size()
l++
length.set(this, l)
return true
} else {
return false
}
}
removeAt(position) {
if (position > -1 && position < this.size()) {
let current = this.getHead(),
previous,
index = 0
if (position === 0) {
head.set(this, current.next)
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
let l = this.size()
l--
length.set(this, l)
return current.element
} else {
return null
}
}
remove(element) {
let index = this.indexOf(element)
return this.removeAt(index)
}
indexOf(element) {
let current = this.getHead(),
index = 0
while (current) {
if (element === current.element) {
return index
}
index++
current = current.next
}
return -1
}
isEmpty() {
return this.size() === 0
}
size() {
return length.get(this)
}
getHead() {
return head.get(this)
}
toString() {
let current = this.getHead(),
string = ''
while (current) {
string += current.element + (current.next ? ', ' : '')
current = current.next
}
return string
}
print() {
console.log(this.toString())
}
}
return LinkedList2
})()let LinkedList2 = (function () {
class Node {
constructor(element) {
this.element = element
this.next = null
}
}
//这里我们使用WeakMap对象来记录长度状态
const length = new WeakMap()
const head = new WeakMap()
class LinkedList2 {
constructor() {
length.set(this, 0)
head.set(this, null)
}
append(element) {
let node = new Node(element),
current
if (this.getHead() === null) {
head.set(this, node)
} else {
current = this.getHead()
while (current.next) {
current = current.next
}
current.next = node
}
let l = this.size()
l++
length.set(this, l)
}
insert(position, element) {
if (position >= 0 && position <= this.size()) {
let node = new Node(element),
current = this.getHead(),
previous,
index = 0
if (position === 0) {
node.next = current
head.set(this, node)
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
let l = this.size()
l++
length.set(this, l)
return true
} else {
return false
}
}
removeAt(position) {
if (position > -1 && position < this.size()) {
let current = this.getHead(),
previous,
index = 0
if (position === 0) {
head.set(this, current.next)
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
let l = this.size()
l--
length.set(this, l)
return current.element
} else {
return null
}
}
remove(element) {
let index = this.indexOf(element)
return this.removeAt(index)
}
indexOf(element) {
let current = this.getHead(),
index = 0
while (current) {
if (element === current.element) {
return index
}
index++
current = current.next
}
return -1
}
isEmpty() {
return this.size() === 0
}
size() {
return length.get(this)
}
getHead() {
return head.get(this)
}
toString() {
let current = this.getHead(),
string = ''
while (current) {
string += current.element + (current.next ? ', ' : '')
current = current.next
}
return string
}
print() {
console.log(this.toString())
}
}
return LinkedList2
})()ts
function LinkedList() {
//Node类声明
let Node = function (element) {
this.element = element
this.next = null
}
//初始化链表长度
let length = 0
//初始化第一个元素
let head = null
this.append = function (element) {
//初始化添加的Node实例
let node = new Node(element),
current
if (head === null) {
//第一个Node实例进入链表，之后在这个LinkedList实例中head就不再是null了
head = node
} else {
current = head
//循环链表知道找到最后一项，循环结束current指向链表最后一项元素
while (current.next) {
current = current.next
}
//找到最后一项元素后，将他的next属性指向新元素node,j建立链接
current.next = node
}
//更新链表长度
length++
}
this.insert = function (position, element) {
//检查是否越界，超过链表长度或是小于0肯定不符合逻辑的
if (position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0
if (position === 0) {
//在第一个位置添加
node.next = current
head = node
} else {
//循环链表，找到正确位置，循环完毕，previous，current分别是被添加元素的前一个和后一个元素
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
//更新链表长度
length++
return true
} else {
return false
}
}
this.removeAt = function (position) {
//检查是否越界，超过链表长度或是小于0肯定不符合逻辑的
if (position > -1 && position < length) {
let current = head,
previous,
index = 0
//移除第一个元素
if (position === 0) {
//移除第一项，相当于head=null;
head = current.next
} else {
//循环链表，找到正确位置，循环完毕，previous，current分别是被添加元素的前一个和后一个元素
while (index++ < position) {
previous = current
current = current.next
}
//链接previous和current的下一个元素，也就是把current移除了
previous.next = current.next
}
length--
return current.element
} else {
return null
}
}
this.indexOf = function (element) {
let current = head,
index = 0
//循环链表找到元素位置
while (current) {
if (element === current.element) {
return index
}
index++
current = current.next
}
return -1
}
this.remove = function (element) {
//调用已经声明过的indexOf和removeAt方法
let index = this.indexOf(element)
return this.removeAt(index)
}
this.isEmpty = function () {
return length === 0
}
this.size = function () {
return length
}
this.getHead = function () {
return head
}
this.toString = function () {
let current = head,
string = ''
while (current) {
string += current.element + (current.next ? ', ' : '')
current = current.next
}
return string
}
this.print = function () {
console.log(this.toString())
}
}
//一个实例化后的链表，里面是添加的数个Node类的实例function LinkedList() {
//Node类声明
let Node = function (element) {
this.element = element
this.next = null
}
//初始化链表长度
let length = 0
//初始化第一个元素
let head = null
this.append = function (element) {
//初始化添加的Node实例
let node = new Node(element),
current
if (head === null) {
//第一个Node实例进入链表，之后在这个LinkedList实例中head就不再是null了
head = node
} else {
current = head
//循环链表知道找到最后一项，循环结束current指向链表最后一项元素
while (current.next) {
current = current.next
}
//找到最后一项元素后，将他的next属性指向新元素node,j建立链接
current.next = node
}
//更新链表长度
length++
}
this.insert = function (position, element) {
//检查是否越界，超过链表长度或是小于0肯定不符合逻辑的
if (position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0
if (position === 0) {
//在第一个位置添加
node.next = current
head = node
} else {
//循环链表，找到正确位置，循环完毕，previous，current分别是被添加元素的前一个和后一个元素
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
//更新链表长度
length++
return true
} else {
return false
}
}
this.removeAt = function (position) {
//检查是否越界，超过链表长度或是小于0肯定不符合逻辑的
if (position > -1 && position < length) {
let current = head,
previous,
index = 0
//移除第一个元素
if (position === 0) {
//移除第一项，相当于head=null;
head = current.next
} else {
//循环链表，找到正确位置，循环完毕，previous，current分别是被添加元素的前一个和后一个元素
while (index++ < position) {
previous = current
current = current.next
}
//链接previous和current的下一个元素，也就是把current移除了
previous.next = current.next
}
length--
return current.element
} else {
return null
}
}
this.indexOf = function (element) {
let current = head,
index = 0
//循环链表找到元素位置
while (current) {
if (element === current.element) {
return index
}
index++
current = current.next
}
return -1
}
this.remove = function (element) {
//调用已经声明过的indexOf和removeAt方法
let index = this.indexOf(element)
return this.removeAt(index)
}
this.isEmpty = function () {
return length === 0
}
this.size = function () {
return length
}
this.getHead = function () {
return head
}
this.toString = function () {
let current = head,
string = ''
while (current) {
string += current.element + (current.next ? ', ' : '')
current = current.next
}
return string
}
this.print = function () {
console.log(this.toString())
}
}
//一个实例化后的链表，里面是添加的数个Node类的实例ts
function mergeSort(arr) {
let len = arr.length
if (len < 2) {
return arr
}
let middle = Math.floor(len / 2)
let left = arr.slice(0, middle)
let right = arr.slice(middle)
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
let result = []
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
while (left.length) {
result.push(left.shift())
}
while (right.length) {
result.push(right.shift())
}
return result
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
console.log(mergeSort(arr))
export { merge, mergeSort }function mergeSort(arr) {
let len = arr.length
if (len < 2) {
return arr
}
let middle = Math.floor(len / 2)
let left = arr.slice(0, middle)
let right = arr.slice(middle)
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
let result = []
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
while (left.length) {
result.push(left.shift())
}
while (right.length) {
result.push(right.shift())
}
return result
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
console.log(mergeSort(arr))
export { merge, mergeSort }ts
function qSort(arr) {
if (arr.length == 0) {
return []
}
let left = []
let right = []
let pivot = arr[0]
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return qSort(left).concat(pivot, qSort(right))
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
console.log(qSort(arr))function qSort(arr) {
if (arr.length == 0) {
return []
}
let left = []
let right = []
let pivot = arr[0]
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return qSort(left).concat(pivot, qSort(right))
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
console.log(qSort(arr))ts
function selectionSort(arr) {
let len = arr.length
let minIndex, temp
console.time('选择排序耗时')
for (let i = 0; i < len - 1; i++) {
minIndex = i
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
//寻找最小的数
minIndex = j //将最小数的索引保存
}
}
;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
console.log(arr)
}
console.timeEnd('选择排序耗时')
return arr
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
console.log(selectionSort(arr)) //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]function selectionSort(arr) {
let len = arr.length
let minIndex, temp
console.time('选择排序耗时')
for (let i = 0; i < len - 1; i++) {
minIndex = i
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
//寻找最小的数
minIndex = j //将最小数的索引保存
}
}
;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
console.log(arr)
}
console.timeEnd('选择排序耗时')
return arr
}
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
console.log(selectionSort(arr)) //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]