Im going to to make a few assumptions. 1) your male (or at least buy men's shoes). 2) your in the States. Adjust advise accordingly.

Your big mistake is two fold. One your buying shoes from a mall "discount" retailer and two your probably not rotating shoes.

Let's talk about that first part. Go into Nordstrom (if your not in the states look for the high end department store in your area). The reason is because the staff are trained in the product, and the return is amazing. Your going to be spending $2-400 on a pair of shoes. Talk to the sales person about what your looking for. Your goal is to not end up with a track shoe, but something made of leather with a real sole.

Secondly. You weigh a bunch compared to your shoes. Every step puts some level of stress on the sole(be it leather, rubber, foam, etc). When you lift your foot back up that stress is relaxed and quickly reapplied. Over time this can wear down your shoes. The trick here is to rotate your shoes so each pair has a day or two to "rest" before usage. This (In conjunction with buying good quality shoes) will result in you needing a new pair closer to every 5 years (longer if you get the soles replaced).