前端基础排序算法

前端工程师开发常规项目时,很少会涉及排序算法的编写.即使碰到了需要进行排序的需求,使用js提供的array.sort()也能轻松搞定,很少需要编写底层的排序代码.

但有些业务场景应用了特殊的数据结构,比如需要实现链表的排序,堆的排序,此时就使用到了排序算法的思想.另外前端面试中算法相关题目偶尔出现在笔试里,要求面试者能够手写.

本文依次整理了冒泡排序、快速排序、插入排序、选择排序、奇偶排序以及二分查找法,这些算法的实现难度都不大,花些时间即能理解.

冒泡排序会重复地遍历要排序的数列,依次比较两个相邻元素的大小,如果顺序错误就将它们的值交换.冒泡排序的平均时间复杂度为O(n²).

存在数组[4,3,2,1],要求从小往大排序.

• 第一轮遍历从首元素开始,将4和3进行比较,发现4比3大,将两个元素值进行交换.数组值为[3,4,2,1].
• 遍历继续,4和2比较,发现4比2大,将两个元素值进行交换.数组值为[3,2,4,1].
• 同理4和1比较,将两个元素值进行交换.数组值为[3,2,1,4].
• 第一轮遍历的结果选出了最大值4放在了数组末尾.第二轮遍历开始,将3和2进行比较,发现3比2大,将两个元素值进行交换.数组值为[2,3,1,4].
• 遍历继续,3和1比较,将两个元素值进行交换.数组值为[2,1,3,4].
• 第一轮已经选出了最大值4放在了末尾,所以4可以不参与第二轮的比较.第二轮遍历结束,选出了次大值3放在了倒数第二个位置.
• 同理第三轮遍历选出2放在数组倒数第三个位置,3和4不参与第三轮的比较,数组值为[1,2,3,4].

function bubbleSort(list){
  
  function swap(a,b){
     let c = list[a];
     list[a] = list[b];
     list[b] = c;
  }

  for(let i = 0;i list[j+1]){
             swap(j,j+1);
        }
    }
  }

  return list;

}

console.log(bubbleSort([1,4,6,3,-1,-2,7,5,9,8,22,1,34])); // [-2, -1, 1, 1, 3, 4, 5, 6, 7, 8, 9, 22, 34]

快速排序首先取出一个基准数(通常取第一个元素),随后遍历后续所有元素,小的放基准数左边,大的放右边(如果按大到小排序则反过来).然后,再按此方法对左右两部分数据分别递归进行快速排序,以此最终实现整条数据变成有序序列.

快速排序的平均时间复杂度为O(nlogn).

存在数组[3,5,4,1,2],要求从小往大排序.

• 取出第一个元素3作为基准数,开始遍历后续元素.
• 5比3大,放到3的右边.同理4也放到3的右边.1放到3的左边.2放到3的左边.
• 经过上一轮操作后数据变成了 [1,2] 3 [5,4].现在再让两个字序列[1,2]和[5,4]分别执行前两个流程.[1,2]变成了1 [2],而[5,4]变成了[4] 5.
• 1 [2]和[4] 5两个子序列[2]和[4]都只有一个元素,可以作为递归的结束条件.
• 最后值的整合形式变成了1 [2] 3 [4] 5,实现了排序的目标.

function quickSort(list){
    function execuate(data){
        if(data.length <= 1){
            return data;
        }
        const anchor = data.shift();
        const left = [];
        const right = [];
        data.forEach((v)=>{
              if(v <= anchor){
                 left.push(v);
              }else{
                 right.push(v)
              }
        })
        return execuate(left).concat([anchor]).concat(execuate(right));
    }
    return execuate(list);
}

console.log(quickSort([2,1,6,100,-3,3,12,-9,7,2,8,3,22,4,1,6,8])); // [-2, -1, 1, 1, 3, 4, 5, 6, 7, 8, 9, 22, 34]

二分法是高效的查询算法,并不属于排序.但由于它在面试中出现的频率太高了,有必要做一次整理.

二分法只能对按照大小排好序的队列使用.以数组为例,首先寻找出数组的中间元素,如果该元素正好和目标元素相等,则跳出循环搜索过程结束,否则执行下一步.

如果目标元素大于或者小于中间元素,则只在大于或者小于中间元素的那一半区域内查找,继续重复上一步的操作.二分法的时间复杂度为O(log2n).

存在数组[3,4,5,10,23,24,30],寻找出数值5.

• 二分法首先寻找出数组的中间元素10,将其与5比较.结果比5大.
• 那么可以推测出10右边的元素都比5大,只需要关心10左边的元素.
• 10左边的元素[3,4,5]继续重复上面步骤,取出中间值4,将其与5比较.结果比5小.
• 抛弃4左边的元素,只需要关心右边.最后只剩下了一个元素5,可以作为循环的结束条件.如果和目标值相等就找到了,如果不相等说明不存在.

// 寻找目标元素的索引
function halfSelect(list,target){
    let start =  0;
    let end = list.length - 1;
    while(start<=end){
        let mid = Math.floor((start + end)/2); // 中间元素的索引
        if(list[mid] === target){
            return mid;
        }else if(list[mid] < target){
             start = mid + 1;
        }else{
            end = mid - 1;
        }
    }
    return -1;  
}


console.log(halfSelect([-1,0,1,2,5,6,7,8,10,45,47],2)); // 3

二分法在实际应用中也有很大的用武之地,比如数组list获取的数据结构如下:

list = [
   {id:12,name:"张三",age:18},
   {id:17,name:"张三",age:18},
   {id:23,name:"张三",age:18},
   {id:45,name:"张三",age:18},
   {id:62,name:"张三",age:18},
   {id:108,name:"张三",age:18},
   ...
]

假设list含有1万条数据,现在需要找出id为42576号的姓名和年龄,如果直接遍历1万条数据太过暴力,使用二分法大概最多遍历多少次呢?(面试题)

二分法的时间复杂度是O(log2n),这就意味着如果数组总长度为4,2的2次方等于4,最多只需要遍历两次.如果数据总长度为10000,2的14次方才大于10000,因此1万条数据最多需要遍历14次.

上面编写的算法是最基础的形式,二分法还有很多延伸的变形写法,可自行练习.

比如数组包含了重复元素,如halfSelect([3,4,5,5,5,5,5,5,10,23,24,30],5).那么使用上面编写的算法并不能算出5的索引为2.

另外有的需求是为了找出距离目标值大小最接近的索引,比如halfSelect([3,4,5,10,23,24,30],6),值5距离6最近,应该返回值5的索引.

插入排序的基本思想是从前往后遍历,每次遍历获取的记录插入到后面已经排好序的有序列表中,从而一个新的有序列表形成.

直接插入排序的时间复杂度为O(n²).

存在数组[5,1,7,3],按照从小往大顺序排序.

• 取出数组第二个元素1,与第一个元素5比较,1比5小,放到5的前面.数组值为[1,5,7,3].
• 此时1,5已经是排好序的子序列.遍历继续,取出第三个元素7,期望插入1,5子序列中合适的位置.由于7比1,5子序列最大的元素还要大,不做任何操作.数组值依旧为[1,5,7,3].
• 子序列变成了1,5,7.遍历继续,取出第四个元素3,期待插入子序列中的合适位置.3首先和7比较,3比7小,于是插入7的前面.数组值为[1,5,3,7].
• 3继续与5比较,3比5小,3插入5的前面.数组值为[1,3,5,7].
• 3继续与1比较,3比1大,不做任何操作.那么3最合适的插入位置处于1与5之间.

function insertSort(list){
    for(let i = 0;i0 && list[j - 1] > value){
        // 数组和链表不同,实现插入的效果比较麻烦.
        // 可以将前一个元素值赋给后一个元素,实现元素整体往右边移动一位,再将待插入的元素值交换,从而模拟了插入的效果
            list[j] = list[j-1];  
            j--;
        }
        list[j] = value;
    }
    return list;
}

console.log(insertSort([1,4,6,3,-1,-2,7,5,9,8,22,1,34])); // [-2, -1, 1, 1, 3, 4, 5, 6, 7, 8, 9, 22, 34]

选择排序是一种简单直观的排序算法.基本思想是在未排序序列中找到值最小的(如果按大到小排序反过来)元素,放到排序序列的起始位置.再从剩余未排序元素中继续寻找次小的元素,放到已排序列的第二个位置.重复上述操作,直到所有元素均排序完毕,时间复杂度为O(n²).

存在数组[5,1,7,3],按照从小往大顺序排序.

• 将数组第一个元素值5作为全局最小值存储起来,往后遍历,5比1大,全局最小值更新为1.遍历继续,1比7小,不做操作.遍历继续,1比3小,不做操作

• 第一轮遍历确定了全局最小值为1,将其放到数组的起始位置.数组变成了[1,5,7,3].

• 第二轮遍历开始,由于1已经确定为了全局最小值,不需要再参与比较.[5,7,3]重复上面两步,确定出全局最小值为3,将其与5替换,数组值变成[1,3,5,7].后续遍历继续重复上述步骤,直至完成所有排序.

function selectSort(list){
    let min_index;
    for(let i = 0;i 
奇偶排序 
奇偶排序是一种相对简单的排序算法,最初发明用于本地互连的并行计算.基本思想是奇数列排一次序,然后偶数列排一次序,接着奇数列再排一次序,然后偶数列排再一次序,重复上面过程直至整个数列有序.
 
奇偶排序的时间复杂度为O(n²).
 
算法原理 
存在数组[24,10,7,23,3,5,11],按照从小往大顺序排序.
 
先做奇排序,参与奇排序的奇数分别有24,7,3.将24与10比较,10的值小于27,将两个值进行交换.
同时7和23比较,3和5比较.第一轮奇排序交换后的数组结果为[10,24,7,23,3,5,11].
第二轮偶排序,参与偶排序的偶数分别有24,23,5.将24与7比较,7的值小,将两个值进行交换.同时23和3比较,5和11比较.第二轮偶排序交换后的数组结果为[10,7,24,3,23,5,11].
第三轮重复上述奇排序操作,数组结果为[7,10,3,24,5,23,11].
第四轮重复上述偶排序操作,数组结果为[7,3,10,5,24,11,23].
第五轮重复上述奇排序操作,数组结果为[3,7,5,10,11,24,23].
第六轮重复上述偶排序操作,数组结果为[3,5,7,10,11,23,24].
 
测试代码 
function oddEvenSort(list){
    function swap(a,b){
        let c = list[a];
        list[a] = list[b];
        list[b] = c;
    }
   //外层循环控制奇偶循环的总次数,最差的情况就是最大值在队列起始位置,要经历list.length-1次循环移到末尾
   for(let i = 0;i < list.length - 1;i++){
        let start = (i+1)%2 != 0 ? 0:1; // 奇循环起始索引为0,偶循环起始索引为1  
        while(start < list.length - 1){
           if(list[start] > list[start + 1]){
            swap(start,start+1);
           } 
           start+=2;
        }
   }
   return list;
}

console.log(oddEvenSort([24,10,7,23,-3,5,5,3,3,5,11])); // [-3, 3, 3, 5, 5, 5, 7, 10, 11, 23, 24]