Full-waveform inversion (FWI) is a highly nonlinear and nonconvex problem. To mitigate the dependence of FWI on the quality of starting model and on the low frequencies in the data, we apply the gradient sampling algorithm (GSA) introduced for nonsmooth, nonconvex optimization problems to FWI. The search space is hugely expanded to have more freedom to accommodate large velocity errors in the starting model. The original implementation of GSA requires explicit calculation of the gradient at each sampled vector, which is prohibitively expensive. Based on the observation that a slight perturbation in the velocity model causes a small spatial shift of the wavefield, we have approximated the sampled gradients by crosscorrelating the space-shifted source- and receiver-side wavefields. Theoretical derivation suggests that the two wavefields should be shifted in the same direction to obtain reasonable low-wavenumber updates. The final descent search direction is obtained by summing all the shifted gradients. For practical implementation, we only take one random space shift at each time step during the gradient calculation. This simplification provides an efficient realization in which the computational costs and memory requirements are the same as conventional FWI. Multiple numerical examples demonstrate that the proposed method alleviates the cycle-skipping problem of conventional FWI when starting from very crude initial velocity models without low-frequency data.