文章/答案/技术大牛

发布

社区首页 >问答首页 >选择排序与插入排序。速度上的巨大差异

问选择排序与插入排序。速度上的巨大差异
EN

Stack Overflow用户

提问于 2016-06-21 10:54:14

回答 2查看 776关注 0票数 2

我知道，插入排序算法比选择排序更快。但在我看来，速度上的差异太大了。这是我的两个密码：

#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

速度不同可以吗？我知道，也许我的密码效率不高。如果这样的差别是不可以的，我该如何纠正呢？

两种代码都工作正常

选择排序

给定向量x，设初始未排序向量u等于x，初始排序向量s为长度为0的向量。
找到u的最小元素，然后从u中移除，并将其添加到s的末尾。
如果你不是空的，那就回到第二步。

插入排序

给定向量x，设初始未排序向量u等于x，初始排序向量s为长度为0的向量。
移除u的最后一个元素并将其插入到s中，这样s仍然被排序。
如果你不是空的，那就回到第二步。

sorting

回答 2

Stack Overflow用户

回答已采纳

发布于 2016-06-21 11:26:27

下面是在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循环，从而避免在while或repeat循环中进行测试。

票数 6

Stack Overflow用户

发布于 2016-06-21 12:46:31

类似的想法(由@Roland实现)也可以在JuliaLang中实现(这里包括这个选项，因为迭代在JuliaLang中通常是快速的)

srand(42)
v =  randn(10)
v1 = deepcopy(v)
function sel_sort(x)
   s = zeros(length(x))
   for i in eachindex(x)
      ind = indmin(x)
      s[i] = x[ind]
      x[ind] = maximum(x) + 1
    end
  s
end


sel_sort(v)
#10-element Array{Float64,1}:
#-2.64199
#-1.1449
#-0.556027
#-0.468606
#-0.444383
#-0.299484
# 0.0271553
# 0.156143
# 1.00331
# 1.77786

此外，我们还可以使用已经实现的排序算法。

sort(v1, alg = InsertionSort)
# 10-element Array{Float64,1}:
#-2.64199
#-1.1449
#-0.556027
#-0.468606
#-0.444383
#-0.299484
#0.0271553
#0.156143
#1.00331
#1.77786

sort!更改原始向量。

sort!(v1, alg = InsertionSort)

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/37942490

复制

相似问题

问选择排序与插入排序。速度上的巨大差异
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问选择排序与插入排序。速度上的巨大差异EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问选择排序与插入排序。速度上的巨大差异
EN