Spraying trajectory planning is a key and challenging work for intelligent spraying robot. In order to effectively fulfill spraying on complex surfaces without CAD model, a novel spraying trajectory planning method based on segmentation and trajectory sequence optimization is proposed in this paper, which is mainly composed by three steps: surface segmentation, trajectories generation and trajectories connection. In surface segmentation, a method named regional growth with minimum curvature point (RGMCP) is proposed to segment a 3D entity into different subsurfaces by taking normals and curvatures into consideration simultaneously. In trajectories generation step, an intersection of plane and point cloud (IPPC) algorithm is used to generate the optimal spraying trajectory for each segmented subsurface. Finally, for trajectories connection, a sequence optimization algorithm based on swap-evolution particles (SOSP) is proposed to connect all the subsurface trajectories as a complete spraying one in an optimum manner by regarding it as a sequence optimization problem. The effectiveness of the proposed method is validated by simulation and practical experiment simultaneously. Comparatively, our method can improve the efficiency of a spray task with 367 trajectories and 627s time-consuming to 215 trajectories and 413s, while the coating thickness variances are lowered from 51.9$um^{2}$ and 30.4$um^{2}$ to 3.64$um^{2}$ and 7.89$um^{2}$ respectively, which shows that the proposed method is more effective and can keep better coating thickness uniformity.