今日算法小练习,排序与查找

    从小做起,以后每天定时写几个js算法,并且做总结打卡。今天写了几个简单的排序和查找,还买了一本书,《算法导论》,接下来的2个月的目标就是它啦,加油。


    快速排序

    快速排序的思想是分治,比如这里[3,4,1,5,6,9]这样一个数组,先选一个轴,比如说是起点,然后先从右向左找到比这个轴小的数,并把这个小数覆盖掉轴的位置。这时候原来小数的位置可以当成是空,然后再以轴为中心从左往右找,找到比轴大的数,再把这个数覆盖原来轴所在的位置。算法复杂度最差是$$n^2$$,最好是nlogn。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    function quickSort (arr,l,r) {
    var left = l,right = r;
    var key = arr[l];
    if(left < right){
    while(left < right){
    while(left<right && key < arr[right]){
    right--;
    }
    arr[left] = arr[right];
    while(left<right && key > arr[left]){
    left++;
    }
    arr[right] = arr[left];
    }
    arr[right] = arr[left];
    quickSort(arr,l,left-1);
    quickSort(arr,r+1,right);
    }
    }
    var arr = [3,4,1,5,6,9];
    quickSort(arr,0,5);
    console.log(arr);

    两种数组去重方法

    第一种利用indexOf,直接每次在新数组里查找是否有值,如果有则不push进入。否则push进入。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    function unique (arr) {
    var newArr = [];
    for(var i = 0;i<arr.length;i++){
    if(newArr.indexOf(arr[i]) == -1){
    newArr.push(arr[i]);
    }
    }
    return newArr;
    }
    var arr = [3,2,5,6,7,6,7,2];
    console.log(unique(arr));

    第二种利用hash,来生成一个键值对,用来存储已经有了的数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    function unique (arr){
    var newArr = [];
    var hash = {};
    for(var i = 0;i<arr.length;i++){
    if(!hash[arr[i]]){
    newArr.push(arr[i]);
    hash[arr[i]] = true;
    }
    }
    return newArr;
    }
    var arr = [3,2,5,6,7,6,7,2];
    console.log(unique(arr));

    二分查找

    二分查找没什么说的,就是3个指针,分别每次从一半来查找,前提是数组已经排号序。logn是其算法时间复杂度。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    function bSearch (arr,n,left,right){
    var mid;
    while(left<=right){
    mid = parseInt((left+right)/2);
    if(n == arr[mid]){
    return mid;
    }else if(arr[mid]<n){
    left = mid + 1;
    }else if(arr[mid]>n){
    right = mid - 1;
    }
    }
    return 0;
    }
    var arr = [0,3,5,7,11,14];
    var x = bSearch(arr,5,0,5);
    console.log(x);