校园网站建设标书,靖江有哪些做网站的,建立网站需要多少钱责任y湖南岚鸿联系,wordpress post存储目录1 插入排序2 堆排序3 归并排序4 快速排序5 冒泡排序6 选择排序1 插入排序
时间复杂度O(n2)O(n^2)O(n2) 空间复杂度 O(1) 稳定
从第一个元素开始#xff0c;认为左边的序列是有序的#xff0c;从有序部分的最后一个向前比较#xff0c;如果当前元素小于有序部分就交换认为左边的序列是有序的从有序部分的最后一个向前比较如果当前元素小于有序部分就交换否则比较下一个元素。
function insertMerge(arr) {for(let i 1; i arr.length; i) {let target ifor (let j i-1; j 0; j--) {if (arr[target] arr[j]) { // 无序 交换元素[arr[target], arr[j]] [arr[j], arr[target]]target j // 交换之后target变为j} else {break // 有序 直接i}}}return arr
}
let arr [1,5,2,4,3,6,8,7]
console.log(insertMerge(arr));2 堆排序
时间复杂度O(n)O(n)O(n) 空间复杂度 O(1) 不稳定
先建堆然后每次让数组的最后一个元素和第一个元素进行交换交换之后调整堆。注意每一轮交换之后找到一个最大值放在了原数组的末尾下次交换这个元素不参与相当于原数组长度-1。
建堆是从最后一个非叶子节点开始也就是 (len/2-)1依次向上调整
调整的过程是拿目标节点和两个子节点中最大的值比较如果子节点大就交换目标节点变成较大的子节点否则已符合堆结构进行下一轮调整。
/*** 完全二叉树的最后一个非叶子节点是 Math.floor(len/2)-1* 孩子节点的 2*i1 和 2*i2*/
function heapSort(arr) {// 建堆 找到一个最大值createHeap(arr, 0, arr.length)// console.log(arr);// 每一轮跳过一个最后的最大值for (let i arr.length-1; i 0; i--) {// 每次交换第一个元素和该轮数组的最后一个元素// 最后一个元素是最大值 下一轮只需要比较之前的序列 最后一个元素变成了i-1[arr[i], arr[0]] [arr[0], arr[i]]// i 是数组的长度adjust(arr, 0, i)}return arr
}
function createHeap(arr) {const len arr.length// 从最后一个非叶子节点开始调整const start Math.floor(len/2)-1for(let i start; i 0; i--) {adjust(arr, i, len)}
}
function adjust(arr, target, len) {for (let i 2*target1; i len; i i*21) {if (i 1 len arr[i1] arr[i]) {i i 1}if (arr[target] arr[i]) {[arr[target], arr[i]] [arr[i], arr[target]]target i} else {break}}
}let arr [1,3,2,5,3,6,2,0]
console.log(heapSort(arr))3 归并排序
时间复杂度O(nlogn) 空间复杂度O(n) 稳定
分割 将数组从分成左右两个数组然后递归的分割知道数组的长度小于2合并 当左右两个数组有序的时候合并两个数组。创建一个空数组temp比较左右两边的数组小值加入到temp中。若左右数组有一个为空那么此时另一个数组一定大于temp中的所有元素直接将其所有元素加入temp。 然后将tmp的值一一传递给原数组
function mergeSort(arr, left, right, tmp) {if (left right) return arrconst mid Math.floor((leftright)/2)mergeSort(arr, left, mid, tmp)mergeSort(arr, mid1, right, tmp)merge(arr, left, right, tmp)return arr
}function merge(arr, left, right, tmp) {const mid Math.floor((leftright)/2)let leftIndex leftlet rightIndex mid 1let tmpIndex 0while (leftIndex mid rightIndex right) {if (arr[leftIndex] arr[rightIndex]) {tmp[tmpIndex] arr[leftIndex]} else {tmp[tmpIndex] arr[rightIndex]}}while (leftIndex mid) {tmp[tmpIndex] arr[leftIndex]}while (rightIndex right) {tmp[tmpIndex] arr[rightIndex]}tmpIndex 0for (let i left; i right; i) {arr[i] tmp[tmpIndex]}
}let arr [3,4,2,1,5,0]
mergeSort(arr, 0, arr.length-1, [])
console.log(arr)4 快速排序
时间复杂度平均O(nlogn)最坏O(n2)O(n^2)O(n2)实际上大多数情况下小于O(nlogn)
空间复杂度:O(logn)递归调用消耗
快速排序是每次找到一个基准元素左右两边分别和基准元素比较如果左边元素小于基准元素左指针向右移动如果右边元素大于基元素右指针向左移动。否则就交换左右两边的元素。当左右指针相遇相遇处即是基准元素所在的位置将基准元素交换到该位置。基准元素切分出了左右两边左边都比基准元素小右边都比基准元素大。
function quickSort(arr, left, right) {if (left right) returnlet i left, j right, pivot arr[left]while (i j) {while (i j arr[j] pivot) {j--}while (i j arr[i] pivot) {i}swap(arr, i, j)}swap(arr, left, i)quickSort(arr, left, i-1)quickSort(arr, i1, right)
}function swap(arr, i, j) {const tmp arr[i]arr[i] arr[j]arr[j] tmp
}const arr [3,2,4,1,5,6,8]
quickSort(arr, 0, arr.length-1)
console.log(arr)5 冒泡排序
时间复杂度O(n2)O(n^2)O(n2) 空间复杂度O(1) 不稳定 每次将一个最大值沉底下一次比较不考虑沉底的元素
function bubble(arr) {const len arr.length// 将第i个最大值沉底for (let i 0; i len; i) {// 排除沉底元素 进行比较for (let j 0; j len-i-1; j) {// 比较的是内层循环if (arr[j1] arr[j]) {[arr[j1], arr[j]] [arr[j], arr[j1]]}}}return arr
}
const arr [4,5,2,1,3]
bubble(arr)
console.log(arr)6 选择排序
时间复杂度O(n2)O(n^2)O(n2) 空间复杂度O(1) 不稳定
每次选出最小的元素放在未排序的部分的首位
/*** 每次选出最小的元素放在首位*/
function selectSort(arr) {const len arr.lengthlet minIndexfor (let i 0; i len; i) {minIndex ifor (let j i1; j len; j) {if(arr[minIndex] arr[j]) {minIndex j}}[arr[i], arr[minIndex]] [arr[minIndex], arr[i]]}
}const arr [1,3,2,1,5,6,7]
selectSort(arr)
console.log(arr)
