首页 > 代码库 > js面试常考之数组冒泡排序

js面试常考之数组冒泡排序

js的数组排序

给出一个无需的数字数组,让写冒泡排序:

解析:冒泡排序是指由第一项数与第二项的数相比较,第一项大的话两者互换位置,若第二项大的话就位置不变;

   在接着比较第二第三项,比较结果重复上一个步骤;(内for循环)

     第一次比较完后在从第二项开始在按上一环节比较;(外for循环)

        只到循环完最后第二项为止;

举例数组 arr = [3,56,4,1,34,78,23,59,66,42];

        //冒泡排序
	function arrSort(arr){
		var len = arr.length;
		for(var i = 0; i <len; i++){ //确定需要循环的次数
			for(var j = 0; j < len-1-i; j++){
				if(arr[j]>arr[j+1]){ //相邻的两项作比较
					var nu = arr[j+1];
					arr[j+1] = arr[j];
					arr[j]= nu;
				}
			}
		}
		console.log(arr);
	}
	arrSort(arr);    

 但是这个两个for循环如果数据量大了会相当消耗内存的运算;因为在每次内for循环一次完毕后都以找出一个最大数放在最后的位置,

外循环没粗循环到最后几位都要重新循环,为节省循环次数在每次内for循环最后一次换位置的地方做标记;

 2.改进冒泡排序:

       function arrSort2(arr){
		var i = arr.length-1;
		while (i>0) {
			console.log(i)//这里依次由大到小打出arr的每项数据位置索引(除去第一项0),
			var pos = 0;//每次循环将标记的位置定位0;
			for(var j=0;j<i;j++){
				if(arr[j]>arr[j+1]){
					pos=j;
					var nu = arr[j+1];
					arr[j+1] = arr[j];
					arr[j]= nu;

				  }
			  }
			  i=pos;//最后一个交换的位置;
		 }
		 console.log(arr);
	    }
	    arrSort2(arr);

  节省了一些不必要的循环,提高了运算速度!

 

js面试常考之数组冒泡排序