数组排序,基础算法

By admin in 4858美高梅 on 2019年4月5日

递归:递归函数是在贰个函数通过名字调用本身情况下结合的

 <script type=”text/javascript”>

<script type=”text/javascript”>
//一、选拔排序
/*var arr=[11,4,7,20,5,800,3,6,9];
var temp;
for(var i=0;i<arr.length;i++){
var minIndex=i;//若是i的值为最小值的目录;
for(var j=i+1;j<arr.length;j++){
if(arr[j]<arr[minIndex]){//最小值的目录;
minIndex=j;//
}
}
if(i!=minIndex){//判断最小的目录是或不是等于于假若的目录。
temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
}*/

7种算法  三种数组方法  注解变量升高 &&和||的回顾

/*function jiecheng(n){//n=5
if(n==1){//基点
return 1;
}else{
return n*jiecheng(n-1);
}

/*var arr=[11,4,7,20,5,800,3,6,9];
var temp;
for(var i=0;i<arr.length;i++){
var minIndex=i;//假如i的值为最小值的目录;
for(var j=i+1;j<arr.length;j++){
if(arr[j]<arr[minIndex]){//最小值的目录;
minIndex=j;//
}
}
if(i!=minIndex){//判断最小的目录是或不是等于于假诺的目录。
temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
数组排序,基础算法。}
}*/
/*alert(arr);
alert(arr.sort(function (a,b){
return a-b;
}));*/

 

一.冒泡排序

}*/

/*function selectSort(arr){
var temp;
for(var i=0;i<arr.length;i++){
var minIndex=i;//假若i的值为最小值的目录;
for(var j=i+1;j<arr.length;j++){
if(arr[j]<arr[minIndex]){//最小值的目录;
minIndex=j;//
}
}
if(i!=minIndex){//判断最小的目录是不是等于于若是的目录。
temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
}
return arr;
}
var arr=[11,4,7,20,5,800,3,6,9];
alert(selectSort(arr));*/

/*alert(arr);
alert(arr.sort(function (a,b){
return a-b;
}));*/

2.sort方法

//alert(jiecheng(100));//9.33262154439441e+157 10的157次方。

//插入排序
/*var arr=[11,4,7,20,5,800,3,6,9];
var temp;
for(var i=0;i<arr.length;i++){
var minIndex=i;//假使i的值为最小值的目录;
var min=arr[minIndex];//最小值
for(var j=i+1;j<arr.length;j++){
if(arr[j]<min){//最小值的目录;
temp=arr[j];
arr[j]=min;
min=temp;
}
}
console.log(min);//3,4,5,6,7,9,11,20,800
arr[i]=min;//i=0-8
}
alert(arr);*/
//快速排序: 数组的方式(splice/push/concat)+递归+Math数学方法。
//Math.floor();向下取整,Math.floor(壹.9玖)==壹
//Math.ceil();向上取整,Math.ceil(一.00玖)==二
/*function quicksort(array){
if(array.length<=壹){//假设数组的尺寸为一,再次来到当前的数组。
return array;
}
var left=[];//存放小于中间值的要素;
var right=[];//存放超越中间值的因素;
var midIndex=Math.floor(array.length/二);//取中间的目录
//var minValue=array[midIndex];
var minValue=array.splice(midIndex,1);//取中间的目录对应的值。
//var minValue=array.slice(midIndex,midIndex+1);
for(var i=0;i<array.length;i++){
if(array[i]<minValue){
left.push(array[i]);
}else if(array[i]>=minValue){//=相同的要素放置right数组里面。
right.push(array[i]);
}
}

//选拔排序(二)
/*function selectSort(arr){
var temp;
for(var i=0;i<arr.length;i++){
var minIndex=i;//假诺i的值为最小值的目录;
for(var j=i+1;j<arr.length;j++){
if(arr[j]<arr[minIndex]){//最小值的目录;
minIndex=j;//
}
}
if(i!=minIndex){//判断最小的目录是还是不是等于于假使的目录。
temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
}
return arr;
}
var arr=[11,4,7,20,5,800,3,6,9];
alert(selectSort(arr));*/

三.选项排序

//贰.应用递归求斐波那契数列的前20项
// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,

return quicksort(left).concat(minValue,quicksort(right));

//插入排序
/*var arr=[11,4,7,20,5,800,3,6,9];
var temp;
for(var i=0;i<arr.length;i++){
var minIndex=i;//即便i的值为最小值的目录;
var min=arr[minIndex];//最小值
for(var j=i+1;j<arr.length;j++){
if(arr[j]<min){//最小值的目录;
temp=arr[j];
arr[j]=min;
min=temp;
}
}
console.log(min);//3,4,5,6,7,9,11,20,800
arr[i]=min;//i=0-8
}
alert(arr);*/

四.递归算法  函数内部协调调用本身就是递归算法  可是得设定一个了结 
不然会陷于死循环

/*function fb(n){//n:位置
if(n==1 || n==2){//基点
return 1;
}else{
return fb(n-1)+fb(n-2)
}
}

}
var arr=[11,4,4,4,4,4,7,20,9,9,9,9,5,800,3,6,4,9];

//急忙排序: 数组的章程(splice/push/concat)+递归+Math数学方法。
//Math.floor();向下取整,Math.floor(1.9玖)==一
//Math.ceil();向上取整,Math.ceil(1.00玖)==二
/*function quicksort(array){
if(array.length<=一){//要是数组的长度为壹,重回当前的数组。
return array;
}
var left=[];//存放小于中间值的因素;
var right=[];//存放超越中间值的成分;
var midIndex=Math.floor(array.length/二);//取中间的目录
//var minValue=array[midIndex];
var minValue=array.splice(midIndex,一);//取中间的目录对应的值。
//var minValue=array.slice(midIndex,midIndex+1);
for(var i=0;i<array.length;i++){
if(array[i]<minValue){
left.push(array[i]);
}else if(array[i]>=minValue){//=相同的要素放置right数组里面。
right.push(array[i]);
}
}

5.快捷排序 能够冬天找二个值作为参考值  相比较 建立七个空数组 
比参考值小的放在左侧  比参考值大的放在左侧  左右边两边再进行那种操作
利用了递归 不断调用本身获得那种效益

//alert(fb(8));
for(var i=1;i<=20;i++){
document.write(fb(i)+’,’);
}*/

alert(quicksort(arr));*/

return quicksort(left).concat(minValue,quicksort(right));

陆.贪心算法 

//一.冒泡排序
//冒泡排序算法的规律如下:
//相比较相邻的因素。即使第三个比第叁个大,就交换他们五个。
//对每1对周围成分做一样的干活,从开端首先对到结尾的最后一对。在那或多或少,最终的要素应该会是最大的数。
//针对富有的成分重复以上的步调,除了最终三个。
//持续每回对越来越少的因素重复上面的步调,直到未有其它壹对数字须要比较。
/*var arr=[9,30,4,89,75,456,2,7,-100,9];
var times=0;//次数
for(var i=0;i<arr.length-壹;i++){//控制次数
-1:10个数字只须求两两比较陆遍。
for(var
j=0;j<arr.length-i-一;j++){//-i:i循环3回,j循环到底,每1次i的循环都已经排好三个数字。
if(arr[j]>arr[j+1]){
var temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
times++;
}
}
console.log(arr);
console.log(times);*/

/*var arr=[11,4,4,4,4,4,7,20,9,9,9,9,5,800,3,6,4,9];
var newarr=[];
newarr.push(arr[0]);//newarr=[11,4];
for(var i=1;i<arr.length;i++){
var bstop=false;//不重复
for(var j=0;j<newarr.length;j++){
if(arr[i]==newarr[j]){
bstop=true;//重复
break;//跳出循环
}
}
if(!bstop){
newarr.push(arr[i]);
}
}
alert(newarr);*/

}
var arr=[11,4,4,4,4,4,7,20,9,9,9,9,5,800,3,6,4,9];

7.折半查找 必须是平稳的 对半取值和选择的值进行相比 减少区间找出那个数

//二.精选排序

/*function norepeat(array){
var newarr=[];
newarr.push(array[0]);//newarr=[11,4];
for(var i=1;i<array.length;i++){
var bstop=false;//不重复
for(var j=0;j<newarr.length;j++){
if(array[i]==newarr[j]){
bstop=true;//重复
break;//跳出循环
}
}
if(!bstop){
newarr.push(array[i]);
}
}
return newarr;
}*/

alert(quicksort(arr));*/

证明变量的升官:任何证明变量和评释函数都会被升级到当下函数顶部

//选取排序(Selection sort)是一种简单直观的排序算法。
它的工作规律是每2次从待排序的数量成分中选出最小(或最大)的三个成分,存放在系列的初阶地方,
结束整个待排序的多少成分排完。
/*var arr=[9,300,4,890,7500,456,20,70,-100,-9];
for(var i=0;i<arr.length;i++){
var minindex=i;//假若最小值的下标
var minvalue=arr[minindex];//尽管最小值

//var arr=[11,4,4,4,4,4,7,’a’,9,9,9,9,5,800,3,6,4,9];
//alert(arr.indexOf(四,柒));//7代表数组的目录。
//indexOf() 第三个参数:数组的要素,再次回到成分对应第二个找到的目录,
第贰个参数:从这个位置伊始查找。

//数组去重(方法一)
/*var arr=[11,4,4,4,4,4,7,20,9,9,9,9,5,800,3,6,4,9];
var newarr=[];
newarr.push(arr[0]);//newarr=[11,4];
for(var i=1;i<arr.length;i++){
var bstop=false;//不重复
for(var j=0;j<newarr.length;j++){
if(arr[i]==newarr[j]){
bstop=true;//重复
break;//跳出循环
}
}
if(!bstop){
newarr.push(arr[i]);
}
}
alert(newarr);*/

&& 且 两者假取前者假  两真取前者真

for(var j=i+1; j<arr.length;j++){
if(minvalue>arr[j]){
minvalue=arr[j];
minindex=j;
}
}
//即使地点的for循环达成,代表minindex正是最小值的下标。
if(minindex!=i){//如果minindex!=i表明找到了实在的相当小值。不然就象征借使的恰恰正是微乎其微值。
var temp=arr[minindex]
arr[minindex]=arr[i];
arr[i]=temp;
}
}
console.log(arr);*/

//alert(arr.indexOf(‘b’));//-壹 未有找到重临-壹.
/* var arr=[11,4,4,4,4,4,7,’a’,9,9,9,9,5,800,3,6,4,9];
var newarr=[];
newarr.push(arr[0]);
for(var i=1;i<arr.length;i++){
if(newarr.indexOf(arr[i])==-1){
newarr.push(arr[i]);
}
}
alert(newarr);
*/
</script>

//数组去重(二)
/*function norepeat(array){
var newarr=[];
newarr.push(array[0]);//newarr=[11,4];
for(var i=1;i<array.length;i++){
var bstop=false;//不重复
for(var j=0;j<newarr.length;j++){
if(array[i]==newarr[j]){
bstop=true;//重复
break;//跳出循环
}
}
if(!bstop){
newarr.push(array[i]);
}
}
return newarr;
}*/

|| 或 取先河出现的非0得数  两假取后者假

//三.便捷排序(去重)

//var arr=[11,4,4,4,4,4,7,’a’,9,9,9,9,5,800,3,6,4,9];
//alert(arr.indexOf(四,7));//七代表数组的目录,起初查找的起第三地点
//indexOf() 第3个参数:数组的因素,重临成分对应第二个找到的目录,
第3个参数:从那些地点初步查找。

具体代码

//在数组中截取中间值,中间值能够随心所欲获取。–splice
//剩余的数组项都和中等值举行相比较,假使比中间值小,放置在2个数组中,比中间值大,放到别的2个数组中。
//分别对地点的多个数组重复上边的操作–递归
//最后利用concat进行拼接。输出结果

//alert(arr.indexOf(‘b’));//-一 未有找到重临-1.
/* var arr=[11,4,4,4,4,4,7,’a’,9,9,9,9,5,800,3,6,4,9];
var newarr=[];
newarr.push(arr[0]);
for(var i=1;i<arr.length;i++){
if(newarr.indexOf(arr[i])==-1){
newarr.push(arr[i]);
}
}
alert(newarr);
*/
</script>

//算法:化解难点的方案;化解难题的一文山会海清女士晰的一声令下

/*var arr=[9,300,4,890,7500,456,20,70,-100,-9];
function quicksort(array){
if(array.length<=1){
return array;
}else{
var midindex=parseInt(array.length/2);//获取中间索引
var midvalue=array.splice(midindex,1)[0];//获取中间值
var left=[];
var right=[];
for(var i=0;i<array.length;i++){
if(array[i]<midvalue){
left.push(array[i]);
}else{
right.push(array[i]);
}
}
return quicksort(left).concat(midvalue,quicksort(right));
}
}
console.log(quicksort(arr));*/

//本性一.时间夏朝性

//去重

//   二.答案唯1性

indexOf去重
/*var
arr=[9,301,4,8900,4,7500,4156,20,70,4156,-100,-9,9,9,4,8900,20];
var newarr=[];
for(var i=0;i<arr.length;i++){
if(newarr.indexOf(arr[i])==-1){
newarr.push(arr[i]);
}
}
console.log(arr);
console.log(newarr);*/

//一.冒泡排序

/*var
arr=[9,301,4,8900,4,7500,4156,20,70,4156,-100,-9,9,9,4,8900,20];

var arr = [5,3,7,8,4];

var newarr=arr.filter(function(value,index,array){

for (var i = 0; i < arr.length-1; i++) {

return arr.indexOf(value)==index;//数组项的目录是不是等于当前目录。

for (var j = 0; j < arr.length-i-1; j++) {

});*/

if (arr[j] > arr[j+1]) {

console.log(newarr);

var temp = arr[j+1];

var arr=[1,7,5,6,4,1,2,6];
function norepeat(arr){
for(var i=0;i<arr.length;i++){
for(var j=i+1;j<arr.length;j++){
if(arr[j]==arr[i]){
arr.splice(i,1);
arr.length-1;
j–;
}
}
}return arr;
}console.log(norepeat(arr));

arr[j+1] = arr[j];

arr[j] = temp;

}

}

}

console.log(arr);

//冒泡排序总共供给排序n-一趟,每一趟比较n-一-趟数这么数十次;每一遍排序可能交流反复成分,找到当中贰个成分的最后地点每趟对比都以相邻成分之间的大大小小比较

//二.sort 措施:js数组的二个艺术

var arr = [1,10,2,35,35,0,49];

//第一种

//需求依据数字的从小到大排序

// arr.sort();

// console.log(arr);

// arr.sort(function(obj1,obj2){

// if (Number(obj1) > Number(obj2)) {

// return 1;  //desc

// }else if(Number(obj1) < Number(obj2)){

// return -1;  //asc

// }else{

// return 0;  //same

// }

// });

// console.log(arr);

//第二种

arr.sort(function(obj1,obj2){

return obj2 – obj1;

});

console.log(arr);

//采取排序

// var arr = [0,3,4,5,15,23,5,43,34]

// //比较n-1趟

// for (var i = 0;i < arr.length – 1; i++) {

// //假定第壹个要素是最大值

// var max = 0;

// //找到了某一趟的最大值

// for (var j = 1; j < arr.length – i;j++ ) {

// if (arr[max] < arr[j]) {

// max = j;

// }

// }

// //放到适当的地方

// if (max != arr.length – i -1){

// //沟通那多个岗位的成分

// var temp = arr[max];

// arr[max] = arr[arr.length – i -1];

// arr[arr.length – i -1] = temp;

// }

// }

// console.log(arr);

//

// for循环 n-1趟{

// 借使下标为0最大 max = 0

// 循环  相比较假定的最大数量背后的数字的高低{

// 记录那趟的最大值

// }

// 查看是或不是须要沟通(数经理度 – 趟数 – 一)

// }

//4.递归算法

//递归跟函数分不开,函数内部团结调用本身,就叫递归

// function fun(){

// console.log(11);

// fun();

// }

// fun();

//递归必须有二个讲话

// var num = 0;

// function fun(){

// num++;

// console.log(num);

// if (num > 100) {

// return;

// }

// fun();

// }

// fun();

//求n!  递归也是3个算法

//规定0! = 一; 求贰个数的阶乘

// function calculate(n){

// if (n == 0) {

// return 1;

// }

// return n * calculate(n-1);

// }

// var result = calculate(5);

// console.log(result);

//伍.火速排序

//基数

//

// var arr = [4,1,6,2,3,10,9,0,19]

// //飞快排序的函数

// function quickSort(oldArray){

// if (oldArray.length <= 1) {

// return oldArray;

// }

// //取出贰个基数

// //那个基数的下标

// var privosIndex = Math.floor(oldArray.length / 2);

// //这么些基数须求从数组里面剔除出去

// var privos = oldArray.splice(privosIndex,1)[0];
//splice重临的是三个数组

// var left = [];

// var right = [];

// for (var i = 0; i < oldArray.length;i++) {

// if (oldArray[i] < privos) {

// left.push(oldArray[i]);

// }else{

// right.push(oldArray[i]);

// }

// }

// return quickSort(left).concat(privos,quickSort(right));

//

// }

// var result = quickSort(arr);

// console.log(result);

//quickSort()—数组排序

//6.贪心算法(有欠缺)

//20美元  10美元  5美元  1美元

//如何用最少数量的钞票凑成九6澳元.

//var num1 = parseInt(96 / 20);

//var num2  =parseInt((96 – num1 *4858美高梅 ,20) / 10) ;

//var num3 = parseInt((96 – num1 * 20 – num2 * 10) / 5);

//var num4 = (96 – num1 * 20 – num2 * 10 – num3 * 5) / 1;

//7.折半搜索

//折半追寻:不是排序算符,是寻找方法,能够进行折半查找的前提是其壹数组是严守原地的

var arr = [1,2,4,5,8,10,30,44,66,76];

//供给查看数字30 在arr中的下标是有点

//indexOf()

// function SWNIndexof(arr,num){

// for (var i = 0;i < arr.length;i++) {

// if (arr[i] == num) {

// return i;

// }

// }

// return -1;

// }

// var result = SWNIndexof(arr,30);

// console.log(result);

//折半搜索

var min = 0;

var max = arr.length – 1;

for (var i = 0; i < arr.length / 2; i++) {

mid = parseInt((min + max) / 2);

if (arr[mid] > 30) {

max = mid;

}else if(arr[mid] < 30){

min = mid + 1;

}else{

console.log(mid);

break;

}

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 美高梅手机版4858 版权所有