数组分区使用小结

在学习算法过程中，经常会跟数组进行打交道，其中难免会遇到数组的排序、删除等等操作，其中很多都应用了数组的分区的方法，比如：

插入排序将数组分为已排序和未排序两个区。（冒泡、选择也是如此）。
快速排序算法中的分区其实也使用了该方法，将数组分为大于分界点、小于分界点的两个区。

在刚开始接触算法的时候，总是努力的去理解算法思想、去记范式代码怎么写，后来发现学过之后还是很难写出来，归根结底还是没有掌握其方法，所以有必要进行专门的总结学习，本文主要介绍数组分区的实现和使用。

分区实现介绍

一般的，数组分区问题可以采用以下步骤来解决：

确定分区方式，已排序/未排序、保留区/删除区等等。
初始化分区长度，设置分区尾部索引，指向分区队尾的下个位置。
遍历另一个分区，将之不断交换到另一个分区中。

还是通过几个例子来具体看下如何使用。

选择排序

回顾一下之前介绍的选择排序思想，选择排序将待排序数据分为两个部分，每次遍历待排序部分，选择其中最小的元素，将之交换到已排序区的尾部，直到所有待排序区的元素处理完毕。

同样的，插入排序、冒泡排序都是基于分区思想来实现的，代码就不实现了，感兴趣可以参考之前的文章。

快速排序的分区

在快速排序中，需要将数组中选取一个分界点，然后将大于分界点的元素置于分界点左侧，大于分界点的置于其右侧，要实现此功能，可以利用分区的思想来实现。

首先将待分区的数据分为小于分界点区(A区)和待处理区(B区)，目标就是遍历待处理区，将小元素交换到 A 区。
初始时，A 区长度为0，尾部索引为 0(指向 B 区第一个元素)，B 区等于待处理数据长度。
遍历 B 区，将小于分界点的元素，交换到 A 区尾部。

代码如下：

function Partition(n,i)
  
    -- 将分区点先交换到最后，避免中间被交换
    n[i],n[#n]=n[#n],n[i]

    -- 保存小于分界点的分区的尾部索引
    local minTail = 1

    for j = 1,#n-1 do
      if n[j] < n[#n] then
        -- 小于分区点，将之交换到小分区点尾部
        n[minTail],n[j] = n[j],n[minTail]
        minTail = minTail + 1
      end
    end

    -- 最后，再将分区点交换到小元素区的尾部
    n[minTail],n[#n] = n[#n],n[minTail]
end

数组多元素删除

我们知道在删除单个数组元素时，需要将删除位置之后的元素进行移动拷贝，索引值越大需要移动的元素就越少，删除最后一个元素则不需要进行移动拷贝，根据这个思路，在删除多个元素时，可以先将所要要删除的元素交换到数组的末尾，然后进行一次性删除，避免数组的移动拷贝。

将要删除的元素置于数组末尾，这就可以采用数组分区方法来实现，步骤如下：

首先将数组分为保留区、待处理区。
初始时，保留区元素为长度为 0，尾部索引为 0（指向待处理第一个元素）。
遍历待处理区，将不满足删除条件的交换到保留区尾部，遍历完成之后，待处理区剩下的就是要删除的元素。

function RemoveAll(nums,val)
    if nums == nil or #nums == 0 then
      return 0
    end

    local endOfRemain = 1
    for i = 1,#nums do
      if nums[i] ~= val then
        nums[endOfRemain],nums[i]=nums[i],nums[endOfRemain]
        endOfRemain = endOfRemain + 1
      end
    end

    return endOfRemain - 1
end