习题

排序

选择排序O(n2)

1. 遍历未排序的数
2. 找到最小（选择）
3. 记录最小值
4. 交换

function SelectionSort(arr){
    for(let i = 0; i < arr.length-1; i++) {
        minIndex = i
        for(let j = i+1 ; i<arr.length;j++){
            minIndex = arr[j]<arr[minIndex]?j:minIndex
        }
        swap(arr,i,minIndex)
    }
}

function swap(a,b){
    temp = a;
    a = b;
    b = temp;
}

冒泡排序O(n2)

1. 遍历
2. 相邻两个做比较

function BubbleSort(arr){
    for(let i= 0;i<length-1;i--){
        for (let j=0;j<arr.length-1-i;j++){
            if(arr[j]>arr[j+1]){
                swap(arr,j,j+1)
            }
        }
    }
}
// 异或
function swap(a,b){
    a = a^b
    b = a^b
    a = a^b
}

插入排序O(n2)

逐一拿起排序

function insertionSort(arr){
    for(let i= 1;i<arr.length;i++){
        for(let j=i-1; arr[j] > arr[j+1] && j >=0;j--){
            swap(arr,j,i)
        }
    }
}

归并排序

• 分治法：分割 集合

function mergeSort(arr){
    if(arr.length<=1) return arr;
    let middle = arr.length>>1 
    let left = mergeSort(arr.slice(0,middle))
    let right = mergeSort(arr.slice(middle))
    return merge(left,right)
}

function merge(left,right){
    result = []
    while(left.length > 0 && right.length>0){
        left[0]<right[0]?result.push(left.shift()):result.push(right.shift())
    }
    return result.concat(left,right)
}

快速排序

TODO

查找

二分查找

小片段

抑或位运算

// 交换
function swap(a,b){
    a = a^b
    b = a^b
    a = a^b
}

// 假设一个数组中有两个数组出现基数次,找到他们
// 解：eor=a^b
function findx(arr){
    let eor = 0
    for(x of arr){
        eor = eor^x
    }
    rightOne=eor&(~eor+1)  // 分类依据
    a = 0
    for(j of arr){
        // 加括号 先位运算 后判断
        if((j&rightOne) == 0){
            a = a^j
        }
    }
    b = eor^a
    console.log(a,b)
}