别人家的面试题:统计“1”的个数

别人家的面试题:统计“1”的个数

2016/05/27 · JavaScript
· 5 评论 ·
Javascript,
算法

本文作者: 伯乐在线 –
十年踪迹
。未经作者许可,禁止转载!
欢迎加入伯乐在线 别人家的面试题:统计“1”的个数。专栏作者。

小胡子哥 @Barret李靖
给我推荐了一个写算法刷题的地方
leetcode.com,没有 ACM
那么难,但题目很有趣。而且据说这些题目都来源于一些公司的面试题。好吧,解解别人公司的面试题其实很好玩,既能整理思路锻炼能力,又不用担心漏题
╮(╯▽╰)╭。

长话短说,让我们来看一道题:

别人家的面试题:一个整数是否是“4”的N次幂

2016/05/30 · 基础技术 ·
2 评论 ·
算法

本文作者: 伯乐在线 –
十年踪迹
。未经作者许可,禁止转载!
欢迎加入伯乐在线 专栏作者。

这是 leetcode.com
的第二篇。与上一篇一样,我们讨论一道相对简单的问题,因为学习总讲究循序渐进。而且,就算是简单的问题,追求算法的极致的话,其中也是有大学问的。

//获取字符数组
String.prototype.ToCharArray=function()
{
         return this.split(“”);
}
//获取N个相同的字符串
String.prototype.Repeat=function(num)
{
    var tmpArr=[];
    for(var i=0;i<num;i++)    tmpArr.push(this);
    return tmpArr.join(“”);
}
//逆序
String.prototype.Reverse=function()
{
     return this.split(“”).reverse().join(“”);
}
//测试是否是数字
String.prototype.IsNumeric=function()
{
    var tmpFloat=parseFloat(this);
    if(isNaN(tmpFloat))    return false;
    var tmpLen=this.length-tmpFloat.toString().length;
    return tmpFloat+”0″.Repeat(tmpLen)==this;
}
//测试是否是整数
String.prototype.IsInt=function()
{
    if(this==”NaN”)    return false;
    return this==parseInt(this).toString();
}
// 合并多个空白为一个空白
String.prototype.resetBlank = function()
{
    return this.replace(/s+/g,” “);
}
// 除去左边空白
String.prototype.LTrim = function()
{
    return this.replace(/^s+/g,””); 

// 除去右边空白
String.prototype.RTrim = function()
{
    return this.replace(/s+$/g,””); 
}
// 除去两边空白
String.prototype.trim = function()
{
    return this.replace(/(^s+)|(s+$)/g,””); 
}
// 保留数字
String.prototype.getNum = function()
{
    return this.replace(/[^d]/g,””);
}
// 保留字母
String.prototype.getEn = function()
{
    return this.replace(/[^A-Za-z]/g,””); 
}
// 保留中文
String.prototype.getCn = function()
{
    return this.replace(/[^u4e00-u9fa5uf900-ufa2d]/g,””);
}
// 得到字节长度
String.prototype.getRealLength = function()
{
    return this.replace(/[^x00-xff]/g,”–“).length;
}
// 从左截取指定长度的字串
String.prototype.left = function(n)
{
    return this.slice(0,n);
}
// 从右截取指定长度的字串
String.prototype.right = function(n)
{
    return this.slice(this.length-n);
}
// HTML编码
String.prototype.HTMLEncode = function()
{
    var re = this;
    var q1 = [/x26/g,/x3C/g,/x3E/g,/x20/g];
    var q2 = [“&”,”<“,”>”,” “];
    for(var i=0;i<q1.length;i++)
    re = re.replace(q1[i],q2[i]);
    return re;
}
// Unicode转化
String.prototype.ascW = function()
{
    var strText = “”;
    for (var i=0; i<this.length; i++) strText += “” + this.charCodeAt(i) + “;”;
    return strText;

Given a non negative integer number
num. For every numbers i in the range 0 ≤ i ≤ num
calculate the number of 1’s in their binary representation and return
them as an array.

Example:
For num = 5 you should return
[0,1,1,2,1,2].

笔试面试经常涉及各种算法,本文简要介绍常用的一些算法,并用javascript实现。

统计“1”的个数

给定一个非负整数 num,对于任意 i,0 ≤ i ≤ num,计算 i
的值对应的二进制数中 “1” 的个数,将这些结果返回为一个数组。

例如:

当 num = 5 时,返回值为 [0,1,1,2,1,2]。

/** * @param {number} num * @return {number[]} */ var countBits =
function(num) { //在此处实现代码 };

1
2
3
4
5
6
7
/**
* @param {number} num
* @return {number[]}
*/
var countBits = function(num) {
    //在此处实现代码
};

“4”的整数次幂

给定一个32位有符号整数(32 bit signed
integer),写一个函数,检查这个整数是否是“4”的N次幂,这里的N是非负整数。

例如:

  • 给定 num = 16,返回 true,因为 16 = 42
  • 给定 num = 5,返回 flase

附加条件: 你能够不用循环和递归吗?

您可能感兴趣的文章:

  • 详解JS中Array对象扩展与String对象扩展
  • Javascript string
    扩展库代码
  • Javascript
    String对象扩展HTML编码和解码的方法
  • JavaScript
    字符串数字左补位,右补位,取固定长度,截位扩展函数代码
  • JavaScript中ES6字符串扩展方法
  • JavaScript常用字符串与数组扩展函数小结
  • js实现prototype扩展的方法(字符串,日期,数组扩展)
  • javascript框架设计读书笔记之字符串的扩展和修复
  • JS字符串函数扩展代码
  • JavaScript实现替换字符串中最后一个字符的方法
  • JavaScript利用正则表达式替换字符串中的内容
  • js
    replace(a,b)之替换字符串中所有指定字符的方法
  • JavaScript基于扩展String实现替换字符串中index处字符的方法

这应该是一道新放入的题。意思是给你一个非负整数num,对于0到num这(num+1)个整数,求出每个数用二进制表示时1的个数。

1、插入排序

解题思路

这道题咋一看还挺简单的,无非是:

  • 实现一个方法 countBit,对任意非负整数
    n,计算它的二进制数中“1”的个数
  • 循环 i 从 0 到 num,求 countBit(i),将值放在数组中返回。

JavaScript中,计算 countBit 可以取巧:

function countBit(n){ return n.toString(2).replace(/0/g,””).length; }

1
2
3
function countBit(n){
    return n.toString(2).replace(/0/g,"").length;
}

上面的代码里,我们直接对 n 用 toString(2)
转成二进制表示的字符串,然后去掉其中的0,剩下的就是“1”的个数。

然后,我们写一下完整的程序:

版本1

function countBit(n){ return n.toString(2).replace(/0/g,”).length; }
function countBits(nums){ var ret = []; for(var i = 0; i <= nums;
i++){ ret.push(countBit(i)); } return ret; }

1
2
3
4
5
6
7
8
9
10
11
function countBit(n){
   return n.toString(2).replace(/0/g,”).length;
}
 
function countBits(nums){
   var ret = [];
   for(var i = 0; i <= nums; i++){
       ret.push(countBit(i));
   }
   return ret;
}

上面这种写法十分讨巧,好处是 countBit 利用 JavaScript
语言特性实现得十分简洁,坏处是如果将来要将它改写成其他语言的版本,就有可能懵B了,它不是很通用,而且它的性能还取决于
Number.prototype.toString(2) 和 String.prototype.replace 的实现。

所以为了追求更好的写法,我们有必要考虑一下 countBit 的通用实现法。

我们说,求一个整数的二进制表示中 “1” 的个数,最普通的当然是一个 O(logN)
的方法:

function countBit(n){ var ret = 0; while(n > 0){ ret += n & 1; n
>>= 1; } return ret; }

1
2
3
4
5
6
7
8
function countBit(n){
    var ret = 0;
    while(n > 0){
        ret += n & 1;
        n >>= 1;
    }
    return ret;
}

所以我们有了版本2

这么实现也很简洁不是吗?但是这么实现是否最优?建议此处思考10秒钟再往下看。


解题思路

如果忽略“附加条件”,这题还挺简单的对吧?简直是信手拈来:

版本1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num /= 4; } return num
=== 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
        num /= 4;
    }
    return num === 1;
}

版本1 好像很简单、很强大的样子,它的时间复杂度是
log4N。有同学说,还可以做一些微小的改动:

版本1.1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num >>>= 2; }
return num === 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
      num >>>= 2;
    }
    return num === 1;
}

上面的代码用位移替代除法,在其他语言中更快,鉴于 JS
通常情况下非常坑的位运算操作,不一定速度能变快。

好了,最关键的是,不管是 版本1 还是 版本1.1
似乎都不满足我们前面提到的“附加条件”,即不使用循环和递归,或者说,我们需要寻找
O(1) 的解法。

按照惯例,大家先思考10秒钟,然后往下看 ——


最简单的思路:对每个数,利用移位和按位与(i &
1)运算,计算1的个数。这样时间复杂度为O(n*sizeof(integer)),如果int用32位表示,那么时间复杂度就是O(32n)。

1)算法简介

更快的 countBit

上一个版本的 countBit 的时间复杂度已经是 O(logN)
了,难道还可以更快吗?当然是可以的,我们不需要去判断每一位是不是“1”,也能知道
n 的二进制中有几个“1”。

有一个诀窍,是基于以下一个定律:

  • 对于任意 n, n ≥ 1,有如下等式成立:

countBit(n & (n – 1)) === countBit(n) – 1

1
countBit(n & (n – 1)) === countBit(n) – 1

这个很容易理解,大家只要想一下,对于任意 n,n – 1 的二进制数表示正好是 n
的二进制数的最末一个“1”退位,因此 n & n – 1 正好将 n
的最末一位“1”消去,例如:

  • 6 的二进制数是 110, 5 = 6 – 1 的二进制数是 101,6 & 5
    的二进制数是 110 & 101 == 100
  • 88 的二进制数是 1011000,87 = 88 – 1 的二进制数是
    1010111,88 & 87 的二进制数是 1011000 & 1010111 == 1010000

于是,我们有了一个更快的算法:

版本3

function countBit(n){ var ret = 0; while(n > 0){ ret++; n &= n – 1; }
return ret; } function countBits(nums){ var ret = []; for(var i = 0; i
<= nums; i++){ ret.push(countBit(i)); } return ret; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function countBit(n){
    var ret = 0;
    while(n > 0){
        ret++;
        n &= n – 1;
    }
    return ret;
}
 
function countBits(nums){
   var ret = [];
   for(var i = 0; i <= nums; i++){
       ret.push(countBit(i));
   }
   return ret;
}

上面的 countBit(88) 只循环 3 次,而“版本2”的 countBit(88) 却需要循环
7 次。

优化到了这个程度,是不是一切都结束了呢?从算法上来说似乎已经是极致了?真的吗?再给大家
30 秒时间思考一下,然后再往下看。


不用循环和递归

其实这道题真心有好多种思路,计算指数之类的对数学系学霸们完全不是问题嘛:

版本2

JavaScript

const log4 = Math.log(4); function isPowerOfFour(num){ var n =
Math.log(num) / log4; return n === (0|n); }

1
2
3
4
5
const log4 = Math.log(4);
function isPowerOfFour(num){
    var n = Math.log(num) / log4;
    return n === (0|n);
}

嗯,通过对数公式 logm(n) = log(n) / log(m)
求出指数,然后判断指数是不是一个整数,这样就可以不用循环和递归解决问题。而且,还要注意细节,可以将
log4 当做常量抽取出来,这样不用每次都重复计算,果然是学霸范儿。

不过呢,利用 Math.log
方法也算是某种意义上的犯规吧,有没有不用数学函数,用原生方法来解决呢?

当然有了!而且还不止一种,大家可以继续想30秒,要至少想出一种哦 ——


考虑优化成O(n):

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

countBits 的时间复杂度

考虑 countBits, 上面的算法:

  • “版本1” 的时间复杂度是 O(N*M),M 取决于 Number.prototype.toString
    和 String.prototype.replace 的复杂度。
  • “版本2” 的时间复杂度是 O(N*logN)
  • “版本3” 的时间复杂度是 O(N*M),M 是 N 的二进制数中的“1”的个数,介于
    1 ~ logN 之间。

上面三个版本的 countBits 的时间复杂度都大于 O(N)。那么有没有时间复杂度
O(N) 的算法呢?

实际上,“版本3”已经为我们提示了答案,答案就在上面的那个定律里,我把那个等式再写一遍:

countBit(n & (n – 1)) === countBit(n) – 1

1
countBit(n & (n – 1)) === countBit(n) – 1

也就是说,如果我们知道了 countBit(n & (n - 1)),那么我们也就知道了
countBit(n)

而我们知道 countBit(0) 的值是 0,于是,我们可以很简单的递推:

版本4

function countBits(nums){ var ret = [0]; for(var i = 1; i <= nums;
i++){ ret.push(ret[i & i – 1] + 1); } return ret; }

1
2
3
4
5
6
7
function countBits(nums){
   var ret = [0];
   for(var i = 1; i <= nums; i++){
       ret.push(ret[i & i – 1] + 1);
   }
   return ret;
}

原来就这么简单,你想到了吗 ╮(╯▽╰)╭

以上就是所有的内容,简单的题目思考起来很有意思吧?程序员就应该追求完美的算法,不是吗?

这是 leetcode
算法面试题系列的第一期,下一期我们讨论另外一道题,这道题也很有趣:判断一个非负整数是否是
4 的整数次方
,别告诉我你用循环,想想更巧妙的办法吧~

打赏支持我写出更多好文章,谢谢!

打赏作者

不用内置函数

这个问题的关键思路和上一道题类似,先考虑“4”的幂的二进制表示:

  • 40 = 1B
  • 41 = 100B
  • 42 = 10000B
  • 43 = 1000000B
  • ……

也就是每个数比上一个数的二进制后面多两个零嘛。最重要的是,“4”的幂的二进制数只有
1 个“1”。如果仔细阅读过上一篇,你就会知道,判断一个二进制数只有 1
个“1”,只需要:

JavaScript

(num & num – 1) === 0

1
(num & num – 1) === 0

但是,二进制数只有 1
个“1”只是“4”的幂的必要非充分条件,因为“2”的奇数次幂也只有 1
个“1”。所以,我们还需要附加的判断:

JavaScript

(num & num – 1) === 0 && (num & 0xAAAAAAAA) === 0

1
(num & num – 1) === 0 && (num & 0xAAAAAAAA) === 0

为什么是 num & 0xAAAAAAAA === 0? 因为这个确保 num 的二进制的那个 “1”
出现在“奇数位”上,也就确保了这个数确实是“4”的幂,而不仅仅只是“2”的幂。

最后,我们得到完整的版本:

版本3

JavaScript

function isPowerOfFour(num) { return num > 0 && (num & (num-1)) === 0
&& (num & 0xAAAAAAAA) === 0; };

1
2
3
4
function isPowerOfFour(num) {
    return num > 0 && (num & (num-1)) === 0
                   && (num & 0xAAAAAAAA) === 0;
};

上面的代码需要加上 num > 0,是因为 0 要排除在外,否则 (0 & -1) === 0
也是 true


对于11这个数,我们暂时用一个字节来表示

2)算法描述和实现

打赏支持我写出更多好文章,谢谢!

任选一种支付方式

图片 1
图片 2

3 赞 8 收藏 5
评论

其他版本

上面的版本已经符合了我们的需求,时间复杂度是 O(1),不用循环和递归。

此外,我们还可以有其他的版本,它们严格来说有的还是“犯规”,但是我们还是可以学习一下这些思路:

版本4:用 Math.sqrt

JavaScript

function isPowerOfFour(num) { num = Math.sqrt(num); return num > 0 &&
num === (0|num) && (num & (num-1)) === 0; };

1
2
3
4
function isPowerOfFour(num) {
    num = Math.sqrt(num);
    return num > 0 && num === (0|num) && (num & (num-1)) === 0;
};

版本5:用正则表达式

JavaScript

function isPowerOfFour(num) { return /^1(00)*$/g.test(num.toString(2));
};

1
2
3
function isPowerOfFour(num) {
    return /^1(00)*$/g.test(num.toString(2));
};

以上就是所有的内容,这道题有非常多种思路,相当有趣,也比较考验基本功。如果你有自己的思路,可以留言参与讨论。

下一期我们讨论另外一道题,这道题比这两道题要难一些,但也更有趣:给定一个正整数
n,将它拆成至少两个正整数之和,对拆出的正整数求乘积,返回能够得到的乘积最大的结果

想一想你的解法是什么?你能够尽可能减少算法的时间复杂度吗?期待你的答案~~

打赏支持我写出更多好文章,谢谢!

打赏作者

11:           0000 1011

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

关于作者:十年踪迹

图片 3

月影,奇舞团团长,热爱前端开发,JavaScript
程序猿一枚,能写代码也能打杂卖萌说段子。
个人主页 ·
我的文章 ·
14 ·
    

图片 4

打赏支持我写出更多好文章,谢谢!

任选一种支付方式

图片 5
图片 6

1 赞 7 收藏 2
评论

11/2 = 5:0000 0101

从第一个元素开始,该元素可以认为已经被排序;

关于作者:十年踪迹

图片 7

月影,奇舞团团长,热爱前端开发,JavaScript
程序猿一枚,能写代码也能打杂卖萌说段子。
个人主页 ·
我的文章 ·
14 ·
    

图片 4

容易发现,除了11最右边那个位和5的最高位,其他位对应一样。也就是说i用二进制表示时1出现的次数等于i/2中1出现的次数加1(如果i用二进制表示时最右边一位为1,否则不加1)。这样我们在计算i时可以利用前面已计算出的i/2:ret[i]
= ret[i/2] + (i % 2 == 0 ? 0 : 1);

取出下一个元素,在已经排序的元素序列中从后向前扫描;

AC代码(C++):

如果该元素(已排序)大于新元素,将该元素移到下一位置;

class Solution {
public:
    vector<int> countBits(int num) {
        if (num <= 0)
            return vector<int>(1, 0);

        vector<int> ret(num+1, 0);
        int i = 0;
        int half = 0;

        for (i = 1; i <= num; ++i)
        {
            //the number of 1's in half equals the number of 1's in i except the right-most bit in i 
            half = i >> 1;
            if (i % 2 == 0)//the right-most bit in i is 0
                ret[i] = ret[half];
            else//the right-most bit in i is 1
                ret[i] = ret[half] + 1;
        }

        return ret;
    }
};

重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;

将新元素插入到该位置后;

重复步骤2~5。

JavaScript代码实现:

function insertionSort(array) {

if
(Object.prototype.toString.call(array).slice(8,
-1) === ‘Array’) {

for (var i = 1; i < array.length; i++) {

var key = array[i];

var j = i – 1;

while (j >= 0 && array[j] > key) {

array[j + 1] = array[j];

j–;

}

array[j + 1] = key;

}

return array;

} else {

return ‘array is not an Array!’;

}

}

3)算法分析

最佳情况:输入数组按升序排列。T(n) = O(n)

最坏情况:输入数组按降序排列。T(n) = O(n2)

平均情况:T(n) = O(n2)

二、二分插入排序

1)算法简介

二分插入(Binary-insert-sort)排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接插入排序算法最大的区别在于查找插入位置时使用的是二分查找的方式,在速度上有一定提升。

2)算法描述和实现

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

从第一个元素开始,该元素可以认为已经被排序;

取出下一个元素,在已经排序的元素序列中二分查找到第一个比它大的数的位置;

将新元素插入到该位置后;

重复上述两步。

JavaScript代码实现:

function binaryInsertionSort(array) {

if (Object.prototype.toString.call(array).slice(8, -1) === ‘Array’) {

for (var i = 1; i < array.length; i++) {

var key = array[i], left = 0, right = i – 1;

while (left <= right) {

var middle = parseInt((left + right) / 2);

if (key < array[middle]) {

right = middle – 1;

} else {

left = middle + 1;

}

}

for (var j = i – 1; j >= left; j–) {

array[j + 1] = array[j];

}

array[left] = key;

}

return array;

} else {

return ‘array is not an Array!’;

}

}

3)算法分析

最佳情况:T(n) = O(nlogn)

最差情况:T(n) = O(n2)

平均情况:T(n) = O(n2)

三、选择排序

1)算法简介

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

2)算法描述和实现

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

初始状态:无序区为R[1..n],有序区为空;

第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录
R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;

n-1趟结束,数组有序化了。

JavaScript代码实现:

function selectionSort(array) {

if (Object.prototype.toString.call(array).slice(8, -1) === ‘Array’) {

var len = array.length, temp;

for (var i = 0; i < len – 1; i++) {

var min = array[i];

for (var j = i + 1; j < len; j++) {

if (array[j] < min) {

temp = min;

min = array[j];

array[j] = temp;

}

}

array[i] = min;

}

return array;

} else {

return ‘array is not an Array!’;

}

}

3)算法分析

最佳情况:T(n) = O(n2)

最差情况:T(n) = O(n2)

平均情况:T(n) = O(n2)

四、冒泡排序

1)算法简介

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2)算法描述和实现

具体算法描述如下:

比较相邻的元素。如果第一个比第二个大,就交换它们两个;

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;

针对所有的元素重复以上的步骤,除了最后一个;

重复步骤1~3,直到排序完成。

JavaScript代码实现:

function bubbleSort(array) {

if (Object.prototype.toString.call(array).slice(8, -1) === ‘Array’) {

var len = array.length, temp;

for (var i = 0; i < len – 1; i++) {

for (var j = len – 1; j >= i; j–) {

if (array[j] < array[j – 1]) {

temp = array[j];

array[j] = array[j – 1];

array[j – 1] = temp;

}

}

}

return array;

} else {

return ‘array is not an Array!’;

}

}

3)算法分析

最佳情况:T(n) = O(n)

最差情况:T(n) = O(n2)

平均情况:T(n) = O(n2)

五、快速排序

1)算法简介

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

2)算法描述和实现

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

从数列中挑出一个元素,称为 ”基准”(pivot);

重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

JavaScript代码实现:

//方法一

function quickSort(array, left, right) {

if (Object.prototype.toString.call(array).slice(8, -1) === ‘Array’ &&
typeof left === ‘number’ && typeof right === ‘number’) {

if (left < right) {

var x = array[right], i = left – 1, temp;

for (var j = left; j <= right; j++) {

if (array[j] <= x) {

i++;

temp = array[i];

array[i] = array[j];

array[j] = temp;

}

}

quickSort(array, left, i – 1);

quickSort(array, i + 1, right);

};

} else {

return ‘array is not an Array or left or right is not a number!’;

}

}

var aaa = [3, 5, 2, 9, 1];

quickSort(aaa, 0, aaa.length – 1);

console.log(aaa);

//方法二

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));

};

3)算法分析

最佳情况:T(n) = O(nlogn)

最差情况:T(n) = O(n2)

平均情况:T(n) = O(nlogn)

六、堆排序

1)算法简介

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

2)算法描述和实现

具体算法描述如下:

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;

将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];

由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

JavaScript代码实现:

/*方法说明:堆排序

@param array 待排序数组*/

function heapSort(array) {

if (Object.prototype.toString.call(array).slice(8, -1) === ‘Array’) {

//建堆

var heapSize = array.length, temp;

for (var i = Math.floor(heapSize / 2); i >= 0; i–) {

heapify(array, i, heapSize);

}

//堆排序

for (var j = heapSize – 1; j >= 1; j–) {

temp = array[0];

array[0] = array[j];

array[j] = temp;

heapify(array, 0, –heapSize);

}

} else {

return ‘array is not an Array!’;

}

}

/*方法说明:维护堆的性质

@param arr 数组

@param x 数组下标

@param len 堆大小*/

function heapify(arr, x, len) {

if (Object.prototype.toString.call(arr).slice(8, -1) === ‘Array’ &&
typeof x === ‘number’) {

var l = 2 * x, r = 2 * x + 1, largest = x, temp;

if (l < len && arr[l] > arr[largest]) {

largest = l;

}

if (r < len && arr[r] > arr[largest]) {

largest = r;

}

if (largest != x) {

temp = arr[x];

arr[x] = arr[largest];

arr[largest] = temp;

heapify(arr, largest, len);

}

} else {

return ‘arr is not an Array or x is not a number!’;

}

}

3)算法分析

最佳情况:T(n) = O(nlogn)

最差情况:T(n) = O(nlogn)

平均情况:T(n) = O(nlogn)

七、归并排序

1)算法简介

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide
and
Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

2)算法描述和实现

具体算法描述如下:

把长度为n的输入序列分成两个长度为n/2的子序列;

对这两个子序列分别采用归并排序;

将两个排序好的子序列合并成一个最终的排序序列。

JavaScript代码实现:

function mergeSort(array, p, r) {

if (p < r) {

var q = Math.floor((p + r) / 2);

mergeSort(array, p, q);

mergeSort(array, q + 1, r);

merge(array, p, q, r);

}

}

function merge(array, p, q, r) {

var n1 = q – p + 1, n2 = r – q, left = [], right = [], m = n = 0;

for (var i = 0; i < n1; i++) {

left[i] = array[p + i];

}

for (var j = 0; j < n2; j++) {

right[j] = array[q + 1 + j];

}

left[n1] = right[n2] = Number.MAX_VALUE;

for (var k = p; k <= r; k++) {

if (left[m] <= right[n]) {

array[k] = left[m];

m++;

} else {

array[k] = right[n];

n++;

}

}

}

3)算法分析

最佳情况:T(n) = O(n)

最差情况:T(n) = O(nlogn)

平均情况:T(n) = O(nlogn)

八、桶排序

1)算法简介

桶排序 (Bucket
sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。

2)算法描述和实现

具体算法描述如下:

设置一个定量的数组当作空桶;

遍历输入数据,并且把数据一个一个放到对应的桶里去;

对每个不是空的桶进行排序;

从不是空的桶里把排好序的数据拼接起来。

JavaScript代码实现:

/*方法说明:桶排序

@param array 数组

@param num 桶的数量*/

function bucketSort(array, num) {

if (array.length <= 1) {

return array;

}

var len = array.length, buckets = [], result = [], min = max =
array[0], regex = ‘/^[1-9]+[0-9]*$/’, space, n = 0;

num = num || ((num > 1 && regex.test(num)) ? num : 10);

for (var i = 1; i < len; i++) {

min = min <= array[i] ? min : array[i];

max = max >= array[i] ? max : array[i];

}

space = (max – min + 1) / num;

for (var j = 0; j < len; j++) {

var index = Math.floor((array[j] – min) / space);

if (buckets[index]) { // 非空桶,插入排序

var k = buckets[index].length – 1;

while (k >= 0 && buckets[index][k] > array[j]) {

buckets[index][k + 1] = buckets[index][k];

k–;

}

buckets[index][k + 1] = array[j];

} else { //空桶,初始化

buckets[index] = [];

buckets[index].push(array[j]);

}

}

while (n < num) {

result = result.concat(buckets[n]);

n++;

}

return result;

}

3)算法分析

桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。

九、计数排序

1)算法简介

计数排序(Counting
sort)是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

2)算法描述和实现

具体算法描述如下:

找出待排序的数组中最大和最小的元素;

统计数组中每个值为i的元素出现的次数,存入数组C的第i项;

对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);

反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

JavaScript代码实现:

function countingSort(array) {

var len = array.length, B = [], C = [], min = max = array[0];

for (var i = 0; i < len; i++) {

min = min <= array[i] ? min : array[i];

max = max >= array[i] ? max : array[i];

C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;

}

for (var j = min; j < max; j++) {

C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);

}

for (var k = len – 1; k >=0; k–) {

B[C[array[k]] – 1] = array[k];

C[array[k]]–;

}

return B;

}

3)算法分析

当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n +
k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。

原文链接:http://www.kubiji.cn/juhe-id9742.html

网站地图xml地图