[TOC]
# 題1、交換兩個數的實現方法？
答：
~~~
let a = 12
let b = 14
?
// 寫法一、使用中間變量
let tmp = a
a = b
b = tmp
?
// 寫法二、數組賦值
[a,b] = [b,a]
~~~
# 題2、寫出冒泡排序法？
答：思路：雙層循環，兩兩比較，判斷、交換。
最壞事件復雜度： `O(n^2)`
~~~
// 思路： 先比較一輪一次，然后用for循環比較一輪多次，然后再加for循環比較多輪多次
let arr = [8, 11, 9, 10, 3, 8, 343, 1, 99, 23, 65]
// 比較輪數
for (var i = 0; i < arr.length; i++) {
? ?// 每輪比較次數，次數 = 長度 - 1 - 此時的輪數
? ?for (var j = 0; j < arr.length - 1 - i; j++) {
? ? ? ?// 相鄰元素兩兩對比，元素交換，大的元素交換到后面
? ? ? ?if (arr[j] > arr[j + 1]) {
? ? ? ? ? ?// 交換
? ? ? ? ? ?// [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
? ? ? ? ? ?let kong = arr[j];
? ? ? ? ? ?arr[j] = arr[j + 1];
? ? ? ? ? ?arr[j + 1] = kong;
? ? ? }
? }
}
~~~
# 題3、寫出折半查找法？
答：前提：只能對已經 `排好序` 的數據使用折半查找法。
思路：每次和中間的元素查找，如果查找的元素比它大，就向右查找中間的，如果小就向左查找中間的。
時間復雜度： O(logn)
代碼演示
~~~
// 參數一、有序數組
// 參數二、要查找的數字
// 參數三、開始的下標
// 參數四、結束的下標
function halfSearch(arr, key, left, right) {
? ?let mid // 中間位置的坐標
? ?while (right > left) {
? ? ? ?// 計算中間元素的下標
? ? ? ?mid = Math.floor((left + right) / 2)
? ? ? ?// 如果找到了就直接返回下標
? ? ? ?if (key == arr[mid]) {
? ? ? ? ? ?return mid
? ? ? } else if (key < arr[mid]) {
? ? ? ? ? ?// 右邊界變為中間元素-1
? ? ? ? ? ?right = mid - 1
? ? ? } else if (key > arr[mid]) {
? ? ? ? ? ?left = mid + 1
? ? ? }
? }
? ?// 沒找到
? ?return -1
}
?
let arr = [1, 4, 7, 8, 12, 34, 66, 212, 6767, 23428]
console.log(halfSearch(arr, 4, 0, arr.length - 1))
~~~
