It is definitely 'could have', 'should have', 'would have', NOT 'could of', 'should of', 'would of'. The second version is simply a mistake which has unfortunately crept into the English language and become quite common.

The same thing with apostrophes. For some reason, people continue to stick them in words when they aren't necessary. They seem to think that to make a plural version of a word, you have to put 's on the end. (like the example Floydyboy gave of Bronco's) For the life of me, I can't work out how that one started, but it's pretty common.

I certainly don't mean to be critical of anyone. Like the situation I referred to with 'there' and 'their', these are simply mistakes that have become more common over the years, because people didn't get picked up on them. I fear for what the English language is going to look like in the future after this damn text messaging craze.