冒泡排序的实现思路和优化方案

文章目录

• • • • 写在前面
      • 基础写法
      • • 图解（白嫖的图）
        • 基础写法代码实现
      • 优化外层循环的写法
      • • 外层循环优化代码实现
      • 优化内层循环
      • • 内层循环优化代码实现

写在前面

基础写法

图解（白嫖的图）

源图片地址

基础写法代码实现

 function _funMp(_dataArr) {
  	console.time()
  	if (_dataArr instanceof Array) {
  		for (let i = 1; i < arr.length; i++) {
  			for (let j = 0; j < arr.length; j++) {
  				if (arr[j] > arr[j + 1]) {
  					let temp = arr[j]
  					arr[j] = arr[j + 1] 
  					arr[j + 1] = temp
  				}
  			}
  		}
  	} else {
  		console.info("_dataArr is not Array")
  	}
  	console.timeEnd()
  	return _dataArr
  }

至于运行的结果你们自己去看吧！这里就不贴了

优化外层循环的写法

外层循环优化代码实现

function _funMp(_dataArr) {
  	console.time()
  	let _ischange = true
  	if (_dataArr instanceof Array) {
  		for (let i = 1; i < arr.length; i++) {
  			if (!_ischange) {
  				break
  			}
  			_ischange = false
  			for (let j = 0; j < arr.length; j++) {
  				if (arr[j] > arr[j + 1]) {
  					_ischange = true
  					let temp = arr[j]
  					arr[j] = arr[j + 1] 
  					arr[j + 1] = temp
  				}
  			}
  		}
  	} else {
  		console.info("_dataArr is not Array")
  	}
  	console.timeEnd()
  	return _dataArr
  }

优化内层循环

内层循环优化代码实现

/**
 * @function _funMp 冒泡排序
 * @param {Array} _dataArr user提供的实参
 * @ischange 标记是否发生交互，如果不交互，不进行比较，优化性能
 * @_currLocal 记录临界值   将没有必要排序的后续操作停止比较，比较当前值前面的所有值
 */
function _funMp(_dataArr) {
		console.time()
		let _currLocal = _dataArr.length 
		let _ischange = true
		if (_dataArr instanceof Array) {
			for (let i = 1; i < arr.length; i++) {
				if (!_ischange) {
					break
				}
				_ischange = false
				let _currIndex = 0
				for (let j = 0; j < _currLocal; j++) {
					if (arr[j] > arr[j + 1]) {
						_ischange = true
						_currIndex = j  
						let temp = arr[j]
						arr[j] = arr[j + 1] 
						arr[j + 1] = temp
					}
				}
				_currLocal = _currIndex
			}
		} else {
			console.info("_dataArr is not Array")
		}
		console.timeEnd()
		return _dataArr
	}