It is of great significance to expand the functions of submarines by carrying underwater manipulators with a large working space. To suppress the flexible vibration of underwater manipulators, an improved sparrow search algorithm (ISSA) combining an elite strategy and a sine algorithm is proposed for the trajectory planning of underwater flexible manipulators. In this method, the vibration evaluation function is established based on the precise dynamic model of the underwater flexible manipulator and considering complex motion and vibration constraints. Simulation results show that the ISSA algorithm requires only 1/3.68 of the time of PSO. Compared to PSO, SSA and the opposition-based learning sparrow search algorithm (OBLSSA), the optimization performance is improved by 17.3%, 13.1% and 9.7%, respectively. However, because the complex dynamics model of the underwater flexible manipulator leads to large computational effort and a long optimization time, ISSA is difficult to apply directly in practice. To obtain a large number of optimization results in a shorter time, an incremental Kriging-assisted ISSA (IKA-ISSA) is proposed in this paper. Simulation results show that IKA-ISSA has good nonlinear approximation ability and the optimization time is only 3% of that of the ISSA.