首頁  >  文章  >  web前端  >  兩種實用的js排序演算法分析

兩種實用的js排序演算法分析

零到壹度
零到壹度原創
2018-04-09 14:57:021553瀏覽

這篇文章給大家分享的內容是兩種實用的js排序演算法分析,有著一定的參考價值,有需要的朋友可以參考一下

零:資料準備,給定數組arr=[2,5,4,1,7,3,8,6,9,0];

一:冒牌排序

1思想:冒泡排序想法:每一次比較相鄰兩個資料的大小,小的排在前面,如果前面的資料比後面的大就交換這兩個數的位置
       要實現上述規則需要用到兩層for循環,外層從第一個數到倒數第二個數,內層從外層的後面一個數到最後一個數

2特點:排序演算法的基礎。簡單實用易於理解,缺點是比較次數多,效率較低。

3實作:

var times=0;
var bubbleSort=function(arr){
	for(var i=0;i<arr.length-1;i++){
		for(var j=i+1;j<arr.length;j++){
			if(arr[i]>arr[j]){//如果前面的数据比后面的大就交换
				var temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
			}
		console.log("第"+(++times)+"次排序后:"+arr);
		}
	} 
	return arr;
}
console.log("The result is:"+bubbleSort(arr));

4效率:陣列長度10,排序次數45次。

二:快速排序

1想法:快速排序思想:先找到一個基準點(一般指數組的中部),然後數組被該基準點分為兩部分,依次與該基準點資料比較,如果比它小,放左邊;反之,放右邊。
      左右分別以空數組去儲存比較後的資料。最後遞歸執行上述操作,直到陣列長度<=1;

2特點:快速,常用。缺點是需要另外聲明兩個數組,浪費了記憶體空間資源。

3實作:

var times=0;
var quickSort=function(arr){ 
	//如果数组长度小于等于1无需判断直接返回即可
	if(arr.length<=1){
		return arr;
	}
	var midIndex=Math.floor(arr.length/2);//取基准点
	var midIndexVal=arr.splice(midIndex,1);//取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数arr[index+1]
	var left=[];//存放比基准点小的数组
	var right=[];//存放比基准点大的数组
	//遍历数组,进行判断分配
	for(var i=0;i<arr.length;i++){
		if(arr[i]<midIndexVal){
			left.push(arr[i]);//比基准点小的放在左边数组
		}
		else{
			right.push(arr[i]);//比基准点大的放在右边数组
		}
		console.log("第"+(++times)+"次排序后:"+arr);
	}
	//递归执行以上操作,对左右两个数组进行操作,直到数组长度为<=1;
	return quickSort(left).concat(midIndexVal,quickSort(right));
};
console.log(quickSort(arr));

4效率:陣列長度10,排序次數22次。

三:總結

兩種方法各有優缺點,但是這兩種方法作為程式設計師必須掌握,因為一種是最基礎的,另一種是最常用的,面試或日常都會碰到。

相關推薦:

js三大排序演算法實作程式碼

JS的十大經典演算法排序

js實作排序演算法(冒泡、選擇、插入、二分插入、快速、希.. .

以上是兩種實用的js排序演算法分析的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn