During migration through the female reproductive tract, sperm undergo physiological changes known as capacitation, including a motility transition termed hyperactivation. Hyperactivation is essential for various aspects of fertilization, particularly effective migration within the tract. However, how hyperactivation facilitates this migration remains elusive. Here, we profiled bull sperm hyperactivation and swimming in Newtonian and complex fluids, using microfluidic surfaces to mimic confinement of the tract. We identified three swim gaits: wandering (persistent random walks), circling, and an intriguing circling-and-wandering mode marked by stochastic transitions between the two. All gaits exhibit diffusive behavior over long time scales, with wandering showing a tenfold higher diffusivity than circling, and the effective diffusivity of circling-and-wandering falling in between. We found that while wandering sperm scatter from convex and concave surfaces, circling sperm become trapped around pillars, highlighting a distinctive feature of each phase. Additionally, stochastic simulations of active transport in porous media showed that as the geometrical complexity of the environment increases, circling-and-wandering outperforms either motility alone in spreading through the media. Our findings suggest that wandering may broaden the search landscape, while circling could help maintain local focus. Therefore, the combined circling-and-wandering swimming behavior might provide a flexible mechanism for modulating motility and facilitating migration in complex environments. Our results may have implications for understanding the physical aspects of sperm migration in the female reproductive tract.