前端常用的查詢和排序演算法等必會知識點
摘要：
function insertNumber(arr, x) {
//查詢到第一個大於x的數字
let b = newArr.find(e => e > x);
if (b === undefined) {
//...
function insertNumber(arr, x) {
//查詢到第一個大於x的數字
let b = newArr.find(e => e > x);
if (b === undefined) {
// 如果b不存在，證明x是最大的數字，push到陣列尾部
newArr.push(x);
} else {
//獲取b的index，把新的數字插入到b的位置
let bIndex = newArr.indexOf(b)
newArr.splice(bIndex, 0, x)
}
return arr;
}
複製程式碼
兩個有序數組合併成一個新的有序陣列
- 和插入一樣， 第一個解構，對第二個陣列進行遍歷迴圈插入到第一個陣列
function insert_some_numbers(arr1, arr2) {
//建立新陣列，並結構第一個陣列
var newArr = [...arr1];
for (var i = 0; i < arr2.length; i++) {
//獲取第二個陣列中的每一位
x = arr2[i];
//在新解構的陣列中查詢第一個比他大的陣列
let b = newArr.find(e => e > x);
//獲取到這個數字的索引並插入到他的前面
let bindex = newArr.indexOf(b)
newArr.splice(bindex === -1 ? newArr.length : bindex, 0, x)
}
return newArr;
}
let arr1 = [1, 2, 3, 4, 5, 6, 8, 9];
console.log(insert_some_numbers(arr1, [1, 2, 3]));
複製程式碼
二分查詢
- 最大查詢次數 Math.ceil(Math.log2(arr.length))
function binarySearch(arr, x) {
var left = 0; //左邊界
var right = arr.length - 1; //右邊界
var guess;// 遊標， 中間索引去小數點
while (left <= right) { // 左側邊界小於右側邊界才執行
guess = ((left + right) / 2) | 0;//遊標索引， 中間索引去小數點
if (arr[guess] === x) return guess // 當遊標索引就是查詢的X的話，返回遊標索引
else if (arr[guess] > x) right = guess - 1 // 遊標索引位 大於 x ， 右邊界移動到guess之前。
else left = guess + 1 // 遊標索引位 小於 x ， 右邊界移動到guess之後。
}
return -1; //未查詢到
}
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(
binarySearch(arr, 5)
)
複製程式碼
有序陣列插入新數字
- 模擬一個空位置迴圈比較，
- 從陣列尾部向前比較，前面的那一位比x大，比x大的那個數字索引+1，
- 再跟前面的一位作比較，如果比X小， p+1位索引就被x佔了
function insert_number_3(arr, x) {
//p是下一個待比較元素的索引
//p-1是空位
//p不能小於0, 當P小於0代表， x是最小的
let p = arr.length - 1;
while (p >= 0 && arr[p] > x) {
arr[p + 1] = arr[p];
p--;
}
arr[p + 1] = x;
}
let arr1 = [1, 2, 3, 4, 5, 6, 8, 9];
insert_number_3(arr1, 6)
console.log(arr1)
複製程式碼
插入排序
- 效能最差
- n^2/2 - n/2次比較
- 從陣列的第1索引位置，逐次向前比較
- 比較次數 1 + 2 + 3 + ··· + arr.length 次
function insertion_sort(arr) {
//第一位不用去作比較，只有一位的陣列可以看作為有序陣列
for (var i = 1; i < arr.length; i++) {
insert(arr, i, arr[i]);
}
}
function insert(arr, i, x) {
let p = i - 1; // p 作為被首先比較的元素
// arr[i] 也就是 x是待插入的元素
while (p >= 0 && arr[p] > x) {
// 當待插入的元素
arr[p + 1] = arr[p];
p--;
}
arr[p + 1] = x;
}
複製程式碼
氣泡排序
- 先找出最大的，再找出最小的
- 效能最差
- 排序次數： arr.length的等差數列求和次 ->n**n/2 -n/2 次
function bubble_sort(arr) {
//值交換函式
function swap(arr, x, j) {
var temp = arr[x];
arr[x] = arr[j];
arr[j] = temp;
}
//先找出最大的，再找出最小的
for (let i = arr.length - 1; i >= 1; i--) {
//從1開始，每一次都和前一位作比較。
for (let j = 1; j <= i; j++) {
arr[j] < arr[j - 1] && swap(arr, j-1, j)
}
}
}
const arr2 = [91, 60, 96, 9, 30, 20, 31, 77, 81, 24];
bubble_sort(arr2)
console.log(arr2);
複製程式碼
深度克隆
function deepClone2(origin, target) {
var target = target || ((origin instanceof Array) ? [] : {});
for (var prop in origin) {
if (origin.hasOwnProperty(prop)) {
if (typeof origin[prop] == 'object') {
if (Object.prototype.toString.call(origin[prop]) === '[object Array]') {
target[prop] = [];
} else {
target[prop] = {};
}
deepClone2(origin[prop], target[prop]);
} else {
target[prop] = origin[prop]
}
}
}
return target;
}
複製程式碼
合併排序
//將陣列分成兩個陣列，
// 索引 [a,b) 和 [b,c)
//合併函式部分，
function merge(arr, a, b, c) {
// 此時arr1 和 arr2 是 兩個有序陣列
let arr1 = arr.slice(a, b);
let arr2 = arr.slice(b, c);
//在兩個陣列後面佈置哨兵
arr1.push(Infinity);
arr2.push(Infinity);
//設定兩個陣列的比較位置的索引的遊標索引
// 如果這個數字被賦值，則索引+1
var i = 0, j = 0;
//迴圈給arr賦值
for (let k = a; k < c; k++) {
//k : 下一個寫入位置
//i ： arr1中的回寫位置
//j :arr2中的回寫位置
arr[k] = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++];
}
}
function mergeSort(arr, a, c) {
//判斷陣列長度是否為1
if (c - a < 2) { return };
const b = Math.ceil((a + c) / 2);
//左側部分遞迴
mergeSort(arr, a, b);
//右側部分遞迴
mergeSort(arr, b, c);
//執行拼接
merge(arr, a, b, c);
}
// 把陣列拆成一個，一個的陣列， 在執行拼接
複製程式碼