For the whole process trajectory planning of UAV formation performing tasks, a UAV formation trajectory planning algorithm based on the multi-step particle swarm optimization(PSO) algorithm is proposed. First, the UAV model and the mission strategy model are established. The whole process of the formation performing tasks is divided into 5 phases: formation forming, task execution, returning, dismissing and UAV landing, and the flight strategies of different phases are designed. Second, multi-class and multi-layer optimization indexes are designed and a multi-step PSO algorithm is used to optimize waypoints according to different terminal constraints. Model predictive control(MPC) is introduced for rolling optimization of waypoints, and a route planning method suitable for different phases that can strictly meet the constraints is obtained. Then, a rotating coordinate system is established to convert the waypoint information into the ideal heading and altitude information in the formation control law, and the formation control algorithm that can pass waypoints is obtained. Finally, the formation control algorithm is used to execute the waypoints given by the route planning method to generate the trajectory, and the formation trajectory planning algorithm is obtained. The simulation results show that the proposed planning method with good generality is more suitable for formation flight than the traditional method, and it can plan a smooth trajectory of the whole process for formation to execute missions.