K-Meansクラスタリングは、クラスタリングを始めるときに、ランダムにクスラターの中心を決めるところから処理を始め、観察対象をクラスターに分けていきます。
そのため、データの並び順が変わることで、最初に設定されるランダムな中心が変わってしまい、得られる結果が変わることは想定されることになります。
一方でデータの並び順による結果のばらつきを減らすためには、以下のリンクで紹介をしています「試行回数」や「反復回数」、特に「試行回数」を増やすことが有効と言えます。
ただし、それぞれの最適な回数の設定に関しては答えがあるわけではありませんので、お手持ちのデータで、それぞれの回数を増やして、ご自身で設定値を決めていただくことになります。