JS数组排序||sort方法
发布日期:2021-11-21 16:35:40
浏览次数:12
分类:技术文章
本文共 2707 字,大约阅读时间需要 9 分钟。
sort方法不传参数的话,排序默认根据字符串的Unicode排序;
传递参数的情况,所传的参数必须为一个函数,该函数对a,b两个参数进行比较,返回一个结果,具体如下: a 大于 b 返回一个大于0的值,a在b位置的后面; a 等于 b 返回一个等于0的值,a、b位置不变; a 小于 b 返回一个小于0的值,a在b位置的前面;冒泡排序
原理:对数组进行遍历,相邻元素根据大小进行交换,每次遍历将最小值推至最前方,然后对剩下的值再次进行比较 最坏时间复杂度:O(n^2) 空间复杂度:O(1)function pop(array) {
var len = array.length, i, j, tmp, result; result = array.slice(0); for (i = 0; i < len; i++) { for (j = len - 1; j > i; j--) { if (result[j] < result[j - 1]) { tmp = result[j - 1]; result[j - 1] = result[j]; result[j] = tmp; } } } return result; } alert(pop([5,6,4,7,8]));快速排序
原理:从数组中取一个值为基准值,并将剩下的值与之比较,小于基准值的放到左边,大于基准值的放到右边,并再次对左右两边进行快速排序,直至左右两边只剩一个元素。 最坏时间复杂度:O(n^2) 当选择的基准值为最大值或最小值时 稳定性:不稳定 平均时间复杂度:O(n*log2n)function quick(arr){
var len=arr.length; if(len<=1){ return arr; } var index=Math.floor(len/2),//向下取整 根据中间的值作为比较对象 pindex=arr.splice(index,1)[0],//需要删除中间值,以缩小排序的数组大小 left=[],//定义左右两个数组 左大右小 right=[]; for(var i=0;i<len-1;i++){ //遍历整个数组 大放右 小放左 if(arr[i]>=pindex){ right.push(arr[i]); }else{ left.push(arr[i]); } } return quick(left).concat([pindex],quick(right)); //继续递归并将数组合并 } alert(quick(arr)); 插入排序原理:从数组第二个值开始,依次将后续的数值经过比较与前面排序后的序列比较后插入
最坏时间复杂度:O(n2):当数组是从大到小排列时,插入第一个元素需要移动一次,插入第二个需要移动两次,以此类推,所以一共为1+2+3+4+......+(n-1),与冒泡排序相同 最优时间复杂度:最好的情况是数组已经由小到大排好,则为O(n) 稳定性:稳定 空间复杂度:O(1) function insert(array) { var len = array.length, i, j, tmp, result; // 设置数组副本 result = array.slice(0); for(i=1; i < len; i++){ //数组第一个值为默认的衡量值 tmp = result[i]; //从第二个值开始与之前的值进行比较 j = i - 1; //之前已经排好序的数组的最后一个 while(j>=0 && tmp < result[j]){ //如果j大于等于零(否则越界) 与最后一个值进行比较,如果小于 result[j+1] = result[j]; //则将最后一个值后移一位 j --; //j往前移动一位 } result[j+1] = tmp; //比较完成 这时result[j]<temp或者j已经为-1,则将tmp的值赋给j+1 } return result; }希尔排序
原理:由于直接插入排序每一次插入新值都要与之前已经序列化的部分进行比较,越往后所需要比较的次数越多,所以希尔排序通过设置步长,将整个数组依照步长分为一个个分块儿,将分块序列化之后再将整个数组进行插入排序。 时间复杂度:希尔排序的时间复杂度和其增量序列有关系,这涉及到数学上尚未解决的难题;不过在某些序列中复杂度可以为O(n1.3); 空间复杂度:O(1) 稳定性:不稳定 function shell(arr) { var len =arr.length, i,j,temp, gap = Math.floor(len/2);//设置步长 while (gap>0) { //当步长大于0时 每次步长减半 for (i = gap; i < len; i++) { temp = arr[i]; j = i-gap; while (j>=0&&temp<arr[j]){ //J>=0且arr[i]<arr[j]时 arr[j+gap]=arr[j]; //a[j]的值向前移动一个步长 j -=gap; //j往前移动一个步长 } arr[j+gap] =temp; } gap = Math.floor(gap/2);//每次步长缩短一半直至为1 } return arr; } alert(shell([2,5,7,9,45,12,6,74])); 选择排序 原理:与冒泡排序类似,只不过选择排序不是通过相邻元素交换而将最小值“冒泡”到顶端,而是从数组第一个元素开始,与后面的的元素进行比较,如果后面的元素都比他大,则不需要交换,如果有比其小的,则两个值相互交换。 最坏时间复杂度:O(n2) 平均时间复杂度:O(n2) 稳定性:稳定 空间复杂度:O(1) function select(arr) { var len = arr.length, i,j,temp,k; for (i=0;i<len;i++){ //遍历数组的每一个值,并于其后的值比较找出最小值之后互换 k=i; for (j=i+1;j<len;j++){ if (arr[j]<arr[k])k=j; } if (k!=i){ //如果arr[i]已经是最小的则不需要互换 temp=arr[k]; arr[k]=arr[i]; arr[i]=temp; } } return arr; } alert(select([14,5,45,2,6,7,5,9]));转载地址:https://blog.csdn.net/yyychocolate/article/details/108095675 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月06日 02时07分50秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
基础知识——进位制
2019-04-27
Lua(十二)——表
2019-04-27
Lua(十三)——模块与包
2019-04-27
Lua(四)——变量
2019-04-27
Lua(十四)——元表
2019-04-27
Lua(十五)——协同程序
2019-04-27
Lua(十六)——文件
2019-04-27
Lua(十七)——面向对象
2019-04-27
Lua(十八)——错误处理,垃圾回收
2019-04-27
xLua(一)——介绍
2019-04-27
xLua(二)——下载
2021-06-30
xLua(三)——在C#中访问Lua代码
2021-06-30
xLua(四)——C#访问Lua的基本类型
2021-06-30
xLua(五)——C#访问Lua的table
2021-06-30
xLua(六)——C#访问Lua的function
2021-06-30
基础知识——常用单位介绍
2021-06-30
xLua(七)——Lua访问C#(一)
2021-06-30
xLua(八)——Lua访问C#(二)
2021-06-30
Unity中实现解析Json文件
2021-06-30
Unity自带Json解析库——JsonUtility
2021-06-30