简单选择排序真的很简单------so:无论什么情况下时间复杂度都很高,而且还不稳定,即使有序,也还是要比较很多次。
直接插入排序 VS 简单选择排序
下表可以看到他和直接插入排序的序列特征是一样的,都是“有序序列+待排序+无序序列”,不要搞混了。
直接插入排序,是在有序序列中寻找一个合适的位置,将待排序序列插入(局部有序)
简单选择排序,是在无序序列中寻找一个合适的数据(最大或者最小)将该数据和待排序位置上的数据交换(全局有序)
编程注意事项:
1.外循环是n-1轮,剩下最后一个元素的时候就不需要比较了
2. 在无序序列中寻找最小值的办法是打擂台
void SelectSort(vector<int> a) { int k, temp; for (int i = 1; i < a.size() - 1; i++) { k = i; for (int j = i + 1; j < a.size(); j++) if (a[j] < a[k]) k = j;//用打擂台的方法找打无序序列中的最小值 if (k!=i) { temp = a[i]; a[i] = a[k]; a[k] = temp;//交换待排序位置和最小值位置上的数据 } } for (int i = 1; i < a.size(); i++)cout << a[i] << " "; }