對數(shù)
如果a^x=N(a>0,且a≠1)尾膊，則x叫做以a為底N的對數(shù),記做x=log(a)(N)，其中a要寫于log右下鹅搪。其中a叫做對數(shù)的底禀苦，N叫做真數(shù) 蔓肯。通常我們將以10為底的對數(shù)叫做常用對數(shù)，以e為底的對數(shù)稱為自然對數(shù)振乏。
「基本知識」：
時間復雜度
通常我們會用大O來表示一個算法的時間復雜度蔗包，即 某個算法的時間增量。
例如： 要在 一個 5個元素的數(shù)組中 查找 1個數(shù) 慧邮， 不管從第幾個元素開始查找 要想 找到這個數(shù) 调限，最多需要 5次查找操作 舟陆，最少需要1次 如果是 6個元素的數(shù)組，要找到這個數(shù) 則 最多 6次 耻矮，最少1次秦躯。 通過 大O表示 時間復雜度就是 O(n), 即 每增加 n個元素 就需要 多查找n次 ，算法的時間增量就是o(n).通常大O表示算法復雜度增量 都是以 最壞的 情況為 準裆装。
簡單查找
在一個數(shù)組中挨個查找某個數(shù)據踱承，這種查找就是簡單查找
比如 5個元素的數(shù)組中 查找 1個數(shù) ，從頭到尾查找哨免，最多需要查找五次茎活。
「時間復雜度」：O(n) , 算法時間是線性增長的。 n個數(shù) 最多查找n次 最少查找1次琢唾。
「例子」：
* 簡單查找
* @param arr 目標數(shù)組
* @param num 要查找的數(shù)字
*/
function simpleSearch(arr: number[], num: number):number {
for (let one of arr) {
if (one === num) {
return one;
}
}
return -1;
}
二分查找
「前提」：已經排序的數(shù)據
「邏輯」：在排好序（降序如 1,2,3）的 容器中 每次選擇 容器的 中間或者+1或者-1的數(shù)字载荔，進行比較，如果 該數(shù)字 大于要查找的數(shù)字 采桃，那么以該數(shù)字索引-1對應的值為最大元素身辨，以原來最小的值為最小值 ，繼續(xù) 折中 查找芍碧，如果 該數(shù)字 小于要查找的數(shù)字 則以 該數(shù)字索引+1所對應的值為最小值 ，原最大值為最大值 再次折中查找 号俐，一直到最小數(shù)索引等于最大數(shù)索引 即 找到對應的值或者 查找完 沒有該值為止泌豆。
「時間復雜度」：O(log2n) 以2為底 真數(shù)為n的對數(shù)。
比如 在 n個已經排好序的數(shù)中查找某個數(shù)據吏饿，每次折中查找 踪危，那么找到這個數(shù)的 最多次數(shù)是 log2n 次 。如果 n是 10 那么 找到這個數(shù) 最多需要4次 即 2 * 2 * 2 * 2猪落。因為222是 8不到10 不能完全查完容器的數(shù)據贞远，所以還需要折中查找一次，所以是 4次
「例子」：
* arr 目標數(shù)組
* num 要查找的數(shù)字
*/
function binarySearch(arr: number[], num: number):number {
let low = 0;
let hight = arr.length - 1;
let count = 0;
while (low <= hight) {
count++;
let mid = Math.floor((low + hight) / 2);
let guess = arr[mid];
if (guess === num) return guess;
if (guess > num) {
hight = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
選擇排序
「邏輯」：需要遍歷n-1趟笨忌，n表示容器中n個元素蓝仲，每趟從待排序的記錄序列中選擇最小或最大的數(shù)字放到已排序表的最前位置，直到全部排完官疲。 每趟交換一次數(shù)據
「時間復雜度」：log(n*n) 最多需要 n * n 次排完
「穩(wěn)定性」：不穩(wěn)定
「例子」：
* 選擇排序 從小到大
* @param arr 容器
*/
function selectionSort(arr: number[]) {
let len = arr.length;
for (let i = 0; i < len - 1 ; i++) {
//設定第一個元素為最小元素
let minindex = i;
for (let j = i + 1; j < len ; j++) {
if (arr[minindex] > arr[j]) {
minindex = j;
}
}
//每次遍歷找出最小值與上一次的最小值交換
if (i != minindex) {
let temp = arr[minindex];
arr[minindex] = arr[i];
arr[i] = temp;
}
}
}
冒泡排序
「邏輯」：在要排序的一組數(shù)中袱结，對當前還未排好序的范圍內的全部數(shù)，對相鄰的兩個數(shù)依次進行比較和調整途凫，讓較大的數(shù)往下沉垢夹，較小的往上冒。即：每當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時维费，就將它們互換果元。 需要遍歷 n-1趟促王，每趟 需要對比 n- 當前排序索引-1 次。每趟 交換 n-當前排序索引 -1次 數(shù)據
「時間復雜度」：log(n*n) 最多需要 n * n 次排完
「穩(wěn)定性」：穩(wěn)定
「例子」：
* 冒泡排序 從小到大
* @param arr
*/
function bubbleSort(arr: number[]) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - i - 1; j++) { // -i 是 排除已經沉到最下面的數(shù)而晒，沒必要再次比較蝇狼。
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
快速排序
「邏輯」：
(1)首先設定一個分界值，通過該分界值將數(shù)組分成左右兩部分欣硼。
(2)將大于或等于分界值的數(shù)據集中到數(shù)組右邊题翰，小于分界值的數(shù)據集中到數(shù)組的左邊。此時诈胜，左邊部分中各元素都小于或等于分界值豹障，而右邊部分中各元素都大于或等于分界值。
(3)然后焦匈，左邊和右邊的數(shù)據可以獨立排序血公。對于左側的數(shù)組數(shù)據，又可以取一個分界值缓熟，將該部分數(shù)據分成左右兩部分累魔，同樣在左邊放置較小值，右邊放置較大值够滑。右側的數(shù)組數(shù)據也可以做類似處理垦写。
(4)重復上述過程，可以看出彰触，這是一個遞歸定義梯投。通過遞歸將左側部分排好序后，再遞歸排好右側部分的順序况毅。當左分蓖、右兩個部分各數(shù)據排序完成后，整個數(shù)組的排序也就完成了尔许。
「時間復雜度」：最好情況 nlog(2n),最差情況log(n*n)
「理想的情況是」：每次劃分所選擇的中間數(shù)恰好將當前序列幾乎等分么鹤，經過log2n趟劃分，便可得到長度為1的子表味廊。這樣蒸甜，整個算法的時間復雜度為O(nlog2n)。
「最壞的情況是」：每次所選的中間數(shù)是當前序列中的最大或最小元素余佛，這使得每次劃分所得的子表中一個為空表迅皇，另一子表的長度為原表的長度-1。這樣衙熔，長度為n的數(shù)據表的快速排序需要經過n趟劃分登颓，使得整個排序算法的時間復雜度為O(n*n)
「穩(wěn)定性」：不穩(wěn)定
「例子」：
* 快速排序
* @param array 輸入待排序數(shù)組
* @returns 排序后的數(shù)組
*/
quickSort(array:number[]) {
const sort = (arr, left = 0, right = arr.length - 1) => {
if (left >= right) {//如果左邊的索引大于等于右邊的索引說明整理完畢
return
}
let low = left
let index = right
const baseVal = arr[right] // 取無序數(shù)組最后一個數(shù)為基準值
while (low < index) {//把所有比基準值小的數(shù)放在左邊大的數(shù)放在右邊
//找到一個比基準值大的數(shù)交換
while (low < index && arr[low] <= baseVal) {
low++
}
arr[index] = arr[low] // 將較大的值放在右邊如果沒有比基準值大的數(shù)就是將自己賦值給自己（i 等于 j）
while (low < index && arr[index] >= baseVal) { //找到一個比基準值小的數(shù)交換
index--
break
}
arr[low] = arr[index] // 將較小的值放在左邊如果沒有找到比基準值小的數(shù)就是將自己賦值給自己（i 等于 j）
}
arr[index] = baseVal // 將基準值放至中央位置完成一次循環(huán)（這時候 j 等于 i ）
sort(arr, left, index-1) // 將左邊的無序數(shù)組重復上面的操作
sort(arr, index+1, right) // 將右邊的無序數(shù)組重復上面的操作
}
sort(array)
return array
}
