2016-10-16 浩阳
content {:toc} 简单来说 Fisher–Yates shuffle 算法是一个用来将一个有限集合生成一个随机排列的算法(数组随机排序)。这个算法生成的随机排列是等概率的。同时这个算法非常高效。 本文主要介绍这个算法的来源、演变、原理。并举出一个例子为大家清晰的描述每次迭代过程。最后使用 JavaScript 代码将算法实现。 继续阅读 »
2014-01-12 W.Y.
在学习排序算法的时候,经常要用到随机数组,于是就写了一个生成随机数组的方法。算法来自网络,只是修改成了 JavaScript 版本。 基本原理是洗牌算法,首先从所有元素中随机选取一个与第一个元素进行交换,然后在第二个之后选择一个元素与第二个交换,直到最后一个元素。这样能确保每个元素在每个位置的概率都是1/n。 具体代码如下: javascript /** * * 生成从 1 到 length 之间的随机数组 * * @length 随机数组的长度,如果未传递该参数,那么 length 为默认值 9 * */ function randomArray(length) { var i, inde 继续阅读 »
2014-01-15 W.Y.
算法原理 为什么叫鸡尾酒排序?其实我也不知道,知道的小伙伴请告诉我。 其实它还有很多奇怪的名称,比如双向冒泡排序 (Bidirectional Bubble Sort)、波浪排序 (Ripple Sort)、摇曳排序 (Shuffle Sort)、飞梭排序 (Shuttle Sort) 和欢乐时光排序 (Happy Hour Sort)。本文中就以鸡尾酒排序来称呼它。 鸡尾酒排序是冒泡排序的轻微变形。不同的地方在于,鸡尾酒排序是从低到高然后从高到低来回排序,而冒泡排序则仅从低到高去比较序列里的每个元素。他可比冒泡排序的效率稍微好一点,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。 以序列(2,3,4 继续阅读 »
2014-01-15 W.Y.
算法原理 猴子排序 (Bogo Sort) 是个既不实用又原始的排序算法,其原理等同将一堆卡片抛起,落在桌上后检查卡片是否已整齐排列好,若非就再抛一次。其名字源自 Quantum bogodynamics,又称 bozo sort、blort sort 或猴子排序(参见无限猴子定理)。并且在最坏的情况下所需时间是无限的。 伪代码: javascript while not InOrder(list) do Shuffle(list) done more 这个排序方法没有办法给出实例分析,下面直接看代码。 JavaScript 语言实现 ``` javascript function bogoSort(array) 继续阅读 »