Which version of Safari are you using? In older versions, you used to have the "Reset Safari" option, which Apple chose to remove in favor of the more limited "Clear History and Website Data" option. In most cases, "Reset Safari" would do the trick, but now it's more complicated.
If you're using Safari 8 or newer, I would recommend that you use the "Clear History and Website Data" option from the Safari menu, make sure you delete all history when prompted. Also, go into Preferences, General button and ensure that you have your Homepage set to the page of your preference, not some Adware site. Finally, download Bitdefender (free, Mac App Store) and have it do a quick scan to ensure there are no Adware bots that are resetting your home page or default search provider.