"should of" is colloquial writing and is a corruption of "should have" in fast speech.
In answer to your question, "should have" is the correct form.
Ex: He would of gone had he had the money. NOT
He would have gone had he had the money. OK
He would've gone had he had the money. OK because "would've" is a contraction of "would have."
If you sound the two words out phonetically, you can see the provenance of the "of."