排序和搜索算法

排序算法

冒泡排序

是比较所有相邻的两个项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序，就好像气泡升至表面一样。

function bubbleSort(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
            }
        }
    }
    return array;
}
function swap(array, a, b) {
    // const temp = array[a];
    // array[a] = array[b];
    // array[b] = temp;  经典方式
    [array[a], array[b]] = [array[b], array[a]];    //ES2015方式
}
function createNonSortedArray(size) {
    const array = [];
    for(let i = size; i > 0; i--) {
        array.push(i);
    }
    return array;
}
let array = createNonSortedArray(5);
console.log(array.join());    //5,4,3,2,1
array = bubbleSort(array);
console.log(array.join());    //1,2,3,4,5

注意当算法执行外循环的第二轮的时候，数字4 5已经是正确排序的了。尽管如此，在后续比较中，他们还一直进行着比较，即使这是不必要的。因此可以稍稍改进一下算法：

function modifiedBubbleSort(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
            }
        }
    }
    return array;
}

选择排序

选择排序是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

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

首先声明变量，接着外循环迭代数组。控制迭代轮次。我们假设本迭代轮次的第一个值为数组最小值。然后从当前i的值开始至数组结束，我们比较是否位置j的值比当前最小值小；如果是，则改变最小值至新最小值。当内循环结束，将得出数组第n小的值。最后，如果该最小值和原最小值不同，则交换其值。

插入排序

每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了，接着它和第二项进行比较——第二项是应该待在原位还是插入到第一项之前呢？这样，头两项就已正确排序，接着和第三项比较，以此类推。

function insertionSort(array) {
    let temp;
    for(let i = 1; i < array.length; i++) {
        let j = i;
        temp = array[i];
        while(j > 0 && array[j - 1] > temp) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = temp;
     }
    return array;
};

迭代数组来给第i项找到正确的位置，用i的值来初始化一个辅助变量并也将其值存储在一个临时变量中，便于之后将其插入到正确的位置上。下一步是要找到正确的位置来插入项目。只要变量j比0大（因为数组的第一个索引是0，没有负值的索引）并且数组中前面的值比待比较的值大，我们就把这个值移到当前位置上并减小j。

归并排序

归并排序是第一个可以实际使用的排序算法，复杂度为O(nlog(n))。是一种分而治之算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

由于是分治法，归并排序也是递归的。我们要将算法分为两个函数：第一个负责将一个大数组分为多个小数组并调用用来排序的辅助函数。

function mergeSort(array) {
    if(array.length > 1) {
        const middle = Math.floor(length / 2);
        const left = mergeSort(array.slice(0, middle));
        const right = mergeSort(array.slice(middle, length));
        array =  merge(left, right);
    }
    return array;
}

递归的停止条件是判断数组的长度是否为1，如果是则直接返回这个数组，因为他已经排序了。

如果数组长度大于1，就将其分成小数组。为此首先要找到数组的中间位，然后将数组分为left、right两个小数组。调用自身直到数组大小小于等于1.

下面是merge函数，负责合并和排序小数组来产生大数组，直到回到原始数组并已排序完成。

function merge(left, right) {
    let i = 0;
    let j = 0;
    const result = [];
    while(i < left.length && j < right.length) {
        result.push(left[i]<right[j] ? left[i++] : right[j++]);
    }
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

merge函数接收两个数组作为参数，并将它们归并为一个大数组。排序发生在归并过程中。首先需要声明归并过程要创建的新数组以及用来迭代两个数组left和right所需的两个变量。迭代两个数组的过程中，我们比较left数组的项是否比来自right数组的项小。如果是，将该项从left数组添加至归并结果数组，并递增用于迭代数组的控制变量，否则，从right数组添加项并递增用于迭代数组的控制变量。

接下来将left数组所有剩余的项添加到归并数组中，right数组也是一样，最后将归并数组作为结果返回。

快速排序

复杂度为O(nlog(n))，且性能较好。使用分而治之的方法，将原始数组分为较小的数组。

1. 首先从数组中选择一个值作为主元（pivot），也就是数组中间的那个值。
2. 创建两个指针（引用），左边一个指向数组第一个值，右边一个指向数组最后一个值。移动左指针直到我们找到一个比主元大的值，接着移动右指针直到找到一个比主元小的值，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，比主元大的值都排在主元之后。这一步叫划分（partition）操作。
3. 接着，算法对划分后的小数组（较主元小的值组成子数组，较主元大的值组成的子数组）重复之前的两个步骤，直到数组已完全排序。

function quickSort(array) {
    return quickSort(array, 0, array.length - 1);
}

声明一个主方法来调用递归函数，传递待排序数组，以及索引0及其最末的位置作为参数。

function quick(array, left, right) {
    //用于划分更小的数组
    let 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);
        }
    }
    return array;
}

首先声明index，该变量能帮助我们将子数组分离为较小值数组和较大值数组。这样就能再次递归地调用quick函数了。partition函数返回值将赋值给index。

1.划分过程

首先要选择主元，有好几种方式，最简单的一种是选择数组的第一个值。然而，研究表明对于已排序的数组，这不是一个好选择，它将导致该算法的最差表现。另一种方式是随机选择数组的一个值或是选择中间的值。

function partition(array, left, right) {
    const pivot = array[Math.floor((right + left) / 2)];
    let i = left;
    let j = right;
    while(i <= j) {
        while(array[i] < pivot) {i++};
        while(array[j] > pivot) {j--};
        if(i <= j) {
            swap(array, i, j);
            i++;
            j--;
        }
    }
    //返回左指针的索引，用来在quick函数中创建子数组。
    return i;
}

在本实现中，我们选择中间值作为主元。我们初始化两个指针：left，初始化为数组第一个元素；right，初始化为数组最后一个元素。

只要left和right指针没有相互交错，就执行划分操作。首先移动left指针直到找到一个比主元大的元素，移动right指针直到找到一个比主元小的元素的。

当左指针指向的元素比主元大且右指针指向的元素比主元小，并且此时左指针索引没有右指针索引大时就交换它们。

划分结束后返回左指针的索引，用来在quick函数中创建子数组。

搜索算法

顺序搜索

将每一个数据结构中的元素和我们要找的元素作比较，是一种低效的搜索算法。

const DOES_NOT_EXIST = -1;
function sequentialSearch(array, value) {
    for(let i = 0; i < array.length; i++) {
        if(value == array[i]){
            return i;
        }
    }
    return DOES_NOT_EXIST
}

二分搜索

要求数据结构已排序。

function binarySearch(array, value) {
    //开始先要对数组排序，这里选择了快速排序
    const sortedArray = quickSort(array);
    //设置边界指针
    let low = 0;
    let high = sortedArray.length - 1;
    while(low <= hign) {
        const mid = Math.floor((low + hign) / 2);
        const element = sortedArray[mid];
        if(element < value) {
            low = mid + 1;
        } else if(element > value) {
            hign = mid - 1;
        } else {
            return mid;
        }
    }
    return DOES_NOT_EXIST;
}

内插搜索

是二分搜索的改良版，二分搜索总是检查mid位置上的值，而内插搜索可能会根据要搜索的值检查数组中的不同地方。

1. 使用position公式选中一个值；
2. 如果这个值是待搜索值，那么算法执行完毕；
3. 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找；
4. 如果待搜索值比选中值要大，则返回步骤1并在选中值右边的子数组中寻找；

function interpolationSearch(array,value) {
    let low = 0;
    let hign = array.length - 1;
    let position = -1;
    let delta = -1;
    while(low <= hign && value >= array[low] && value <= array[hign]) {
    }
}