这篇文章主要为大家详细介绍了 JavaScript 希尔排序、快速排序、归并排序算法,感兴趣的朋友可以参考一下
Javascript 是一种由 Netscape 的 LiveScript 发展而来的原型化继承的基于对象的动态类型的区分大小写的客户端脚本语言,主要目的是为了解决服务器端语言,比如 Perl,遗留的速度问题,为客户提供更流畅的浏览效果。
以 var a = [4,2,6,3,1,9,5,7,8,0]; 为例子。
1. 希尔排序。 希尔排序是在插入排序上面做的升级。是先跟距离较远的进行比较的一些方法。
- function shellsort(arr){
- var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp;
- while(gap>0){
- for (var k = 0; k < gap; k++) {
- var tagArr = [];
- tagArr.push(arr[k])
- for (i = k+gap; i < len; i=i+gap) {
- temp = arr[i];
- tagArr.push(temp);
- for (j=i-gap; j >-1; j=j-gap) {
- if(arr[j]>temp){
- arr[j+gap] = arr[j];
- }else{
- break;
- }
- }
- arr[j+gap] = temp;
- }
- console.log(tagArr,"gap:"+gap);//输出当前进行插入排序的数组。
- console.log(arr);//输出此轮排序后的数组。
- }
- gap = parseInt(gap/2);
- }
- return arr;
- }
过程输出:
- [4, 9] "gap:5"
- [4, 2, 6, 3, 1, 9, 5, 7, 8, 0]
- [2, 5] "gap:5"
- [4, 2, 6, 3, 1, 9, 5, 7, 8, 0]
- [6, 7] "gap:5"
- [4, 2, 6, 3, 1, 9, 5, 7, 8, 0]
- [3, 8] "gap:5"
- [4, 2, 6, 3, 1, 9, 5, 7, 8, 0]
- [1, 0] "gap:5"
- [4, 2, 6, 3, 0, 9, 5, 7, 8, 1]
- [4, 6, 0, 5, 8] "gap:2"
- [0, 2, 4, 3, 5, 9, 6, 7, 8, 1]
- [2, 3, 9, 7, 1] "gap:2"
- [0, 1, 4, 2, 5, 3, 6, 7, 8, 9]
- [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1"
- [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
由输出可以看到。第一轮间隔为 5。依次对这些间隔的数组插入排序。
间隔为 5:
- [4, 9] "gap:5"
- [4, 2, 6, 3, 1, 9, 5, 7, 8, 0]
- [2, 5] "gap:5"
- [4, 2, 6, 3, 1, 9, 5, 7, 8, 0]
- [6, 7] "gap:5"
- [4, 2, 6, 3, 1, 9, 5, 7, 8, 0]
- [3, 8] "gap:5"
- [4, 2, 6, 3, 1, 9, 5, 7, 8, 0]
- [1, 0] "gap:5"
- [4, 2, 6, 3, 0, 9, 5, 7, 8, 1]
- [4, 6, 0, 5, 8] "gap:2"
- [0, 2, 4, 3, 5, 9, 6, 7, 8, 1]
- [2, 3, 9, 7, 1] "gap:2"
- [0, 1, 4, 2, 5, 3, 6, 7, 8, 9]
- [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1"
- [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
间隔为 2:
- [4, 2, 6, 3, 0, 9, 5, 7, 8, 1]
- 4 6 0 5 8
- 2 3 9 7 1
排序后:
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9]
间隔为 1:
排序后:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。
2. 快速排序。把一个数组以数组中的某个值为标记。比这个值小的放到数组的左边,比这个值得大的放到数组的右边。然后再递归 对左边和右边的数组进行同样的操作。直到排序完成。通常以数组的第一个值为标记。
代码:
- function quickSort(arr) {
- var len = arr.length,
- leftArr = [],
- rightArr = [],
- tag;
- if (len < 2) {
- return arr;
- }
- tag = arr[0];
- for (i = 1; i < len; i++) {
- if (arr[i] <= tag) {
- leftArr.push(arr[i])
- } else {
- rightArr.push(arr[i]);
- }
- }
- return quickSort(leftArr).concat(tag, quickSort(rightArr));
- }
3. 归并排序。把一系列排好序的子序列合并成一个大的完整有序序列。从最小的单位开始合并。然后再逐步合并合并好的有序数组。最终实现归并排序。
合并两个有序数组的方法:
- function subSort(arr1, arr2) {
- var len1 = arr1.length,
- len2 = arr2.length,
- i = 0,
- j = 0,
- arr3 = [],
- bArr1 = arr1.slice(),
- bArr2 = arr2.slice();
- while (bArr1.length != 0 || bArr2.length != 0) {
- if (bArr1.length == 0) {
- arr3 = arr3.concat(bArr2);
- bArr2.length = 0;
- } else if (bArr2.length == 0) {
- arr3 = arr3.concat(bArr1);
- bArr1.length = 0;
- } else {
- if (bArr1[0] <= bArr2[0]) {
- arr3.push(bArr1[0]);
- bArr1.shift();
- } else {
- arr3.push(bArr2[0]);
- bArr2.shift();
- }
- }
- }
- return arr3;
- }
归并排序:
- function mergeSort(arr) {
- var len = arr.length,
- arrleft = [],
- arrright = [],
- gap = 1,
- maxgap = len - 1,
- gapArr = [],
- glen,
- n;
- while (gap < maxgap) {
- gap = Math.pow(2, n);
- if (gap <= maxgap) {
- gapArr.push(gap);
- }
- n++;
- }
- glen = gapArr.length;
- for (var i = 0; i < glen; i++) {
- gap = gapArr[i];
- for (var j = 0; j < len; j = j + gap * 2) {
- arrleft = arr.slice(j, j + gap);
- arrright = arr.slice(j + gap, j + gap * 2);
- console.log("left:" + arrleft, "right:" + arrright);
- arr = arr.slice(0, j).concat(subSort(arrleft, arrright), arr.slice(j + gap * 2));
- }
- }
- return arr;
- }
排序 [4,2,6,3,1,9,5,7,8,0] 输出:
- left: 4 right: 2 left: 6 right: 3 left: 1 right: 9 left: 5 right: 7 left: 8 right: 0 left: 2,
- 4 right: 3,
- 6 left: 1,
- 9 right: 5,
- 7 left: 0,
- 8 right: left: 2,
- 3,
- 4,
- 6 right: 1,
- 5,
- 7,
- 9 left: 0,
- 8 right: left: 1,
- 2,
- 3,
- 4,
- 5,
- 6,
- 7,
- 9 right: 0,
- 8
看出来从最小的单位入手。
第一轮先依次合并相邻元素:4,2; 6,3; 1,9; 5,7; 8,0
合并完成之后变成: [2,4,3,6,1,9,5,7,0,8]
第二轮以 2 个元素为一个单位进行合并:[2,4],[3,6]; [1,9],[5,7]; [0,8],[];
合并完成之后变成:[2,3,4,6,1,5,7,9,0,8]
第三轮以 4 个元素为一个单位进行合并:[2,3,4,6],[1,5,7,9]; [0,8],[]
合并完成之后变成: [1,2,3,4,5,6,7,9,0,8];
第四轮以 8 个元素为一个单位进行合并:[1,2,3,4,5,6,7,9],[0,8];
合并完成。 [0,1,2,3,4,5,6,7,8,9];
来源: http://www.phperz.com/article/17/0223/265946.html