选择排序与插入排序.速度差异很大

Question

我知道,插入排序算法比选择排序更快.但在我看来,速度的差异太大了.这是我的两个代码:

#Selection sort algorithm:
u <- round(runif(100,1,100))
selection_sort <- function(x){
    s <- vector('numeric')
    while(length(x) != 0){
        minimum <- x[1]
        for(i in 1:length(x)){
            ifelse(x[i]<minimum,minimum <- x[i],next())
        }
        x <- x[-match(minimum,x)]
        s <- c(s,minimum)
    }
    s
}

#Insertion sort algorithm:
u <- round(runif(100,1,100))
insertion_sort <- function(x){
    s <- vector('numeric')
    while(length(x) !=0){
        num <- x[1]
        x <- x[-match(num,x)]
        if(length(s) == 0){
            s <- c(s,num)
        } else{
            for(i in 1:length(s)){
                if(s[i]>=num){
                    s <- append(s,num,i-1)
                    break
                }
            }
            if(s[length(s)]<num){
                s <- c(s,num)
            }
        }
    }
}

我通过推荐检查了我的代码速度,microbenchmark得到了以下结果:

microbenchmark(b <- insertion_sort(u),times = 10)
expr      min       lq     mean   median       uq      max neval
2.793573 2.873704 3.159338 2.920087 3.136996 5.066089    10


microbenchmark(b <- selection_sort(u),times = 10)
expr      min       lq    mean   median       uq      max neval
21.50502 21.61436 31.7791 22.71371 40.64712 68.17705    10

这种速度差异好吗？我知道,也许我的代码效率不高.如果这种差异不好,我该如何纠正呢？

PS两个代码都正常工作

选择排序

1. 给定向量x,让初始未排序向量u等于x,并且初始排序向量s是长度为0的向量.

2. 找到你的最小元素然后从你的中删除它并将其添加到s的末尾.

3. 如果你不是空的,那就回到第2步.

插入排序

1. 给定向量x,让初始未排序向量u等于x,并且初始排序向量s是长度为0的向量.

2. 删除u的最后一个元素并将其插入s中,以便仍然对s进行排序.

3. 如果你不是空的,那就回到第2步.

Answer 1

这是在R中实现选择排序的一种(相对)有效的方法:

selection_sort <- function(x){
  s <- numeric(length(x))
  for (i in seq_len(length(x))) {
    ind <- which.min(x)
    s[i] <- x[ind]
    x[ind] <- NA
  }
  s
}

set.seed(42)
v <- rnorm(10)
selection_sort(v)
#[1] -0.56469817 -0.10612452 -0.09465904 -0.06271410  0.36312841  0.40426832  0.63286260  1.37095845  1.51152200  2.01842371

注意我如何避免调整向量的大小以及如何使用for循环,从而避免在whileor repeat循环中进行测试.