摘要:本篇教程介绍了JavaScript基础教程 快速排序实现详解,希望阅读本篇文章以后大家有所收获,帮助大家对JavaScript的理解更加深入。
本篇教程介绍了JavaScript基础教程 快速排序实现详解,希望阅读本篇文章以后大家有所收获,帮助大家对JavaScript的理解更加深入。
<
一、特定的数字数字
var arr=[a1,...,an]; // 长度为n的数组
二、冒泡排序
1、思想:两层for循环,外层从第一个数到倒数第二个数,内层从外层的后面一个数到最后一个数
第1次内层循环,循环n-1次,找到最小数放到a0中,同时将原来a0的值赋值到原数组中最小数的位置;
第2次内层循环,循环n-2次,找到第二小的数放到a1中,同时将原来a1的值赋值到原数组中第二小的数的位置;
...
第n-1次内层循环,循环1次,找到最大数就是最后一个数an;
等差数列,循环次数为: (n-1)(n -1+1)/ 2 = n(n-1)/2
2、特点:排序算法的基础。简单实用易于理解,缺点是比较次数多,效率较低。
3、示例:
function minK(N, K, sort) {
var randomArr = []; // 长度为N的随机数字数组
for(var n = 0; n < N; n++) {
randomArr.push(Math.floor(Math.random() * 200));
}
console.log(randomArr)
if(N <= 1) {
return randomArr;
}
var oBoolean;
oBoolean = (N/2 < K && !sort) ? true : false;
K = oBoolean ? N - K : K;
var num = 0; // 循环次数
var t = 0; // 中间存值变量
for(var i = 0 ; i < K; i++) {
for(var j = i; j < N - 1; j++) {
if(oBoolean) {
if(randomArr[i] < randomArr[j+1]) {
t = randomArr[i];
randomArr[i] = randomArr[j+1];
randomArr[j+1] = t;
}
}else{
if(randomArr[i] > randomArr[j+1]) {
t = randomArr[i];
randomArr[i] = randomArr[j+1];
randomArr[j+1] = t;
}
}
num++;
}
}
return oBoolean ? [randomArr.slice(K), num] : [randomArr.slice(0, K), num];
}
console.log(minK(11, 5, true))
该示例实现长度为N的数字数组,求前K个最小的数,sort为true时,前K个数是排序的,当K=N&&sort为true时,就是数组的排序返回;
三、二分法
1、思想:先找到一个基准点(数组中的任何一个),然后数组被该基准点分为两部分,依次与该基准点数据比较,如果比它小,放左边;反之,放右边。 左右分别用一个空数组去存储比较后的数据。最后递归执行上述操作,直到数组长度<=1;
2、特点:快速,常用。缺点是需要另外声明两个数组,浪费了内存空间资源。
3、示例:
var kpTimes = 0;
var kuaiPai = function(arr) {
if(arr.length <= 1) {
return arr;
}
//var midIndex = Math.floor(arr.length/2);
//var minIndexVal = arr.splice(midIndex,1); var minIndexVal = arr.pop();// 数组的最后一个
var leftArr = [];
var rightArr = [];
for(var i = 0; i < arr.length; i++) {
if(arr[i] > minIndexVal) {
rightArr.push(arr[i]);
}else{
leftArr.push(arr[i]);
}
kpTimes++;
}
return kuaiPai(leftArr).concat(minIndexVal,kuaiPai(rightArr))
}
console.log(kuaiPai(arr),kpTimes);
可以用二分法实现求长度为N的数字数组的前K个最小的数。
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标WEB前端JavaScript频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号