算法题之「移动零」

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  • 必须在原数组上操作,不能拷贝额外的数组。

  • 尽量减少操作次数。

实现

const  format = (arr) => arr.sort((a, b) => b === 0 ? -1 : 1)

优化版:

const  format = (arr, target) => arr.sort((a, b) => b === target ? -1 : 1)

本例实现使用了sort排序,sort排序如果传入的是自定义排序函数的话,其内部实现其实就是冒泡排序:
每次对比相邻的两个元素a,b,如果a>b则将a和b交换,重复这一步骤直到排序完成。
冒泡排序示意
例,将[1,4,0,2]这四个数按从小到大排序,内部是这样实现的:
image
扩展到上面format函数的实现,要实现将target移动到数组末尾的话,只需要将每个元素与target比较,如果元素与target相等,则把这个元素与target交换,这样,target最终就会被交换到数组末尾,而其他的元素位置也不会改变。