排序和搜索算法

[funnycoderstar]

排序算法

// 交换位置
let swap = function(index1, index2) {
   [array[index1], array[index2]] = [array[index2], array[index1]]
}

1.冒泡排序

比较任何两个相邻的值, 如果第一个比第一个大,则交换他们;
复杂度为O(n^2)

let bubbleSort = function() {
    let len = array.length;
    for(let i = 0; i < len; i++) {
        for(let j = 0; j < len - 1;j++ ) {
            if(array[j] > array[j+1]) {
                swap(j, j+1);
            }
        }
    }
}
// 升级后的冒泡排序
let modifiedBubbleSort = function() {
    let len = array.length;
    for(let i = 0; i < len; i++) {
        for(let j = 0; j < len - 1 - i;j++ ) {
            if(array[j] > array[j+1]) {
                swap(j, j+1);
            }
        }
    }
}

2.选择排序

找到最小的值放第一位, 找到第二小的值放第二位;
复杂度为O(n^2)

// 选择排序
let selectionSort = function() {
   let len = array.length;
   let indexMin;
    for(let i = 0; i < len -1; i++) {
        let indexMin = i;
        for(let j = i; j < len; j++) {
            if(array[indexMin] > array[j]) {
                indexMin = j;
            }
        }
        if( i !== indexMin) {
            swap(i, indexMin);
        }
    }
}

3.插入排序

// 插入排序
this.insertionSort = function() {
    let len = array.length;
    let j;
    let temp;
    for(let i = 0; i < length; i++) {
        j = i;
        temp = array[i];
        while( j > 0 && array[j - 1] > temp) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = temp;
    }
}

4.归并排序

let mergeSort = function() {
    array = mergeSortRec(array);
}
var mergeSortRec = function(array) {
    let len = array.length;
    if(length === 1) {
        return array;
    }
    var mid = Math.floor(length / 2);
    var left = array.slice(0, mid);
    var right = array.slice(mid, length);
    return merge(mergeSortRec(left), mergeSortRec(right))
}
var merge = function(left, right) {
    let result = [];
    let il = 0;
    let ir = 0;
    while(il < left.length && ir < right.length) {
        if(left[il] < right[ir]) {
            result.push(left[il++])
        } else {
            result.push(left[ir++])
        }
    }
    while(il < left.length) {
        result.push(left[il++]);
    }
    while(ir < right.length) {
        result.push(right[ir++]);
    }
    return result;
}

5.快速排序

this.quickSort = function() {
    quick(array, 0, array.length - 1);
}
var quick = function(array, left, right) {
    // 从数组中选择一项作为主元
    var index;
    if(array.length > 1) {
        index = partition(array, left, right);
        if(left  < index - 1)) {
            quick(array, left, index - 1);
        }
        if(index < right) {
            quick(array, index, right);
        }
    }
}
var partition = function(array, left, right) {
    // 选用中间项作为主元
    var pivot = array[Math.floor(left + right) / 2]],
    // left, 低,初始为数组中的第一个元素
    i = left,
    // right, 高, 初始为数组
    j = right;
    while(i <= j) {
        // 移动left指针直到找到一个元素比主元大
        while(array[i] < pivot) {
            i++;
        }
        // 移动right指针直到找到一个元素比主元小
        while(array[j] > pivot) {
            j--;
        }
        // 当左指针指向的元素比主元大且右指针指向的元素比主元小, 并且左指针索引没有右指针索引大, 则交换它们, 移动两个指针
        if(i <= j) {
            swap(array, i , j);
            i++;
            j--;
        }
    }
    return i;
}

对原数组操作，不占用额外空间；
先排一次序，找到index， index左边的都比arr[index]小，右边的都比arr[index]大
然后左右分别重复上一个排序做法

6.堆排序

this.heapSort = function() {
    var heapSize = array.length;
    // 构造一个满足array[parent[i]] >= array[i]的堆结构
    buildHeap(array);
    while(heapSize > 1) {
        heapSize--;
        // 交换堆里面第一个元素(数组中较大的值)和最后一个元素的位置
        swap(array, 0, heapSize);
        // 再次将数组转成堆, 找到当前堆的根节点(较小的值), 重新放在底部
        heapify(array, heapSize, 0);
    }
}
var buildHeap = function(array) {
    var heapSize = array.length;
    for(var i = Math.floor(array.length / 2); i >= 0; i--) {
        heapify(array, heapSize, 0);
    }
}
var heapify = function(array, heapSize, i) {
    var left = i * 2 + 1,
    right = i * 2 + 2,
    largest = i;
    if(left < heapSize && array[left] > array[largest]) {
        largest = left;
    }
    if(right < heapSize && array[right] > array[largest]) {
        largest = right;
    }
    if(largest !== i) {
        swap(array, i, largest);
        heapify(array, heapSize, largest);
    }
}

7.分布式排序

之前介绍的排序方法都是在不借助辅助数据结构的情况下对数组进行排序
分布式排序算法是: 原始数组中的数据会分发到多个中间结构(桶), 再合起来放回原始数组
最著名的分布式算法有计数排序, 桶排序和基数排序

搜索算法

1.顺序搜索

this.sequentialSearch = function(item) {
    for(let i = 0; i < array.length; i++) {
        if(item === array[i]) {
            return i;
        }
    }
    return -1;
}

2.二分搜索

1.选择数组中的中间值
2.如果选中值是待搜索值, 那么算法执行完毕
3.如果待搜索值比选中值要小, 则返回步骤1并在选中值左边的子数组中寻找
4.如果待搜索值比选中值要大, 则返回步骤1并在选中值右边的子数组中寻找

this.binarySearch = function(item) {
    this.quickSort();
    let low = 0;
    let high = nums.length - 1;
    while(low <= high) {
        const mid = Math.floor((low + high)/2);
        const element = nums[mid];
        
        if(element < target) {
            low = mid + 1;
        } else if(element > target) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}