几种基本的排序算法总结

准备函数

	var arr = []
	function swap(arr, a, b) {  //交换函数
		var temp = arr[a]
		arr[a] = arr[b]
		arr[b] = temp
	}
	function random_arr (){  //生成随机数组的函数
		let long = Math.floor(Math.random()*100+1)
		for(var x = 0; x < long; x++) {
			arr.push(Math.floor(Math.random()*100))
		}
		console.log(arr)
	}
	random_arr()

冒泡排序

算法思路:

遍历数组, 将相邻两个数之间两辆比较, 如果前面的数比后面的数大, 就交换位置, 然后继续将这个数跟后面相邻的数比较如果前面的数比后面的数小, 就用下一个数跟后面相邻的数继续比较

function bubble(arr) {
		for(var i = arr.length-1; i >= 0; i--) {
			for(var j = 0; j <= i; j++) {
				if(arr[j] > arr[j+1]) {
					swap(arr, j, j+1)
				}
			}
		}
		console.log(arr)
	}
bubble(arr)

选择排序

算法思路:

将第一个数与后面的没一个数进行比较, 如果有存在比第一个数小的数, 则交换位置, 然后用这个较小数继续之前的位置向后比较, 经过一圈遍历后, 数组第一位的数就是跟个数组的最小值, 然后在用第二个数跟后面的所有数一次比较进行上述操作

	function chose(arr) {
		for(var i = 0; i<arr.length; i++) {
			for(var j = i+1; j<arr.length; j++) {
				if(arr[i] > arr[j]) {
					swap(arr, i, j)
				}
			}
		}
		console.log(arr)
	}
	chose(arr)

插入排序

算法思路:

遍历整个数组, 将遍历项与其之前的项从后往前做比较, 如果他前面的数大于遍历项, 则交换位置, 直到他前面的数小于遍历项为止

	function fuck_sort(arr) {
		for(var i = 1; i < arr.length; i++) {
			for (var j = i; j > 0; j--) {
				if(arr[j]<arr[j-1]) {
					swap(arr, j, j-1)
				}
			}
		}
		console.log(arr)
	}
	fuck_sort(arr)

归并排序

算法思路:

将一个数组, 对半分割, 递归执行, 直到被分割后的数组只剩下一个数, 然后利用外排的方式将分割好的数组进行排序然后复写到原数组中

function guibing(arr,low,height) {
		var mid = low+Math.floor((height-low)/2)
		if(low === height) {
			return
		}
		guibing(arr, low, mid)
		guibing(arr, mid+1, height)
		sort(arr, low, height, mid)
	}
	function sort(arr, low, height, mid) {
		var temp = []
		var p1 = low
		var p2 = mid+1
		while (true){
			if (arr[p1] >= arr[p2]) {
				temp.push(arr[p2++])
			}else {
				temp.push(arr[p1++])
			}
			if(p1 > mid) {
				for(var j = p2; j <= height; j++) {
					temp.push(arr[j])
				}
				break
			}
			if(p2 > height) {
				for(var j = p1; j < mid+1; j++) {
					temp.push(arr[j])
				}
				break
			}
		}

		for(var i = 0; i <= temp.length-1; i++) {
			arr[i+low] = temp[i]
		}
	}
	guibing(arr, 0, arr.length-1)
	console.log(arr)

或者

function guibing2(arr) {
		if(arr.length === 1) {
			return arr
		}
		var mid = Math.floor(arr.length/2)
		var left = arr.slice(0,mid)  //slice()是数组截取方法
		var right = arr.slice(mid, arr.length)     
		return sort2(guibing2(left), guibing2(right))
	}
	function sort2(left, right) {
		var temp = []
		while(left.length > 0 && right.length > 0) {
			if(left[0] <= right[0]) {
				temp.push(left.shift())
			}else {
				temp.push(right.shift())
			}
		}
		return temp.concat(left).concat(right)   //concat()是数组拼接方法
	}
	console.log(guibing2(arr))

快速排序

算法思路:

在数组中随便找一个数做基准数, 将比这个基准数大的数放到这个数的右侧, 将比这个基准数小的数, 放到这个数的左侧, 然后在基准数的小于区和大于区继续递归执行上述操作

function range(arr, l, r) {
		var less = l - 1
		var more = r
		while( l < more ) {
			if(arr[l] > arr[r]) {
				swap(arr, l, --more)
			}else if(arr[l] < arr[r]) {
				swap(arr, l++, ++less)
			}else {
				l++
			}
		}
		swap(arr, r, more)
		return [less+1,more]
	}
	function quick(arr, l, r) {
		if(l < r) {
			var scale = range(arr, l, r)
			quick(arr, l, scale[0]-1)
			quick(arr, scale[1]+1, r)
		}
	}
	quick(arr, 0, arr.length-1)
	console.log(arr)

或者

function quick2(arr) {
		if(arr.length === 0 ) {
			return []
		}
		var left = []
		var right = []
		var middle = []
		var index =Math.round(Math.random()*(arr.length-1))
		for(var i = 0; i<arr.length; i++) {
			if(arr[i] < arr[index]) {
				left.push(arr[i])
			}else if(arr[i] > arr[index]) {
				right.push(arr[i])
			}else {
				middle.push(arr[i])
			}
		}
		return quick2(left).concat(middle).concat(quick2(right))
	}
	console.log(quick2(arr))

堆排序

算法思路:

因为堆的结构就是一个完全二叉树, 所以我们可以把数组的结构也想象成一个完全二叉树, 首先将数组变成一个大根堆, 然后将数组的第一位与数组的最后一位进行交换, 将数组的遍历范围减少一位, 此时数组的最后一位就是最大值了, 然后再将二叉树的头节点, 跟其左右两孩子最大的那个作比较, 如果孩子节点大于父节点, 就交换位置, 然后利用原来的那个父节点继续跟左右孩子作比较,比较结束后, 又形成了一个大根堆, 继续将二叉树的头结点跟二叉树的倒数第二位作交换, 将数组的遍历范围再减少一位, 重复执行上述操作.

function dui_sort(arr) {
		dui(arr)
		var long = arr.length
		swap(arr, 0, --long)
		while(long > 0) {
			var j = 0
			var left = j*2+1
			while(left<long) {
				largest = left+1<long && arr[left+1] >arr[left] ? left+1 : left
				largest = arr[largest] > arr[j] ? largest : j
				if(largest === j) {
					break
				}
				swap(arr, largest, j)
				j = largest
				left = j*2+1
			}
			swap(arr, 0, --long)
		}
	}


	function dui(arr) {
		for(var i = 0; i < arr.length; i++) {
			var j = i
			while (arr[j] > arr[Math.floor((j-1)/2)]) {
				swap(arr, j, Math.floor((j-1)/2))
				j = Math.floor((j-1)/2)
			}
		}
	}
	dui_sort(arr)
	console.log(arr)