JS-经典排序算法

选择排序：
function selectSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let min = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        let temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
    return arr;
}

插入排序：
function insertSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i - 1; j >= 0; j--) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

希尔排序：
function shellSort(array) {
    let len = array.length;
    let gap = Math.floor(len / 2);
    while (gap > 0) {
        for (let i = gap; i < len; i++) {
            let current = array[i], preIndex = i - gap;
            while (preIndex >= 0 && array[preIndex] > current) {
                array[preIndex + gap] = array[preIndex];
                preIndex -= gap;
            }
            array[preIndex + gap] = current;
        }
        gap = Math.floor(gap / 2);
    }
    return array;
}

快速排序：
function quickSort(array, left, right) {
    if (left < right) {
        let i = left, j = right, mainNum = array[left];
        while (i < j) {
            while (i < j && array[j] > mainNum)
                j--;
            i < j ? array[i++] = array[j] : undefined;
            while (i < j && array[i] < mainNum)
                i++;
            i < j ? array[j--] = array[i] : undefined;
        }
        array[i] = mainNum;
        quickSort(array, left, i - 1);
        quickSort(array, i + 1, right);
    }
}

归并排序：
function MergeSort(array) {
    if (array.length < 2) {
        return array;
    }
    let mid = Math.floor(array.length / 2);
    let left = array.slice(0, mid);
    let right = array.slice(mid, array.length);
    return merge(MergeSort(left), MergeSort(right))
}
function merge(left, right) {
    let res = [], i = 0, j = 0;
    while (i < left.length && j < right.length) {
        left[i] < right[j] ? res.push(left[i++]) : res.push(right[j++]);
    }
    while (i < left.length)
        res.push(left[i++]);
    while (j < right.length)
        res.push(right[j++])
    return res;
}

二分查找：
function binarySearch(arr, target) {
  let left = 0, right = arr.length, mid;
  while(left <= right) {
    mid = Math.floor((left + right) / 2);
    if(arr[mid] > target) {
      right = mid - 1;
    } else if(arr[mid] < target) {
      left = mid + 1;
    } else {
      return mid;
    }
  }
  return -1;
}