# 经典算法

# 冒泡排序

冒泡排序是数列排序的算法之一。依次比较大小进行位置上的交换。平均时间复杂度O(n2),空间复杂度O(1)

var bubbleSort = function(arr) {
    for(let i=0;i<arr.length;i++){
        for(let j=0;j<arr.length;j++){
            if(arr[j]>arr[j+1]){
                let temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
            }
        }
    }
    return arr;
};

1
2
3
4
5
6
7
8
9
10
11
12

# 选择性排序

选择性排序是数列排序的算法之一。平均时间复杂度O(n2),空间复杂度O(1),数据规模越小越好

var selectionSort = function(arr) {
    for(let i=0;i<arr.length;i++){
        let  minIndex=i; //寻找最小值i
        for(let j=i+1;j<arr.length;j++){
            if(arr[j]<arr[minIndex]){
                minIndex=j
            }
        }
        let temp=arr[i];
        arr[i]=arr[minIndex];
        arr[minIndex]=temp;
    }
    return arr;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 插入排序

选择性排序是数列排序的算法之一。平均时间复杂度O(n2),空间复杂度O(1),数据规模越小越好

var insertSort = function(arr) {
    let preIndex,current;
    for(let i=1;i<arr.length;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;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 线性搜索

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

var sequentialSearch = function(arr, item) {
    for (var i = 0; i < arr.length; i++) {
	    if (item === arr[i]) {
		    return i;
	    }
    }
    return -1;
}

1
2
3
4
5
6
7
8

# 二分搜索

算法要求：数据结构已排序,时间复杂度O(logn)

算法步骤：1.选取中间值。2.如果待搜索值比选中值要小，则返回步骤1并在选中值的左边的子数组中查找。3.如果待搜索值比选中值要大，则返回步骤1并在选中值的右边的子数组中查找。

//非递归
var binary_search=function(arr, key) {
    var low = 0,
        high = arr.length - 1;
    while (low <= high) {
        let mid = parseInt((high + low) / 2);
        if (key == arr[mid]) {
            return mid;
        } else if (key > arr[mid]) {
            low = mid + 1;
        } else if (key < arr[mid]) {
            high = mid - 1;
        } else {
            return -1;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//递归
var binary_search2=function(arr,low,high,key) {
    if(low>high) return -1;
    let mid=parseInt((low+high)/2)
    if(arr[mid]==key){
        return mid;
    }else if(arr[mid]<key){
        low=mid+1;
        return binary_search2(arr,low,high,key)
    }else if(arr[mid]>key){
        high=mid-1;
        return binary_search2(arr,low,high,key)
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

← 中等