移动零

本文介绍了移动零问题的两种解法：冒泡排序思路和快速排序双指针思路，并分析了各自的优缺点。

Leetcode 双指针 Python 排序算法

题目

(https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked)

解法一

思路

参考冒泡排序，将0逐渐移动到最右边

答案

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums) - 1, -1, -1):
            for j in range(i):
                if nums[j] == 0:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
提交超时了，但是感觉还能凹一下

解法二

思路

解法一参考的冒牌排序，而常见的排序算法中时间复杂度低的是快速排序。因此可以以快速排序的思路来做。

快速排序的两个核心思路分别是双指针加递归，递归主要用于对子数组的排序，在本题用应该使用不上。

而在快速排序的双指针，主要是用于在右子数组中寻找比基准小的数，在左子数组中寻找比基准大的数，最后将两者交换，直至左子数组全是比基准小的数，右子数组全是比基准大的数。

在本题中，可简化为，指针i之前的全为排好序的，指针j从i到数组结尾遍历去寻不为0的数，然后交换，排好序的加一即i++

答案

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = 0
        for j in range(i, len(nums)):
            if nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
                i+=1

收获

复习了一下快速排序以及分治思想
类排序算法都可以排好序和未排好分为两部分来处理