动画演示几种常见排序算法--桶排序、冒泡、鸡尾酒、插入、快速...

动画演示几种常见排序算法　--　桶排序、冒泡、鸡尾酒、快速...（JavaScript 版）

　　同学们，如果你手上有54张次序乱了的扑克牌，你要把它们重新排序，用什么方法？先想想再往看下吧。

　　对计算机算法有兴趣，或想参加全国青少年信息学（计算机）奥林匹克联赛NOIP的同学们请特别留神咯，希望通过这篇文章，让大家对算法有个初步认识。

　　这个时候已经有同学举手了，哈哈，请说说你的排序法吧！

　　只要把凌乱的牌逐个往桌子上放就可以了，放的时候，注意要放到适当的位置上。比如，第一张牌是葵扇9，我就放到第一排第九个位置；第二张牌是方片A，就放到第四排的第一个位置，如此类推，如下图，最后把全部牌按次序收拾起来就可以了！

　　非常好！这种方法也类似于计算机排序算法里的"桶排序"(Bucket sort)法哦！这个算法就好比有54个桶，编号0~53，每出现一张牌，就往对应编号的桶里面放，最后将所有桶的排序结果合并起来。这是一种非常快的排序算法哦~　当然，这里也要告诉大家，计算机往往要处理大量数据，真正的桶排序算法要比这个复杂些，每个桶不是存放一张牌，而是一定区间范围的牌，例如黑桃A到黑桃K由一个桶存放，红桃A到红桃K由第二个桶存放，如此类推，54张牌需4个桶。类似的，计算机对数据排序时，例如要对大小为[1..1000]范围内的n个整数A[1..n]排序，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储(10..20]的整数，……集合B[i]存储((i-1)*10, i*10]的整数，i = 1,2,..100。总共有100个桶。然后对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。然后再对这100个桶中每个桶里的数字排序，这时可用别的排序法，如冒泡法，快速排序法，或者是以递归方式继续使用桶排序进行排序都可以。现在，我们已经掌握了桶排序的基本思路咯！我们也需要知道，这种方法的缺点是什么？就是要有足够大的桌子！对计算机来说，内存空间要足够大，才能对大量的数据用"桶排序"法进行排序哦！

　　如果我们压根就没有桌子，只有一对手，怎么把54张牌排好序呢？

　　聪明的同学们想到了，先比较第1、第2两张牌，小的放前面，大的放后面，再比较第2，第3张牌，也是小的放前面，大的放后面，如此类推，经过53次比较，最大的那张牌“大鬼”就肯定排在最后，归位了，沉底了，小的牌就排比较前，浮上来，冒泡了。然后进行第二次循环，也就是再比较开头的两张牌...... 这思路也就是计算机“冒泡排序”法哦！但这种方法很慢，是不是？那我们继续开动脑筋咯！

　　又想到新方法了吧？好的，好的，开动脑筋就能想到了哦~

　　让我们看看不同方法的比较，来看 排序动画演示，看看哪种算法速度快吧，让老师提醒一句，不要用太大数组去测试冒泡排序，浏览器崩溃了我不管哦。如果有兴趣，还可以下载源码。

　　每个浏览器测试得出的数据会不一样。比如我用chrome 测试一般快速排序都会最快，IE 则根据数组长度有可能希尔最快。（微信浏览器看不了动画演示，可能检测到JS怕不安全）。

　　冒泡排序：最简单，也最慢，貌似长度小于7最优。
　　插入排序：比冒泡快，比快速排序和希尔排序慢，较小数据有优势。
　　快速排序：这是一个非常快的排序方式，V8的sort方法就使用快速排序和插入排序的结合。
　　希尔排序：在非chrome下数组长度小于1000，希尔排序比快速更快。
　　系统方法：在firefox下系统的这个方法非常快。

代码举例：
// ---------- 一些排序算法
// js 利用sort进行排序
systemSort: function(array) {
return array.sort(function(a, b) {
return a - b;
});
},

// 冒泡排序
bubbleSort: function(array) {
var i = 0,
len = array.length,
j, d;
for (; i < len; i++) {
for (j = 0; j < len; j++) {
if (array < array[j]) {
d = array[j];
array[j] = array;
array = d;
}
}
}
return array;
},

// 快速排序
quickSort: function(array) {
//var array = [8,4,6,2,7,9,3,5,74,5];
//var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
var i = 0;
var j = array.length - 1;
var Sort = function(i, j) {

// 结束条件
if (i == j) {
return
};

var key = array;
var stepi = i; // 记录开始位置
var stepj = j; // 记录结束位置
while (j > i) {
// j <<-------------- 向前查找
if (array[j] >= key) {
j--;
} else {
array = array[j]
//i++ ------------>>向后查找
while (j > ++i) {
if (array > key) {
array[j] = array;
break;
}
}
}
}

// 如果第一个取出的 key 是最小的数
if (stepi == i) {
Sort(++i, stepj);
return;
}

// 最后一个空位留给 key
array = key;

// 递归
Sort(stepi, i);
Sort(j, stepj);
}

Sort(i, j);

return array;
},

// 插入排序
insertSort: function(array) {

// http://baike.baidu.com/image/d57e99942da24e5dd21b7080
// http://baike.baidu.com/view/396887.htm
//var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
var i = 1,
j, step, key, len = array.length;

for (; i < len; i++) {

step = j = i;
key = array[j];

while (--j > -1) {
if (array[j] > key) {
array[j + 1] = array[j];
} else {
break;
}
}

array[j + 1] = key;
}

return array;
},

// 希尔排序
//Jun.array.shellSort(Jun.array.df(10000));
shellSort: function(array) {

// http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
// var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10];
var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在维基上看到这个最优的步长较小数组
//var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1]//针对大数组的步长选择
var i = 0;
var stepArrLength = stepArr.length;
var len = array.length;
var len2 = parseInt(len / 2);

for (; i < stepArrLength; i++) {
if (stepArr > len2) {
continue;
}

stepSort(stepArr);
}

// 排序一个步长
function stepSort(step) {

//console.log(step) 使用的步长统计
var i = 0,
j = 0,
f, tem, key;
var stepLen = len % step > 0 ? parseInt(len / step) + 1 : len / step;

for (; i < step; i++) { // 依次循环列
for (j = 1;
/*j < stepLen && */
step * j + i < len; j++) { //依次循环每列的每行
tem = f = step * j + i;
key = array[f];

while ((tem -= step) >= 0) { // 依次向上查找
if (array[tem] > key) {
array[tem + step] = array[tem];
} else {
break;
}
}

array[tem + step] = key;

}
}

}
return array;
}

部分内容摘自:来源

智少年教育