js中数组排序(冒泡、快速、插入)

我就是我 2022-12-05 10:16 206阅读 0赞

1.冒泡排序法

将数组中的相邻两个元素进行比较,将比较大(较小)的数通过两两比较移动到数组末尾(开始),执行一遍内层循环,确定一个最大(最小)的数,外层循环从数组末尾(开始)遍历到开始(末尾)
在这里插入图片描述

  1. function MaoPaoSort(arr){
  2. for(var i = 0;i<arr.length-1;i++) {
  3. for(var j = 0;j<arr.length-i-1;j++){
  4. if(arr[j]>arr[j+1]){
  5. //把大的数字放到后面
  6. var str = arr[j];
  7. arr[j] = arr[j+1];
  8. arr[j+1] = str;
  9. }
  10. }
  11. }
  12. }
  13. var arr = [3,5,1,2,7,8,4,5,3,4];
  14. //console.log(arr);[3,5,1,2,7,8,4,5,3,4];
  15. MaoPaoSort(arr);
  16. //console.log(arr);[1, 2, 3, 3, 4, 4, 5, 5, 7, 8]

2. 插入排序法(插队排序)

将要排序的数组分成两部分,每次从后面的部分取出索引最小的元素插入到前一部分的适当位置

在这里插入图片描述

  • 从第一个元素开始,该元素可以认为已经被排序;
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • 将新元素插入到该位置后;
  • 重复步骤2~5。

    function InsertSort(arr) {
    let len = arr.length;
    let preIndex, current;
    for (let i = 1; i < len; i++) {

    1. preIndex = i - 1;
    2. current = arr[i];
    3. while (preIndex >= 0 && current < arr[preIndex]) {
    4. arr[preIndex + 1] = arr[preIndex];
    5. preIndex--;
    6. }
    7. arr[preIndex + 1] = current;

    }
    return arr;
    }

  1. var arr = [3,5,7,1,4,56,12,78,25,0,9,8,42,37];
  2. InsertSort(arr);

3.快速排序

在看完上面的东西之后,不知道大家有没有发现在实际的工作中如果数据量过大,数组比较复杂,通过两次遍历,同时会带来性能上的问题,不用慌,我们还可以用快速排序的方法进行解决,快速排序对冒泡排序的一种改进

实现思路是,将一个数组的排序问题看成是两个小数组的排序问题,以一个数为基准(中间的数),比基准小的放到左边,比基准大的放到右边,而每个小的数组又可以继续看成更小的两个数组,一直递归下去,直到数组长度大小最大为2。

  1. function quickSort(arr){
  2. //如果数组长度小于1,没必要排序,直接返回
  3. if(arr.length<=1) return arr;
  4. //pivot 基准索引,长度的一半
  5. let pivotIndex = Math.floor(arr.length/2);//奇数项向下取整
  6. //找到基准,把基准项从原数组删除
  7. let pivot = arr.splice(pivotIndex,1)[0];
  8. //定义左右数组
  9. let left = [];
  10. let right = [];
  11. //把比基准小的放left,大的放right
  12. arr.forEach(element => {
  13. if(element<pivot){
  14. left.push(element)
  15. }else{
  16. right.push(element)
  17. }
  18. });
  19. return quickSort(left).concat([pivot],quickSort(right))
  20. }
  21.  
  22. var arr=[4,56,3,67,44,5,66];
  23. console.log(quickSort(arr));//[3, 4, 5, 44, 56, 66, 67]

在这里插入图片描述

发表评论

表情:
评论列表 (有 0 条评论,206人围观)

还没有评论,来说两句吧...

相关阅读

    相关 js冒泡快速排序

    冒泡排序: 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大