我正在尝试编写选择排序和插入排序的实现 . 并使用自动生成的数组对它们进行测试，并使用Posix gettimeofday 以u-second精度评估耗时，在 MAC OS 下 .
但在大多数情况下，总输入 65525 和 -65525 和 +65525 输入数组的范围，插入排序远比选择排序快，大约一半的时间 .
实施见下文：
void selectionSort (vector<int>& ns) {
uint_t j, minInd;
for (uint_t i = 0; i< ns.size() - 1; i++) {
j = i + 1;
minInd = i;
while (j < ns.size()) {
if(ns[j] < ns[minInd])
minInd = j;
j++;
}
if (minInd != i) {
int tmp = ns[minInd];
ns[minInd] = ns[i];
ns[i] = tmp;
}
}
}
insertSort (vector<int>& ns){
for(int i = 1; i < (int)ns.size(); i++) {
int key = ns[i];
int j = i - 1;
for( ; j >= 0; j--) {
if (ns[j] > key ) {
ns[j+1] = ns[j];
} else {
break;
}
}
ns[j+1] = key;
}
}
一些测试结果：
Insert Sort:
Min =（ - 65524），index =（89660）; Max =（62235），index =（23486）ShowSysTime millisecond：1447749079447950，diff time to last record：20092583 Min =（ - 65524），index =（0）;最大=（62235），指数=（131050）
Selection Sort:
Min =（ - 65524），index =（89660）; Max =（62235），index =（23486）ShowSysTime millisecond：1447749114384115，diff time to last record：34934768 Min =（ - 65524），index =（0）;最大=（62235），指数=（131050）
插入排序来自本书ITA，所以我怀疑我的选择排序有些不正确 .
2 回答
Selection sort是一种简单但效率低下的排序算法 . 在最坏的情况下以及在最好的情况下，它总是具有二次复杂性 .
另一方面，insertion sort在最坏情况下是二次的，但最好是线性的 . 因此，在某些情况下，预计它将比选择排序更好 . 相反，这将是令人惊讶的 .
在所有选择排序的情况下，将选定的值与所有其他未排序的值进行比较 . 因此，时间复杂度总是二次或n ^ 2 .
在插入排序中，在最好的情况下它是线性的（因为，要插入的值总是大于排序部分的最后一个索引处的值） . 在最坏的情况下它变成二次方 .