欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JS实现常见的查找、排序、去重算法示例

程序员文章站 2022-05-15 11:01:52
本文实例讲述了js实现常见的查找、排序、去重算法。分享给大家供大家参考,具体如下: 今天总结了下排序简单的算法 【自定义排序】 先寻找一个最小的数,然后依次那这个数和...

本文实例讲述了js实现常见的查找、排序、去重算法。分享给大家供大家参考,具体如下:

今天总结了下排序简单的算法

【自定义排序】

先寻找一个最小的数,然后依次那这个数和数组中其他数字比较,如果发现比这个数字小的数就把这两个数调换位置,然后再继续寻找下一个最小的数字进行下一轮比较

var arr = [31, 6, 19, 8, 2, 3];
function findmin(start, arr) {
  var imin = arr[start];
  var iminindex = start;
  for (var i = start + 1; i < arr.length; i++) {
    if (arr[i] < imin) {
      imin = arr[i];
      iminindex = i;
    }
  }
  return iminindex;
}
function sort1(arr) {
  for (var i = 0; i < arr.length; i++) {
    var iminindex = findmin(i, arr);
    var car;
    car = arr[i];
    arr[i] = arr[iminindex];
    arr[iminindex] = car;
  }
  return arr;
}
document.write(sort1(arr));

【线性查找】:一个一个去查找

//不重复 有序
var arr = [0];
for (var i = 1; i < 100000; i++) {
  arr[i] = arr[i - 1] + math.floor(math.random() * 4 + 1);
}
function find1(n, arr) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] == n) {
      return true;
    }
  }
  return false;
}
//测试性能
var t1 = new date().gettime();
for (var i = 0; i < 10000; i++) {
  var n = math.random() * 10000;
  find2(n, 0, arr.length - 1)
}
alert(new date().gettime() - t1);

【二分查找】:不停的分成两个部分,分部分查找

是一种万能方法,不一定是最好的,但是个保底的方法。(分治法)

***中间值 相加除以二,统一偏左,向下取整

//不重复 有序
var arr = [12, 17, 23, 34, 45, 76, 89];
function find2(n, s, e) {
  //边界处理
  if (s > e) {
    return false;
  } else if (s == e) {
    if (arr[s] == n) {
      return true;
    } else {
      return false;
    }
  }
  var c = math.floor((s + e) / 2);
  if (arr[c] == n) {
    return true;
  } else {
    if (n < arr[c]) {
      return find2(n, s, c);
    } else {
      return find2(n, c + 1, e);
    }
  }
}
alert(find2(34, 0, arr.length - 1)); //true false

【边界处理】-----递归,一层一层往下找

//要求数组不重复有顺序\
var arr = [12, 23, 34, 45, 56, 67, 78]
function find2(n, s, e) {
  if (s > e) {
    return fasle;
  } else if (s == e) {
    if (arr[s] == e) {
      return true;
    } else {
      return false;
    }
  }
  var c = math.floor((s + e) / 2);
  if (arr[c] == n) {
    return true;
  } else {
    if (n < arr[c]) {
      return find2(n, s, c);
    } else {
      return find2(n, c + 1, e);
    }
  }
}
alert(find2(12, arr.length + 1, 78));

应用

【查找最小值】

var arr = [12, 54, 32, 9, 5, 3, 1, 101, -100, -1000];
function findmin(s, e) {
  if (s > e) {
    return [];
  } else if (s == e) {
    return arr[s];
  } else if (s == e - 1) {
    if (arr[s] < arr[e]) {
      return arr[s];
    } else {
      return arr[e];
    }
  }
  var c = math.floor((s + e) / 2);
  var l = findmin(s, c);
  var r = findmin(c + 1, e);
  if (l < r) {
    return l;
  } else {
    return r;
  }
}
alert(findmin(0, arr.length - 1));

【数组去重】

var arr = [1, 2, 3, 4, 5, 4, 3, 4, 5, 2, 1, 4, 2, 1, 5, 7];
function findinarr(n, arr) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] == n) {
      return true;
    }
  }
  return false;
}
function removecopy(s, e) {
  if (s > e) {
    return [];
  } else if (s == e) {
    return [arr[s]];
  } else if (s == e - 1) {
    if (arr[s] == arr[e]) {
      return [arr[s]];
    } else {
      return [arr[s], arr[e]]
    }
  }
  var c = math.floor((s + e) / 2);
  var l = removecopy(s, c);
  var r = removecopy(c + 1, e);
  for (var i = 0; i < r.length; i++) {
    if (!findinarr(r[i], l)) {
      l.push(r[i]);
    }
  }
  return l;
}
document.write(removecopy(0, arr.length - 1));

【数组排序】

var arr = [34, 32, 1, 76, 55, -100, 99, 101];
function mysort(s, e) {
  //边界处理
  if (s > e) {
    return [];
  } else if (s == e) {
    return [arr[s]]
  } else if (s == e - 1) {
    if (arr[s] < arr[e]) {
      return [arr[s], arr[e]];
    } else {
      return [arr[e], arr[s]];
    }
  }
  //1.切中间值
  var c = math.floor((s + e) / 2);
  //2.分半处理
  var l = mysort(s, c);
  var r = mysort(c + 1, e);
  var res = [];
  while (l.length > 0 || r.length > 0) {
    if (l[0] < r[0]) {
      res.push(l.shift());
    } else {
      res.push(r.shift());
    }
  }
  if (l.length == 0) {
    res = res.concat(r);
  } else if (r.length == 0) {
    res = res.concat(l);
  }
  return res;
}
//调用
document.write(mysort(0, arr.length - 1));

冒泡排序 bubblesort

循环,每次拿出两个值,两两比较,如果下一个值比目前的小,那么交换位置

外层循环是循环取数,内层循环是两两交换比较

var arr = [ - 122, -2, 5, 6, 73, 34, 5, 2];
function bubblesort(arr) {
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp
      }
    }
  }
  return arr;
}
document.write(bubblesort(arr));

【快速排序】 -------quicksort

取数组中间的数,比中间数小的房中间数左边,比中间数大的放右边,再把两遍链接起来

function quicksort(arr, s, e) {
  //边界处理 参与流程
  if (arr.length == 0) {
    return [];
  }
  var c = math.floor((s + e) / 2);
  var arrc = arr.splice(c, 1);
  var l = [];
  var r = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < arrc) {
      l.push(arr[i]);
    } else {
      r.push(arr[i]);
    }
  }
  return quicksort(l).concat(arrc, quicksort(r));
}
var arr = [5, 5, 12, 56, 1, 67, -1, -23 - 1];
document.write(quicksort(arr, 0, arr.length - 1));

【散列】 hash 哈希 数组 ------js常用用的结构

添加

var arr = [];
arr.length = 0;
var cont = 0;
function hash_add(n) {
  var pos = n % arr.length;
  //当空间不足的时候
  if (arr[pos]) {
    while (arr[pos]) {
      cont++;
      if (arr[pos] == n) {
        return;
      } else {
        pos++;
        if (pos == arr.length) {
          pos = 0;
        }
      }
    }
    arr[pos] = n;
  } else {
    arr[pos] = n;
  }
  //空间不足的时候的扩建
  if (cont == arr.length) {
    //d等呗扩建
    var oldarr = arr;
    arr.length = oldarr.length * 2;
    arr = [];
    for (var i = 0; i < oldarr.length; i++) {
      arr.push(oldarr[i]);
      count = 0;
    }
  }
}
hash_add();

ps:这里再为大家推荐一款关于排序的演示工具供大家参考:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:

更多关于javascript相关内容感兴趣的读者可查看本站专题:《javascript数学运算用法总结》、《javascript数据结构与算法技巧总结》、《javascript数组操作技巧总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结

希望本文所述对大家javascript程序设计有所帮助。