Java教程

javascript算法系列(第三周):冒泡排序与选择排序

本文主要是介绍javascript算法系列(第三周):冒泡排序与选择排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1. 冒泡排序

冒泡排序核心思想:将第i个数依次与剩下的数进行比较,如果比后面的数大就互换位置。咕嘟咕嘟咕嘟,大的数字都给我上去。

javascript代码:

const bubble = (arr) => {
	for(let i = 0; i<arr.lenght - 1; i++) {
		for (let j = 0; j<arr.length - 1 - i; j++) {
			let c = null 
			if (arr[j] > arr[j + 1]) {
				c = arr[j]
				arr[j] = arr[j + 1]
				arr[j + 1] = c
			}
		}
	}
	return arr
}

上述代码会将每一个元素都比对一遍,如果是这样的无序列表[4,2,3,5,6,7,8,9],比对到5时,即使后面已经是有序的列表了,6,7,8也还是会与后面的元素进行比较,造成时间浪费,所以可以用个标志位来控制,比较5的时候,如果没有产生换位,则6,7,8都不用进行比较了,直接跳出循环

代码如下:

const bubble2 = (arr) => {
	for(let i = 0; i < arr.length - 1; i++) {
		let flag = false
		for (let j = 0; j < arr.length -1 -i; j++) {
			if (arr[j] > arr[j+1]) {
				flag = true
				[arr[j], arr[j + 1]] = [arr[j+1], arr[j]]
			}
		}
		if(!flag) {
			return arr
		}
	}
	return arr
}

2. 选择排序

核心思想:每次选择一个最小的,放到第i位(与第i位交换位置)
javascript代码如下

const selectSort = (arr) => {
	for(let i = 0; i < arr.length - 1; i++) {
		let min_loc = i
		for (let j = i + 1; j < arr.length; j++) {
			if (arr[j] < arr[min_loc]) {
				min_loc = j
			}
		}
		[arr[min_loc], arr[i]] = [arr[i], arr[min_loc]]
	}
	return arr
}

选择排序与冒泡排序的时间复杂度都是O( n 2 n^2 n2)

这篇关于javascript算法系列(第三周):冒泡排序与选择排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!