algorithm - 为什么我的选择排序比插入排序慢

Question

我正在尝试编写选择排序和插入排序的实现。并使用自动生成的数组对其进行测试，并在 MAC OS 下以 u 秒的精度评估 Posix gettimeofday 的耗时。

但在大多数情况下，总的 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;
    }
}

一些测试结果:

插入排序:

Min=(-65524), index=(89660); Max=(62235), index=(23486) ShowSysTime millisecond: 1447749079447950, diff time to last record:20092583 Min=(-65524), index=(0); Max=(62235), index=(131050)

选择排序:

Min=(-65524), index=(89660); Max=(62235), index=(23486) ShowSysTime millisecond: 1447749114384115, diff time to last record:34934768 Min=(-65524), index=(0); Max=(62235), index=(131050)

插入排序来自 ITA 书，所以我怀疑我的选择排序有问题。

Answer 1

Selection sort是一种简单但效率低下的排序算法。在最坏的情况下和最好的情况下，它总是具有二次复杂度。

另一方面，insertion sort在最坏的情况下是二次的，但在最好的情况下是线性的。因此，预计在某些情况下，它的性能会优于选择排序。相反的情况会令人惊讶。