js排序算法

首页 > 我的学习历程作者：月丶 2022年4月12日 12:19 星期二热度：1172° 百度已收录

时间：2022-4-12 12:19 热度：1172°

1、冒泡排序，时间复杂度O(n²)，

		
						    // 冒泡排序 
					
						    function bubbleSort (arr) {
					
						      const len = arr.length 
					
						      for (let i = 0; i < len; i++) { // 共需要排序的位数 
					
						        for (let j = 0; j < len - i - 1; j++) { // 每次遍历确定最后一位 
					
						          if (arr[j] > arr[j + 1]) {
					
						            [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
					
						          }
					
						        }
					
						      }
					
						      return arr 
					
						    }

2、快速排序，时间复杂度O(nlogⁿ)，是冒泡排序的优化版，将数组切割成左右两块，然后递归调用方法

		    // 快速排序 
	
		    function quikSort (arr) {
	
		      const len = arr.length 
	
		      if (len <= 1) return arr;
	
		      const midIdx = parseInt(len / 2)
	
		      const midVal = arr.splice(midIdx, 1)[0]
	
		      const left = [], right = [];
	
		      for (let val of arr) {
	
		        val < midVal ? left.push(val) : right.push(val)
	
		      }
	
		      return [...quikSort(left), midVal, ...quikSort(right)]
	
		    }

3、归并排序，时间复杂度O(nlogⁿ)，思想：将排序数组无限分割为左右两个数组，直到长度为1，然后开始合并相邻两个数组并排序

		    // 归并排序 
	
		    function mergeSort (arr) {
	
		      const len = arr.length 
	
		      if (len <= 1) return arr;
	
		      const midIdx = parseInt(len / 2)
	
		      const left = mergeSort(arr.slice(0, midIdx))
	
		      const right = mergeSort(arr.slice(midIdx))
	
		      return merge(left, right)
	
		    }
	
		    function merge (left, right) {
	
		      const lLen = left.length 
	
		      const rLen = right.length 
	
		      let l = 0, r = 0, res = [];
	
		      while (l < lLen && r < rLen) {
	
		        res.push(left[l] < right[r] ? left[l++] : right[r++])
	
		      }
	
		      return [...res, ...(l === lLen ? right.slice(r) : left.slice(l))]
	
		    }

4、选择排序，时间复杂度O(n²)，选出最小值，放在排好序的后面一位

		    // 选择排序 
	
		    function selectSort (arr) {
	
		      for (let i = 0, len = arr.length; i < len; i++) {
	
		        let k = i 
	
		        for (let j = i + 1; j < len; j++) {
	
		          if (arr[j] < arr[k]) k = j 
	
		        }
	
		        [arr[k], arr[i]] = [arr[i], arr[k]]
	
		      }
	
		      return arr 
	
		    }

5、插入排序，时间复杂度O(n²)，遍历值与前面排好序的值进行比较，交换，最佳情况O(n)

		    // 插入排序 
	
		    function insertSort (arr) {
	
		      for (let i = 1, len = arr.length; i < len; i++) {
	
		        let j = i 
	
		        const val = arr[j]
	
		        while (j > 0 && val < arr[j - 1]) {
	
		          [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
	
		          j--
	
		        }
	
		      }
	
		      return arr 
	
		    }

排序算法

本文作者：月丶文章标题： js排序算法
本文地址：http://silver.eleuu.com/?post=48
版权声明：若无注明，本文皆为“月丶”原创，转载请保留文章出处。

正文到此结束

vscode使用eslintrc及stylelintrc格式化代码

js创建对象与继承方式

搜索