博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
JavaScript实现常见排序算法
阅读量:6449 次
发布时间:2019-06-23

本文共 4695 字,大约阅读时间需要 15 分钟。

这里用JavaScript实现冒泡排序、选择排序、插入排序、归并排序以及快速排序这些常见的排序算法

首先我们给本文约定一个实现的框架:定义一个ArrayList类里面包含排序数组声明、数组元素添加、排序算法实现以及数组输出的方法。

代码框架:

function ArrayList(){        var array=[];            this.inputArraymember=function(){   //将10个大小在1~15的随机数添加到数组中            var ins=0;            for(var i=0;i<10;i++){                ins=Math.floor(Math.random()*15+1);                array.push(ins);            }        };            this.相应的排序算法=function(){...算法的具体实现代码...};    //代码块替换部分            this.toString=function(separator){  //将数组按指定分隔符生成字符串方便输出            return array.join(separator);        };        }        var a = new ArrayList();    a.inputArraymember();    console.log("随机生成的原始数组为:"+a.toString('-'));    a.bubbleSort();    console.log("排序后数组为:"+a.toString('-'));

冒泡排序

用两层循环,第一层用来记录剩余的还未排序的数的个数,第二层用来在剩下的未排序的数中找到最大的数并将其放到未排序数的最后面(冒泡)。

代码实现:

this.bubbleSort=function(){         var length=array.length;        for(var i=0;i
array[j+1]){ var t=array[j]; array[j]=array[j+1];array[j+1]=t; } } } };

冒泡排序的时间复杂度是O(n²)。将以上代码替换文章开始约定的代码框架中的“代码块替换部分”即可用于在调试工具中运行查看代码运行结果。

选择排序

思路很简单,每次都找出未排序的数当中最小的数并放在开头,直到所有数的位置确定下来。说清楚点就是从所有序列中先找到最小的,然后放到第一个位置。之后再看剩余元素中最小的,放到第二个位置……以此类推。

代码实现:

this.selectsort=function(){        var length=array.length,currentMin;        for(var i=0;i
array[j]){ currentMin=j; } } if(i!==currentMin){ //若下标不是未排序的最开始的那个元素的下标,则将两者的值交换 var t=array[currentMin]; array[currentMin]=array[i]; array[i]=t; } } };

可看出,选择排序也用了两个嵌套着的循环,所以时间复杂度也是O(n²),是一种原址排序。

插入排序

从第二个数开始(因为第一个数只有一个,前面没得比。),与前面的数挨个比较,直到找到前一个数比当前值小,后一个数比当前值大的位置,让后将当前值置于此处,以此类推。

代码实现:

this.insertsort=function(){        var length=array.length, j,temp;        for(var i=1;i
0&&array[j-1]>temp){ //如果这个数比上一个数小,则让上一个数占据现在这个数的位置(右移每个比当前数小的数) array[j]=array[j-1]; j-- } array[j]=temp; //直到这个数不比上一个数小的时候,将这个数放在当前的位置 } };

归并排序

时间复杂度为O(nlogn)。归并用的是分治的思想,将原始数组切分成较小的数组,直到每个小数组只有一个位置,接着讲小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。

代码实现:

this.mergeSort=function() {        array = mergeSortRec(array);    };        //建堆函数,将数组一直拆分成两部分,直到各部分数组长度都为1的时候停止,然后进行merge操作    var mergeSortRec = function(array){        var length = array.length;        if (length === 1) {            return array;        }        var mid = Math.floor(length / 2),            left = array.slice(0, mid),//slice() 方法可从已有的数组中返回选定的元素,语法 arrayObject.slice(start,end)            right = array.slice(mid, length);        return merge(mergeSortRec(left), mergeSortRec(right));    };    //将各部分进行归并    var merge = function(left, right) {        var result = [],            il = 0,            ir = 0;        while(il < left.length && ir < right.length) {            if (left[il] < right[ir]) {                result.push(left[il++]);            } else {                result.push(right[ir++]);            }        }        //如果il数组还有剩余,则将其剩余部分添加到结果数组中        while (il < left.length) {            result.push(left[il++]);        }        //如果ir数组还有剩余,则将其剩余部分添加到结果数组中        while (ir < right.length) {            result.push(right[ir++]);        }        return result;    };

快速排序

时间复杂度为O(logn)。用的是分治的思想。

代码实现:

this.quickSort = function(){        quick(array,  0, array.length - 1);    };    var partition = function(array, left, right) {    //划分过程                //主元的选择方法最好是随机选择一个数组想或是选择中间项,这里选择中间项        var pivot = array[Math.floor((right + left) / 2)],            i = left,            j = right;        console.log('pivot is ' + pivot + '; left is ' + left + '; right is ' + right);        while (i <= j) {            while (array[i] < pivot) {                i++;                console.log('i = ' + i);            }            while (array[j] > pivot) {                j--;                console.log('j = ' + j);            }            if (i <= j) {                console.log('swap ' + array[i] + ' with ' + array[j]);                swapQuickStort(array, i, j);                i++;                j--;            }        }        return i;    };    var swapQuickStort = function(array, index1, index2){        var aux = array[index1];        array[index1] = array[index2];        array[index2] = aux;    };    var quick = function(array, left, right){//将子数组分离为较小值数组和较大值数组        var index;        if (array.length > 1) {            index = partition(array, left, right);            if (left < index - 1) {                quick(array, left, index - 1);            }            if (index < right) {                quick(array, index, right);            }        }        return array;    };

转载地址:http://mrlwo.baihongyu.com/

你可能感兴趣的文章
2012.5.7
查看>>
Cent OS查看系统版本信息的几个命令
查看>>
我的友情链接
查看>>
使用正确的筛选参数来提高查询性能
查看>>
网易云课堂Linux运维在线班命令笔记
查看>>
static
查看>>
通过字体大小的设计来提高用户体验
查看>>
请输入两个数字
查看>>
面试题:将字符串中的中英文分开显示
查看>>
python-09
查看>>
HDU 1542 Atlantis[扫描线]
查看>>
spark SQL学习(spark连接 mysql)
查看>>
centos查看端口被哪个应用端口占用命令
查看>>
Python学习笔记3-字符串
查看>>
logistic 回归(线性和非线性)
查看>>
nginx下禁止访问robots.txt的设置方法
查看>>
SQLPLUS 小技巧格式化字符串
查看>>
upc组队赛1 闪闪发光 【优先队列】
查看>>
AMD的Loom技术将大大改变新闻业的传统模式
查看>>
Thrift.0
查看>>