javascript之快速排序 ゝ一纸荒年。 2022-12-05 04:53 104阅读 0赞 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title> </head> <body> <script> /* 快速排序的中心思想: 取出数组中最靠近中间的一个值,遍历数组,用数组里面的每一个值和这个基准值进行比较, 小于这个基准值的放左边的数组,大于这个基准值的放右边的数组,递归遍历 递归遍历的结束条件:当我数组中的值只有一项的时候,原封不动的返回该数组 最后把左边的数组合并这个基准值以及右边的数组完成排序 */ const arr = [3, 4, 1, 2, 5, 7, 2, 9, 22, 1] function quickSort(arr) { // 判断arr的length是否只有1位了为结束条件 if (arr.length <= 1) return arr // 取出基准值对应的下标 const middIndex = Math.floor(arr.length / 2) // 根据下标在数组中把对应的值取出 const middValue = arr.splice(middIndex, 1)[0] // 创建左边和右边的数组 const leftArr = [], rightArr = [] // 遍历数组 for (let i = 0; i < arr.length; i++) { // 提取每一项放入一个变量,用于缓存数据,提高性能 const value = arr[i] // 判断是否小于这个基准值.小的放左边的数组,大的放右边的数组 value < middValue ? leftArr.push(value) : rightArr.push(value) } // 继续从左边的数组中取出一个中间值,在进行对比,递归 const newLeftArr = quickSort(leftArr) // 继续从右边的数组中取出一个中间值,也进行对比,递归 const newRightArr = quickSort(rightArr) // 递归完毕,进行合并返回即可 return newLeftArr.concat([middValue], newRightArr) } const newArr = quickSort(arr) console.log(newArr) </script> </body> </html>
还没有评论,来说两句吧...