js算法之冒泡排序、快速排序和洗牌算法

随着前端的发展和进步，对前端的要求相应提高，作为前端开发不仅需要了解常规的业务逻辑，产品思维，还需要对算法有了解和思考，也是前端进阶高级的必经之路。最近的面试中经常遇到排序算法的题目，忙里偷闲整理了一下冒泡和快速排序。

冒泡排序原理

通过相邻两个元素之间的比较和交换，如果后面的比前面的小，则将小的元素排到前面, 反之排到后面，依照这个规则进行多次并且递减的迭代，直到顺序正确。

// 冒泡排序
function bubbleSort(arr){
	for(let i=arr.length-1; i>0; i--){
		for(let j=0; j arr[i]){
				[arr[i], arr[j]] = [arr[j], arr[i]]
			}
		}
	}
	return arr
}

let arr = [1,3,2,9,5,8,6,7]

bubbleSort(arr) // [1, 2, 3, 5, 6, 7, 8, 9]

快速排序原理

元素的比较和交换是从两端向中间进行的,从数组中选定一个基数，把数组中的每一项与此基数做比较，小的放入left数组，大的放入right数组,然后再采用这样的方法操作新数组。直到所有子集只剩下一个元素，排序完成。

// 快速排序
function quickSort(arr){
	// 停止递归条件
	if (arr.length <=1) {return arr}
	
	// 获取中间值索引
	var pivotIndex = Math.floor(arr.length / 2)
	
	// 利用索引取出中间值
	var pivot = arr.splice(pivotIndex, 1)[0]
	
	// 定义左右数组，比基准小的放在left数组，比基准大的放入right数组
	var left = [], right = []
	
	// 遍历数组，进行判断分配
	for (var i=0; i

洗牌算法原理

洗牌算法是将原来的数组通过random进行打散，从原数组中随机抽取一个元素放入新数组，得到一个新数组。（应用场景：音乐随机播放、棋牌类游戏洗牌）

// 洗牌算法
function shuffle(arr){
	let newArr = [], random
	
	while(arr.length >0){
        // 获取随机数
		random = Math.floor(Math.random() * arr.length)
  
        // 将随机数值放入新数组中
		newArr.push(arr[random])

        // 删除原数组值
		arr.splice(random, 1)
	}
	return newArr
}

let arr = [1,2,3,4,5,6]

shuffle(arr) // [5, 2, 3, 1, 4, 6]