简介
- 排序： 把某个乱序的数组变成升序或者降序的数组
- 搜索：找出数组中某个元素的下标
JS中的排序和搜索
- JS中的排序：数组的 sort 方法
- JS中的搜索：数组的 indexOf 方法
排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- ...
搜索算法
- 顺序搜索
- 二分搜索
- ...
1. JavaScript 实现：冒泡排序
image.png
image.png
Array.prototype.bubbleSort = function() {
console.log(this);
for(let i = 0; i< this.length -1; i += 1) {
for(let j = 0; j< this.length -1 - i; j += 1) {
if(this[j] > this[j+1]) {
const temp = this[j];
this[j] = this[j+1];
this[j+1] = temp;
}
}
}
}
const arr = [5,2,4,1];
arr.bubbleSort();
时间复杂度：O(n^2) // 两个嵌套循环
2. JavaScript 实现：选择排序
image.png
Array.prototype.selectionSort = function() {
for(let i = 0; i< this.length -1; i += 1) {
let indexMin = i;
for(let j = i; j< this.length; j += 1) {
if(this[j] > this[indexMin]) {
indexMin = j;
}
}
if(indexMin !== i) {
const temp = this[i];
this[i] = this[indexMin];
this[indexMin] = temp;
}
}
}
const arr = [5,2,4,1];
arr.selectionSort();
时间复杂度：O(n^2) // 两个嵌套循环
3. JavaScript 实现：插入排序
image.png
Array.prototype.insertionSort = function() {
for(let i = 1; i< this.length; i += 1) {
const temp = this[i];
let j = i ;
while(j > 0) {
if(this[j-1] > temp) {
this[j] = this[j-1];
} else {
break;
}
j -= 1;
}
this[j] = temp;
}
};
const arr = [5,2,4,1];
arr.insertionSort();
时间复杂度：O(n^2) // 两个嵌套循环, 但是在小型数组时，性能更好
4. JavaScript 实现：归并排序
image.png
image.png
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.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,8,0,1,2,3];
arr.mergeSort();
- 分的时间复杂度：O(logn) //
- 合的时间复杂度：O(n) //
- 时间复杂度 O(n*logN)
5. JavaScript 实现：快速排序
image.png
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,2,4,1];
arr.quickSort();
console.log(arr);
- 递归时间复杂度：O(logn) //
- 分区的时间复杂度：O(n) //
- 时间复杂度 O(n*logN)
6. JavaScript 实现：顺序搜索
image.png
Array.prototype.sequentialSearch = function(item) {
for (let i = 0; i < this.length; i++) {
if(this[i] === item) {
return i;
}
}
return -1;
}
const res = [1,2,3,4,5].sequentialSearch(1);
- 时间复杂度 O(n)
7. JavaScript 实现：二分搜索（折半搜索，前提是数组是有序的）
image.png
Array.prototype.binarySearch = function(item) {
let low = 0;
let hight = this.length - 1;
while(low <= hight) {
const mid = Math.floor((low + hight) / 2);
const element = this[mid];
if(element < item) {
low = mid +1
} else if(element < item) {
hight = mid -1
} else {
return mid;
}
}
return -1;
}
const res = [1,2,3,4,5].binarySearch(0);
- 时间复杂度 O(logN)
Leecode 21. 合并两个有序链表
image.png
image.png
image.png
function ListNode(val) {
this.val = val;
this.next = null;
}
var mergeTwoLists = function(l1, l2) {
const res = new NodeList(0);
let p = res;
let p1 = l1;
let p2 = l2;
while(p1 && p2) {
if(p1.val < p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
// 如果某个链表还有值，拼接到新链表的结尾即可
if(p1) {
p.next = p1;
}
if(p2) {
p.next = p2;
}
return res.next;
}
时间复杂度O(n)
空间复杂度O(1)
Leecode 374. 猜数字大小
image.png
image.png
image.png
// 0 mid
// 1 higher than the guess number
//-1 lower than the guess number
//var guess = function(num) {}
var guessNumber = function(n) {
let low = 1;
let heigh = n;
while(low <= heigh) {
const mid = Math.floor((low + heigh) / 2);
const res = guess(mid);
if(res === 0) {
return mid;
} else if(res === 1) {
low = mid + 1
} else {
heigh = mid - 1
}
}
}
时间复杂度O(n) && 空间复杂度O(1)
