题目来自于《R语言的科学编程与仿真》第9章第7题。
显然,此时若给出一个可以返回一个向量最小元素的函数会使整个过程变得非常方便。代码如下:
#choose sort method minR<-function(x){ num<-length(x) if(num==1){return(x) }else{ x_min<-x[1] for(i in 2:length(x)){ if(x_min>x[i]){x_min<-x[i]} } return(x_min) } }#最小值函数minR() choose_sort<-function(x){ u<-x s<-c() while(length(u)>0){ u_min<-minR(u) s<-c(s,u_min) u<-u[-which(u==u_min)[1]] } return(s) } choose_sort(c(rep(1,1000),rep(0,1000),rep(2,1000)))
将一个元素a插入到一个有序向量s=(b1,...,bk)中(类似于上述第2步的过程),通常我们并不需要考虑向量中的每一个元素。实际上,如果我们从向量的尾部开始搜索,我们只要找出第一个使得a≥bi的i就可以了,然后就可以得到一个新的有序向量(b1,...,bi,a,bi+1,...,bk)。代码如下:
#insert sort method insert_sort<-function(x){ if(length(x)==1){return(x)} u<-x[-length(x)] s<-x[length(x)] while(length(u)>0){ n<-length(u) s1<-s[s-u[n]<0] s2<-s[s-u[n]>=0] s<-c(s1,u[n],s2)#保持s的顺序 u<-u[-n] } return(s) }
代码实现如下:
#bubble sort method bubble_sort<-function(x){ num<-length(x) if(num==1){return(x) }else{ finished<-FALSE while(!finished){ m<-x for(i in 1:(num-1)){ s<-x if(x[i]>x[i+1]){ s[i]<-x[i+1] s[i+1]<-x[i]} x<-s } finished<-sum(s==m)==num#判断是否不存在需要交换的元素 } return(x) } }
使用递归函数来实现快速排序法的过程,代码如下:
#quick sort method quick_sort<-function(x){ num<-length(x) if(num==0||num==1){return(x) }else{ a<-x[1] y<-x[-1] lower<-y[y<a] upper<-y[y>=a] return(c(quick_sort(lower),a,quick_sort(upper)))}#递归 }
接下来测试比较一下吧。
test<-c(rep(1,1000),rep(0,1000),rep(2,1000)) system.time(choose_sort(test)) #user system elapsed #0.39 0.00 0.39 system.time(insert_sort(test)) #user system elapsed #0.14 0.00 0.14 system.time(bubble_sort(test)) #user system elapsed #7.61 0.05 7.78 system.time(quick_sort(test)) #user system elapsed 0.07 0.00 0.08
排序结果都是对的,貌似冒泡排序写得不好,有点慢,快速排序确实是最快的。
原文:https://www.cnblogs.com/Enjoy-Respect-9527/p/13220737.html