准备
在实现排序算法之前,先介绍将用到的几个函数。比如说为了将数组中数字的顺序打乱,我们可能需要一个洗牌函数,为了记录代码运行的时间,我们需要一个记录时间的函数。下面来介绍这些函数的实现。
-
洗牌方法
function shuffle() { return Math.random() - 0.5; }
因为 Math.random()
方法产生的数值在 [0,1) 之间,所以这个方法可以确保返回的数值是随机的。有了这个函数之后,只需要将其传入数组的 sort()
方法作为参数即可打乱数组。这个方法借鉴自 《12 个 JavaScript 技巧》 一文。
- 记录时间
记录时间其实很简单,我们只需要在代码执行前获取到时间,然后执行完毕之后再获取一次时间,取二者之间的差值即可,就像下面这样。
var Clock = {
"time": function() {
this.start = new Date().getTime();
},
"timeEnd": function() {
this.end = new Date().getTime();
return Math.floor(this.end - this.start);
}
}
如果你在 Java
中利用上面这个方面来计时,那是合情合理的,不过我们这是在写 JavaScript
代码,我们的宿主环境非常体贴,为我们提供了 console.time()
和 console.timeEnd()
方法来帮助我们计算 js
代码执行的时间。
不过值得一提的是,如果你利用 Clock
对象来计时会让你感到失望,因为它计时不是太准确,我使用上面提到的方法对选择排序进行了千数量级的计时, Clock
对象给我的结果使 8ms
左右,而 console.time()
和 console.timeEnd()
给出的结果却是 4ms
, 咋一看,好像时间长了两倍,当我在进行万数量级测验时,发现二者计时还是相差 4ms
左右,所以我的理解是,我们使用自定义计时方法是创建了一个对象,而这 4ms
使我们创建这个对象花费的时间。
好了,说的已经够多了,下面开始进入正题。
选择排序
选择排序的思想非常简单,首先,找到数组中最小的那个元素,然后将它和数组的第一个元素交换位置。其次,在剩下的元素中找到最小的元素,将它和数组的第二个元素位置交换。如此往复,直到整个数组排序。
从算法的思想中我们可以得出结论,在最好的情况下,也就是说数组元素全部有序的情况下,选择排序需要经历 N^2 / 2
次比较,0 次位置变换。在最差的情况下,也就是说所有数组元素一开始都不在最终位置上,需要经历 N^2 / 2
次比较和 N-1
次移位。
function selectionSort(array) {
var length = array.length,
min,
temp;
for(var i = 0; i < length; i++) {
min = i;
for(var j = i; j < length;j++) {
if (array[min] > array[j]) {
min = j;
}
}
if (min !== i) {
temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
可见,这种算法实现起来十分简单,不过遗憾的是这种排序算法用于处理小数组的排序尚能称职,对于比较多的数据却是无力回天,这也正是我们探索其他方法的动力所在,下面来讲一个同样简单但是性能优于选择排序的算法 —— 插入排序。
插入排序
插入排序的思想就是从第二个元素开始,与前面的元素进行比较,直到找到比当前元素还要小的元素之后,将元素放下来,然后将后面的元素依次后移,腾出位置。
举个例子来说,对于数组 [2, 1,0, 4],首先从 1 也就是第二个元素开始,与前面的 2 进行对比,发现 1 比 2 小,而且 2 前面也没有元素了,所以要将 1 放置在 2 的前面,这个时候 2 就需要后移为 1 腾出位置,这个时候数组元素就变成了 [1, 2, 0, 4]。然后 0 与 2 比较,发现 0 比 2 小,这个时候交换 0 与 2 的位置,再 与 1 进行比较,发现 0 还是比 1 小,所以交换 1 与 0 的位置,这个时候数组就变成了 [0, 1, 2, 4]。4 与 2 比较,比 2 大,保持原位置不变。
那么,插入排序与选择排序的差别在哪里呢?选择排序会对余下的所有元素进行大小比较,而插入排序则不是这样,对位于 i 下标的元素来说,只要它在 (i-1) - 0 的路径中找到比 i 小的元素,它就会终止比较,这对于一个已经基本排序的数组来说,是一个非常大的优化。不过,有利也有弊,插入排序相对于选择排序的缺点就是它移动次数会显著增加。
在最佳情况下,也就是说对于一个有序数组,插入排序只需要 N-1 次比较和 0 次交换。在最差情况下,也就是对于一个逆序数组,它需要 N^2 / 2
次比较和 N^2 /2
次交换。
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
function insertionSort(array) {
var length = array.length,
temp;
for(var i = 1; i < length; i++) {
for(var j = i; j > 0 && array[j] < array[j - 1]; j--) {
swap(array, j, j-1);
}
}
}
插入排序平均情况下会比选择排序快一倍左右,我以万级数量级数据对这两个算法进行了比较,选择排序耗时 120 ms 左右, 插入排序在 65ms 左右。当然,这只是在我电脑上的数据,根据电脑配置的不同得出的结果会有所不同。
还有一点值得提及,对于一个基本有序的数据来说,插入排序可能比任何排序算法都要快,也就是说它可能比归并排序和快速排序还要快。那么该怎么定义基本有序呢?满足下面三个条件之一就可以了。
- 数组中的每个元素距离它的最终位置都不远。
- 一个有序的大数组接一个小数组。
- 数组中只有几个元素的位置不正确。
希尔排序
希尔排序其实就是对插入排序进行改进,让其适应大数组排序。看了插入排序的代码你可能也发现了一个问题,如果一个非常大的数组,比如千万数量级的数组,它是逆序的,使用插入排序的话,那么我们不得不将最后一个元素一步步的移动到第一位,将倒数第二个元素一步步的移动到第二位,这样的话真的是拖垮了这个算法的性能,也就是插入排序的最坏情况。
希尔排序只是对插入排序进行了一点点修改,却将这个算法的性能提升了一大截,将细节的作用展现的淋漓尽致。简单地说,希尔排序的思想就是使数组中任意间隔 h 的元素都是有序的,这样的数组被称为 h 有序数组。如果 h 很大,那么我们一次就可以将一个元素移动到很远的位置,这样就弥补了插入排序的缺陷。
所以,关键的就是这个 h 的值该如何选择呢?事实上算法的性能和 h 的大小是有关系的,不过到目前为止并不知道 h 选取什么值是最好的,所以我一般选择数组长度的 1/3 左右 。
function shellSort(array) {
var length = array.length,
temp,
h = 1;
while (h < length / 3) {
h = 3 * h;
}
while (h >= 1) {
for (var i = h; i < length; i++) {
for (var j = i; j >= h && array[j] < array[j - h]; j -= h) {
swap(array, j, j - h);
}
}
h = h / 3;
}
}
关于希尔排序的运行时间具体是多少,目前尚不清楚,只能说它的运行时间达不到平方级别,最坏情况下的比较次数与 N^(3/2)
成正比。
对于万级数量级数组,我用希尔排序只花了 8ms 的时间,相比于插入排序和选择排序,这种算法真是快了不知多少倍!
冒泡排序
对于冒泡排序是真的没什么好讲的了,它和选择排序一样,是各教科书介绍的重点,它的思想就是每次迭代将最大的元素排到末尾。我感觉这种算法在比较次数上和选择排序相同,而移动次数却又和插入排序差不多,所以性能比较差,是理论上的排序算法,并不实用。
function bubleSort(array) {
var length = array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - i - 1; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}
网友评论