虽然前端对于算法的要求并不高，但是工作和面试偶尔还是会遇到排序算法和二分查找法。笔者通过这篇文章对排序和查找简单总结，既是总结笔记以便以后参考，也是供大家一起学习交流。
注：以下所有排序都是由小到大升序排列。
冒泡排序
冒泡算法原理是数组里每相邻的两个数相比较，如果两数中后者小于前者，则交换位置，否则不变，这样一次遍历下来，数组中最后一个数是最大的数，这样的遍历进行arr.length（数组长度）次，数组元素将顺次排序。数组元素交换像冒泡一样，所以叫冒泡排序。
平均时间复杂度：O(n^2)。
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { //相邻元素两两对比
var temp = arr[j+1]; //元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
选择排序
选择排序原理每次选择数组中未排序中最小的，放到数组前面，这样前面部分元素已顺序排列。对未排序部分遍历arr.length次，数组元素将顺次排序。
时间复杂度O(n^2)。
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { //寻找最小的数
minIndex = j; //将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
插入排序
插入排序过程：数组被分为两部分已排序部分，待排序部分，待排序部分第一个元素，与已排序部分每个元素比较，如果发现已排序元素大于未排序元素，则已排序元素向后移一位，否则未排序元素插入后一位。
时间复杂度：O(n^2)。
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
希尔排序
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //动态定义间隔序列
gap =gap*3+1;
}
for (gap; gap> 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j]> temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
归并算法
运用了分而治之的思想，将数组分为两半，分别排序在将两部分合并，而分开的两部分在进行同样的操作，也就是递归的思想，最终实现升序排列。
function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length>0 && right.length>0) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
快速排序
首先在这个序列中随便找一个数作为基准数。接下来，需要将这个序列中所有比基准数大的数放在基准数的右边，比基准数小的数放在基准数的左边。
var quickSort = function(arr) {
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
堆排序
大顶堆：根节点为最大值， 每个节点的值大于等于孩子节点。
小顶堆：根节点为最小值，每个节点的值小于等于孩子节点。
建立大顶堆，将根节点移到数组最后，调整未排序部分，循环往复最终得到升序数组。
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function shiftDown(arr, i, length) {
let temp = arr[i];
for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
temp = arr[i];
if (j + 1 < length && arr[j] < arr[j + 1]) {
j++;
}
if (temp < arr[j]) {
swap(arr, i, j);
i = j;
} else {
break;
}
}
}
function heapSort(arr) {
for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
shiftDown(arr, i, arr.length);
}
for (let i = Math.floor(arr.length - 1); i > 0; i--) {
swap(arr, 0, i);
shiftDown(arr, 0, i);
}
return arr;
}
二分查找法
二分查找法用于在有序数组里查找目标值，先检验中间项和目标值的大小，如果相同则返回下标，如果中间项小于目标值，则在中间项的右侧寻找目标值，如果中间项大于目标值，则在中间项的左侧寻找目标值，循环往复直到数组遍历完或找到目标。
function binarySearch(target, arr) {
var start = 0;
var end = arr.length - 1;
while (start <= end) {
var mid = parseInt(start + (end - start) / 2);
if (target == arr[mid]) {
return mid;
} else if (target > arr[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
