常用排序算法
2021-01-20 23:14
阅读：362
语雀入口
https://www.yuque.com/along-n3gko/ezt5z9
冒泡排序
- 比较相邻的两个元素，如果前一个比后一个大，则交换位置。
- 比较完第一轮的时候，最后一个元素是最大的元素。
- 这时候最后一个元素是最大的，所以最后一个元素就不需要参与比较大小。
1 let arr = [1, 5, 8, 22, 66, 55, 0, 1, 22, 4, 88, 999]; 2 let sortArr = (arr) => { 3 let temp = null; 4 for (let i = 0; i ) { 5 for (let j = i + 1; j ) { 6 if (arr[i] > arr[j]) { 7 temp = arr[i]; 8 arr[i] = arr[j]; 9 arr[j] = temp; 10 } 11 } 12 } 13 return arr; 14 }
sort排序
- arrayObject(sortby) 默认是按照字符串UniCode编码排序
字符串排序
1 let next = [‘a‘, ‘c‘, ‘g‘, ‘h‘, ‘b‘, ‘e‘]; 2 3 next.sort(); 4 5 // [‘a‘, ‘b‘, ‘c‘, ‘e‘, ‘g‘, ‘h‘ ]
升序，sort方法接受一个函数作为参数，参数传递两个参数，即返回一个a-b小于0的值，为升序
1 let arr2 = [1, 5, 8, 22, 66, 55, 0, 1, 22, 4, 88, 999]; 2 let sortArr2 = (arr) => { 3 return arr.sort((a, b) => { 4 return a - b 5 }) 6 }
降序，sort方法接受一个函数作为参数，参数传递两个参数，即返回一个a-b大于0的值，为降序
1 let arr3 = [1, 5, 8, 22, 66, 55, 0, 1, 22, 4, 88, 999]; 2 let sortArr3 = (arr) => { 3 return arr.sort((a, b) => { 4 return b - a 5 }) 6 }
数组值为对象排序方法同上
1 let arr6 = [ 2 { ‘id‘: ‘1‘ }, 3 { ‘id‘: ‘2‘ }, 4 { ‘id‘: ‘5‘ }, 5 { ‘id‘: ‘100‘ }, 6 { ‘id‘: ‘101‘ }, 7 { ‘id‘: ‘31‘ }, 8 { ‘id‘: ‘11‘ } 9 ] 10 let sortArr6 = (arr) => { 11 return arr.sort((a, b) => { 12 return a.id - b.id 13 }) 14 }
取最小值
Math中的min方法实现
1 let arr4 = [1, 5, 8, 22, 66, 55, 1, 22, 4, 88, 999]; 2 let sortArr4 = (arr) => { 3 return Math.min(...arr); 4 }
排序法:对数组进行升序或者降序排列，然后取出数组的第一个值或者最后一个值，即可取出最小值。
假设法：假设数组的第一个值是最小值，然后数组的每个元素和第一个值做比较，如果小于第一个值，则把值传递给第一个。
1 let a = [10,2,3,4,5,6,7,8]; 2 var min = a[0]; 3 4 for(let i=0; i) { 5 a[i] null; 6 }
取最大值
Math中的max方法实现
1 let arr4 = [1, 5, 8, 22, 66, 55, 1, 22, 4, 88, 999]; 2 let sortArr4 = (arr) => { 3 return Math.max(...arr); 4 }
排序法:对数组进行升序或者降序排列，然后取出数组的第一个值或者最后一个值，即可取出最大值。
比较法：取第一个值与所有值作比较，大于所有值则返回第一个值，否者返回大于它的那个值。
1 let a = [2,10,2,3,4,5,6,7,8]; 2 const getMax = function (array){ 3 var max = undefined; 4 for (var i = 0; i i) { 5 max = max === undefined ? array[i] : (max >= array[i] ? max : array[i]); 6 } 7 return max; 8 }
乱序
使用sort方法
1 let a = [1,2,3,4,5,6,7,8]; 2 3 a.sort(() => { 4 return Math.random() - 0.5 5 })
弊端：允许多次的时候就会发现末尾大值的概率高，开头小值概率高。
原来，在Chrome v8引擎源码中，处理sort方法时，使用了插入排序和快速排序两种方案。当目标数组长度小于10时，使用插入排序；反之，使用快速排序和插入排序的混合排序。
1 const arr = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10] 2 function shuffle(arr) { 3 return arr.sort(() => (Math.random() - 0.5)) 4 } 5 6 let resultArr = Array(10).fill(0) 7 for (let i = 0; i ) { 8 // sort 会改变原数组，必须用新数组来进行乱序 9 let newArr = [].concat(arr) 10 const tmp = shuffle(newArr) 11 resultArr.forEach((item, index) => { 12 // 不能直接改变 item 的值, item += tmp[index], 因为 forEach 不会改变原数组 13 resultArr[index] += tmp[index] 14 }) 15 } 16 console.log(resultArr) 17 const average = resultArr.map(i => i/ 10000) 18 console.log(average) 19 20 // => [48544, 48860, 55333, 56927, 56797, 53396, 53790, 56762, 58967, 60624] 21 // => [4.8544, 4.886, 5.5333, 5.6927, 5.6797, 5.3396, 5.379, 5.6762, 5.8967, 6.0624]
洗牌算法
先从数组末尾开始，选取最后一个元素，与数组中随机一个位置的元素交换位置；然后在已经排好的最后一个元素以外的位置中，随机产生一个位置，让该位置元素与倒数第二个元素进行交换
1 function shuffle(a) { 2 for (let i = a.length; i; i--) { 3 let j = Math.floor(Math.random() * i); 4 [a[i - 1], a[j]] = [a[j], a[i - 1]]; 5 } 6 return a; 7 }
测试下看效果
1 const arr = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10] 2 function shuffle(a) { 3 for (let i = a.length; i; i--) { 4 let j = Math.floor(Math.random() * i); 5 [a[i - 1], a[j]] = [a[j], a[i - 1]]; 6 } 7 return a; 8 } 9 10 let resultArr = Array(10).fill(0) 11 for (let i = 0; i ) { 12 // sort 会改变原数组，必须用新数组来进行乱序 13 let newArr = [].concat(arr) 14 const tmp = shuffle(newArr) 15 resultArr.forEach((item, index) => { 16 // 不能直接改变 item 的值, item += tmp[index], 因为 forEach 不会改变原数组 17 resultArr[index] += tmp[index] 18 }) 19 } 20 console.log(resultArr) 21 const average = resultArr.map(i => i/ 10000) 22 console.log(average) 23 24 // => [55070, 54854, 54588, 55169, 55458, 54670, 55311, 54944, 55030, 54906] 25 // => [5.507, 5.4854, 5.4588, 5.5169, 5.5458, 5.467, 5.5311, 5.4944, 5.503, 5.4906]
插入排序
- 从第二位（当前元素）开始从后向前查找
- 若新元素（当前元素的前面）大于当前元素，将新元素移到下一位置
- 重复2，直到在有序区找到大于或等于新元素的位置
- 将当前元素插到上面找到的位置
- 重复2~4
1 function insertionSort(arr){ 2 var 3 len = arr.length, 4 i = 1, 5 j, 6 buffer; 7 8 for (; i ) { 9 buffer = arr[i]; 10 11 //在当前元素从后向前遍历, 12 //一旦找到比当前元素大的就进行“元素加位” 13 for (j = i - 1; j >= 0 && arr[j] > buffer; j--) { 14 arr[j+1] = arr[j]; 15 } 16 //找到的位置替换为当前元素，比它大的在上面已经“加位”了 17 arr[j+1] = buffer; 18 } 19 20 return arr; 21 }
...
评论
亲，登录后才可以留言！