这里有新鲜出炉的 Javascript 教程,程序狗速度看过来!
Javascript 是一种由 Netscape 的 LiveScript 发展而来的原型化继承的基于对象的动态类型的区分大小写的客户端脚本语言,主要目的是为了解决服务器端语言,比如 Perl,遗留的速度问题,为客户提供更流畅的浏览效果。
下面小编就为大家带来一篇 js 基本算法: 冒泡排序, 二分查找的简单实例。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
知识扩充:
时间复杂度:算法的时间复杂度是一个函数,描述了算法的运行时间。时间复杂度越低,效率越高。
自我理解:一个算法,运行了几次时间复杂度就为多少,如运行了 n 次,则时间复杂度为 O(n)。
1. 冒泡排序
解析:1. 比较相邻的两个元素,如果前一个比后一个大,则交换位置。
2. 第一轮的时候最后一个元素应该是最大的一个。
3. 按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较。
- function sort(elements){
- for(var i=0;i<elements.length-1;i++){
- for(var j=0;j<elements.length-i-1;j++){
- if(elements[j]>elements[j+1]){
- var swap=elements[j];
- elements[j]=elements[j+1];
- elements[j+1]=swap;
- }
- }
- }
- }
- var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
- console.log('before: ' + elements);
- sort(elements);
- console.log(' after: ' + elements);
2. 快速排序
解析:快速排序是对冒泡排序的一种改进,第一趟排序时将数据分成两部分,一部分比另一部分的所有数据都要小。然后递归调用,在两边都实行快速排序。
- function quickSort(elements) {
- if (elements.length <= 1) {
- return elements;
- }
- var pivotIndex = Math.floor(elements.length / 2);
- var pivot = elements.splice(pivotIndex, 1)[0];
- var left = [];
- var right = [];
- for (var i = 0; i < elements.length; i++) {
- if (elements[i] < pivot) {
- left.push(elements[i]);
- } else {
- right.push(elements[i]);
- }
- }
- return quickSort(left).concat([pivot], quickSort(right));
- };
- var elements = [5, 6, 2, 1, 3, 8, 7, 1.2, 5.5, 4.5];
- alert(quickSort(elements));
3. 插入排序
解析:
(1) 从第一个元素开始,该元素可以认为已经被排序
(2) 取出下一个元素,在已经排序的元素序列中从后向前扫描
(3) 如果该元素(已排序)大于新元素,将该元素移到下一位置
(4) 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置
(5)将新元素插入到下一位置中
(6) 重复步骤 2
- insertSort: function(elements) {
- var i = 1,
- j, step, key, len = elements.length;
- for (; i < len; i++) {
- step = j = i;
- key = elements[j];
- while (--j > -1) {
- if (elements[j] > key) {
- elements[j + 1] = elements[j];
- } else {
- break;
- }
- }
- elements[j + 1] = key;
- }
- return elements;
- }
2. 二分查找
解析:二分查找,也为折半查找。首先要找到一个中间值,通过与中间值比较,大的放又,小的放在左边。再在两边中寻找中间值,持续以上操作,直到找到所在位置为止。
(1)递归方法
- function binarySearch(data,item,start,end){
- var end=end || data.length-1;
- var start=start || 0;
- var m=Math.floor((start+end)/2);
- if(item==data[m]){
- return m;
- }else if(item<data[m]){
- return binarySearch(data,item,start,m-1) //递归调用
- }else{
- return binarySearch(data,item,m+1,end);
- }
- return false;
- }
- var arr=[34,12,5,123,2,745,32,4];
- binary(arr,5);
(2)非递归方法
- function binarySearch(data, item){
- var h = data.length - 1,
- l = 0;
- while(l <= h){
- var m = Math.floor((h + l) / 2);
- if(data[m] == item){
- return m;
- }
- if(item > data[m]){
- l = m + 1;
- }else{
- h = m - 1;
- }
- }
- return false;
- }
- var arr=[34,12,5,123,2,745,32,4];
- binarySearch(arr,5);
以上就是小编为大家带来的 js 基本算法: 冒泡排序, 二分查找的简单实例全部内容了,希望大家多多支持 phperz~
来源: http://www.phperz.com/article/17/0522/331370.html