关于前端工程师:面试官问你工作多久了怎么还不会冒泡排序

前言

大家好，我是梁木由，一个有想头的前端，明天温习到了如何排序，那么给大家来分享下，冒泡排序与疾速排序

冒泡排序

概念

从第一个元素开始，把以后元素与下一个元素进行比拟，元素大的往后排，小的往前排，顺次比拟到最初一个元素，进行替换地位。

实现步骤

• 先遍历一共有多少个数须要跟其它数进行比拟
• 再遍历每个数须要跟其它数比拟多少次
• 如果前一个数小于后一个数，就替换地位

function bubbleSort(arr){
  let len = arr.length;
  // 遍历多少个数跟其它数进行比拟
  for(let i = 0; i < len; i++){
    // 再遍历每个数须要跟其它数比拟多少次
    for(let j = 0; j < len - i - 1; j++){
      // 如过前一个数小于后一个数
      if(arr[j+1] < arr[j]){
        // 替换地位
        [arr[j+1],arr[j]] = [arr[j],arr[j+1]]
      }
    }
  }
  return arr
}
​
// 验证
let arr = [1,44,6,77,3,7,99,12]
console.log(bubbleSort(arr))
// [1, 3, 6, 7, 12, 44, 77, 99]

疾速排序

概念

在数据集之中，找一个基准点，建设两个数组，别离存储右边和左边的数组，利用递归进行下次比拟。

实现步骤

• 先做边界解决
• 定一个左右两侧的数组
• 查找数组两头地位，并获取两头地位这个数值，并在原数组删除它
• 遍历数组，判断以后项与两头地位数值的大小，大的 push 到右侧数组，小的 push 到左侧数组
• 再对两侧数组进行递归，拼接两头数值

function quickSort(arr){
  // 解决边界
  if(!Array.isArray(arr)) return arr;
  if(arr.length <=1) return arr;
  
  // 定义左右两侧的数组
  const leftArr = [],
        rightArr = [];
  
  // 查找数组两头地位，并获取两头地位这个数值，并在原数组删除它
  const midValue = arr.splice(Math.ceil(arr.length/2),1)[0];
  
  // 遍历数组，判断以后项与两头地位数值的大小，大的 push 到右侧数组，小的 push 到左侧数组
  for(let i = 0; i < arr.length; i++){if(arr[i] > midValue){rightArr.push(arr[i])
    }else{leftArr.push(arr[i])
    }
  }
  
  // 再对两侧数组进行递归，拼接两头数值
  return [...quickSort(leftArr), midValue,...quickSort(rightArr)]
}
​
// 验证
let arr = [1,44,6,77,3,7,99,12]
console.log(quickSort(arr))// [1, 3, 6, 7, 12, 44, 77, 99]