Song shuffle

I have close to 9000 songs in my iPhone music library. When I shuffle songs I invariably here the same songs day after day. Sometimes the same song is repeated within a couple of hours even though I only have it once in my library. In other words, it is not on two different albums. Likewise I may have one album of an artist and I will here 2 or 3 songs from that artist within a couple of hours. I generally do not shut my iPhone off so I should think the shuffle algorithm should provide a more random selection of songs. Is there some setup I am missing that will provide a more random shuffle and not repeat artists or songs as frequently? In my mind a shuffle algorithm should shuffle through a list without repeating a song until the list is depleted or the program is interrupted and restarted. When I say interrupted I mean the phone is turned off and restarted not the music app. I believe the music app should retain its status in the background even when not in use.