JS-排序详解:冒泡排序、选择排序和快速排序
2024-09-01 10:12:00
JS-排序详解-冒泡排序
说明
- 时间复杂度指的是一个算法执行所耗费的时间
- 空间复杂度指运行完一个程序所需内存的大小
- 稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面
- 不稳定指,如果a=b,a在b的前面,排序后可能会交换位置
JS冒泡排序
原理
依次比较相邻的两个值,如果后面的比前面的小,则将小的元素排到前面。依照这个规则进行多次并且递减的迭代,直到顺序正确。
时间复杂度,空间复杂度,稳定性
- 平均时间复杂度O(n*n)
- 最好情况O(n)
- 最差情况O(n*n)
- 空间复杂度O(1)
- 稳定性:稳定
冒泡排序的写法
var examplearr=[8,94,15,88,55,76,21,39];
function sortarr(arr){
for(i=0;i<arr.length-1;i++){
for(j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
var temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr;
}
sortarr(examplearr);
console.log(examplearr);
解析
两个循环
当i=0的时候,里面的循环完整执行,从j=0执行到j=6,这也就是第一遍排序,结果是将最大的数排到了最后,这一遍循环结束后的结果应该是[8,15,88,55,76,21,39,94]
当i=1的时候,里面的循环再次完整执行,由于最大的数已经在最后了,没有必要去比较数组的最后两项,这也是j<arr.length-1-i的巧妙之处,结果是[8,15,55,76,21,39,88,94]
说到这里,规律就清楚了,每次将剩下数组里面最大的一个数排到最后面,当第一个循环执行到最后的时候,也就是i=6,此时,j=0,只需要比较数组的第一和第二项,比较完毕,返回。
JS-排序详解-选择排序
说明
- 时间复杂度指的是一个算法执行所耗费的时间
- 空间复杂度指运行完一个程序所需内存的大小
- 稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面
- 不稳定指,如果a=b,a在b的前面,排序后可能会交换位置
JS选择排序
原理
首先从原始数组中找到最小的元素,并把该元素放在数组的最前面,然后再从剩下的元素中寻找最小的元素,放在之前最小元素的后面,知道排序完毕。
时间复杂度,空间复杂度,稳定性
- 平均时间复杂度O(n*n)
- 最好情况O(n*n)
- 最差情况O(n*n)
- 空间复杂度O(1)
- 稳定性:不稳定
选择排序的写法
var example=[8,94,15,88,55,76,21,39];
function selectSort(arr){
var len=arr.length;
var minIndex,temp;
console.time('选择排序耗时');
for(i=0;i<len-1;i++){
minIndex=i;
for(j=i+1;j<len;j++){
if(arr[j]<arr[minIndex]){
minIndex=j;
}
}
temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
console.timeEnd('选择排序耗时');
return arr;
}
console.log(selectSort(example));
解析
minIndex始终保存着最小值的位置的索引,随着i的自增,遍历的数组长度越来越短,直到完成排序。
JS-排序详解-快速排序
说明
- 时间复杂度指的是一个算法执行所耗费的时间
- 空间复杂度指运行完一个程序所需内存的大小
- 稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面
- 不稳定指,如果a=b,a在b的前面,排序后可能会交换位置
JS快速排序
原理
从数组中选定一个基数,然后把数组中的每一项与此基数做比较,小的放入一个新数组,大的放入另外一个新数组。然后再采用这样的方法操作新数组。直到所有子集只剩下一个元素,排序完成。
时间复杂度,空间复杂度,稳定性
- 平均时间复杂度O(nlogn)
- 最好情况O(nlogn)
- 最差情况O(n*n)
- 空间复杂度O(logn)
- 稳定性:不稳定
快速排序的写法
var examplearr=[8,94,15,88,55,76,21,39];
function fastsort(arr){
if(arr.length<2){
return arr;
}
var left=[];
var right=[];
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];
for(i=0;i<arr.length;i++){
if(arr[i]<pivot){
left.push(arr[i]);
}else{
right.push(arr[i])
}
}
return fastsort(left).concat([pivot],fastsort(right));
}
console.log(fastsort(examplearr));
解析
pivotIndex是将数组的长度除2向下取整得到的一个数值,数组的长度是不断减半的,所以最后它的值为0
pivot是利用splice方法从数组里获取一个基数
最新文章
- python 学习笔记十六 django深入学习一 路由系统,模板,admin,数据库操作
- One to One 的数据库模型设计与NHibernate配置
- jquery.cookie.js 用法
- Linux 安装 redis
- Linux系统编程@文件操作(一)
- 某些手机一直连不上adb的解决办法
- Xamarin Mono错误: unable to find explicit activity class
- 使用 OpenWrt Image Generator 为 WR703N 路由器定制固件
- iOS中的图像处理(一)——基础滤镜
- Shell中一键添加作者,版权信息
- Java经典编程题50道之十一
- OpenLiveWriter.exe已停止工作---解决办法
- Python3 字典 setdefault() 方法
- maven打包不包含配置文件[z]
- [JavaScript] - 7kyu
- 搭建Nuget.Server push时,";Failed to process request. &#39;Method Not Allowed&#39;";
- Quiver快速入门
- Xadmin的配置及使用
- 基础js--调试js
- 本地连不上远程mysql数据库(2)
热门文章
- 小马哥课堂-统计学-t分布(2)
- WEB前端的性能优化
- 当一个线程进入一个对象的synchronized方法A之后,其他线程是否可进入此对象的synchronized方法B?
- NPAPI命休矣
- 控件禁用与启easyui用
- Petrozavodsk Summer-2015. Ivan Smirnov Contest 1 B Bloom
- 【BZOJ】3403: [Usaco2009 Open]Cow Line 直线上的牛(模拟)
- poj 1659(havel算法)
- 在ASP.NET MVC3 中利用JSONP跨域登录WEB系统
- 把本地的jar包安装到maven库中