冒泡排序
Array.prototype.bubbleSort = function() {
// console.log(this)
for (let i = 0; i < this.length - 1; i++) {
for(let j = 0;j<this.length -1 - i; j+=1){ // -1 可以用j+1来获取 - i是为了缩小循环节省时间
if(this[j] > this[j+1]){
const temp = this[j] // 存储j
this[j] = this[j+1] // 切换 j 和 j+1元素的位置
this[j+1] = temp; // j+1 = j
}
}
}
}
const arr = [ 5,4,3,2,1]
arr.bubbleSort()
console.log(arr)两个嵌套循环
时间复杂度 O（n^2）
选择排序
选择排序的思路
找到数组中的最小值，选择它并将其放置在第一位。
接着找到第二小的值，选中它并将其放置在第二位。
以此类推，执行N-1轮
Array.prototype.slectionSort = function() {
for (let i = 0; i < this.length - 1; i++) {
let indexMin = i // 等于i 是为了缩减循环，因为找的是最小的值 每一轮都是最小的
for(let j = i;j<this.length; j+=1){ // 等于i 是为了缩减循环， 这个循环是为了找到最小值的下标
if(this[j] < this[indexMin]){
indexMin = j
}
}
if( indexMin !== i){ //优化 避免最小值的下标和当前下标相等
const temp = this[i]; // 进行替换
this[i] = this[indexMin]
this[indexMin] = temp
}
}
}
const arr = [ 5,4,3,2,1]
arr.slectionSort()
console.log(arr)两个嵌套循环
时间复杂度 O（n^2）
插入排序
插入排序的思路
从第二个数开始 往前比。
比它大舅往后排。
以此类推进行到最后一个数。
Array.prototype.insertionSotr = function() {
for(let i =1 ; i < this.length; i+=1){ // 拿数组的第二个元素和前一个对比 所以i =1
const temp = this[i] // 获取当前对比元素
let j = i; // 元素下标
while (j>0){
if(this[j-1] > temp){ // j-1 获取前一个元素的值 进行对比
this[j] = this[j-1] ; // 进行替换
}
else{
break; // 终止循环
}
j -= 1; //循环条件
}
this[j] = temp ; //进行插入
}
}
const arr = [ 5,4,3,2,1,6,9,8,7]
arr.insertionSotr()
console.log(arr)两个嵌套循环
时间复杂度 O（n^2）
归并排序
归并排序的思路
分：把数组劈成两半，在递归地对子数组进行“分”操作，直到分成一个个单独的数。
合：把两个数合并为有序数组，在对有序数组进行合并，直到全部子数组合并为一个完整数组
合并两个有序数组
新建一个空数组res,用于存放最终排序后的数组。、
比较两个有序数组的头部，较小者出对并推入res中。
如果两个数组还有值，就重复第二步。
Array.prototype.mergeSort = function() {
const rec =(arr) =>{
if(arr.length === 1) {return arr} // 预防死循环 并返回数组
const mid = Math.floor(arr.length / 2) // 获取中间下标
const left = arr.slice(0,mid) // 获取左边数组
const right = arr.slice(mid,arr.length);// 右边的数组
const orderLeft = rec(left) // 分隔左数组 得到有序数组
const orderRight = rec(right) // 分隔右数组 得到有序数组
const res = [];
while(orderLeft.length || orderRight.length){
if(orderLeft.length && orderRight.length){
// 如果左边的对头 小于 右边对头 那么左边的出对 否则 右边出对 然后进入res
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
}else if(orderLeft.length){ // 如果左边还有值
res.push(orderLeft.shift()) //那么不断的出对并进入数组
}else if(orderRight.length){ // 如果右边还有值
res.push(orderRight.shift()) //那么不断的出对并进入数组
}
}
return res
}
const res = rec(this)
res.forEach((n,i)=>{this[i] = n})
}
const arr = [ 5,4,3,2,1,6,9,8,7]
arr.mergeSort()
console.log(arr)分的时间复杂度是O（logN）
合的时间复杂度是O（n）
时间复杂度O(n* logN)
\
快速排序
分区： 从数组中任意选择一个 “基准”，所有比基准小的元素放在基准前面，比基准打的元素放在基准后面。
递归：递归地对基准前后的子数组进行分区
Array.prototype.quickSort = function() {
const rec =(arr) =>{
if(arr.length === 1){return arr}
// 分别存放 前后的数组
const left = []
const right = []
// 设置一个基准
const mid = arr[0]
//进行分区
for(let i =1; i<arr.length; i+=1){
if(arr[i] < mid){
left.push(arr[i])
}else{
right.push(arr[i])
}
}
return [...rec(left),mid,...rec(right)] //...用于取出参数对象中的所有可遍历属性，拷贝到当前对象之中
}
const res = rec(this)
res.forEach((n,i)=>{this[i] = n})
}
const arr = [ 5,4,3,2,1,6,9,8,7]
arr.quickSort()
console.log(arr)递归的时间复杂度是O（logN）
分区操作的时间复杂度是O（n）
时间复杂度 O（n*logN）
顺序搜索
遍历数组。
找到跟目标相等的元素，就返回它的下标。
遍历结束后，如果没有搜索到目标值，就返回 -1
Array.prototype.sequentialSearch = function(val){
for(let i=0;i<this.length;i+=1){
if(this[i] === item){
return i
}
}
return -1
}
const res = [1,2,3,4,5,6].sequentialSearch(2)时间复杂度O（n）
二分搜索
从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。
如果目标值大于或者小于中间元素，则在大于或者小于中间元素的那一半数组中搜索。
Array.prototype.binarySearch = function(val) {
// * 二分搜索的数组是有序的
let low = 0;
let high = this.length -1;
while( low <= high){
const mid = Math.floor((low+high) / 2)
const elemnt = this[mid]
if(elemnt < val){
low = mid + 1
}
else if(elemnt > val){
high = mid - 1
}else {
return mid
}
}
return -1
}
const arr = [1,2,3,4,5].binarySearch(2)
console.log(arr)时间复杂度O（logN）
