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

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 在最坏的情况下是二次的，但在最好的情况下是线性的。因此，预计在某些情况下，它的性能会优于选择排序。相反的情况会令人惊讶。

Answer 2

在所有选择排序的情况下，将选定的值与所有其他未排序的值进行比较。因此，时间复杂度总是二次方或 n^2。

在插入排序中，在最好的情况下它是线性的（因为，要插入的值总是大于排序部分最后一个索引处的值）。在最坏的情况下它变成二次方。

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

Why my selection sort is slower than insertion sort

algorithm

sorting

insertion-sort

selection-sort