The phrase should have indicates a missed obligation or opportunity in the past. In informal speech, it is contracted to should’ve, not "should of."
You should have (should’ve) called me!
You should of called me!
I should have (should’ve) known you were lying.
I should of known you were lying.
Tom and Pauline are so selfish, they should have (should’ve) been there for you.
Tom and Pauline are so selfish, they should of been there for you.
Should have should never be written "should of." However, the latter does exist: when should is followed by an expression that begins with of.
You should, of course, compare prices.
Past: You should, of course, have compared prices.
He should, of his own will, do the right thing.
Past: He should, of his own will, have done the right thing.
The Bottom Line
The erroneous phrase "should of" likely came about from the very similar pronunciation of should’ve. Perhaps I should’ve mentioned this sooner.