R 中的选择/插入/刷新/快速排序
最编程
2024-04-19 08:08:09
...
题目来自于《R语言的科学编程与仿真》第9章第7题。
- 选择排序法。这是一种最简单,但是效率最低的排序算法。算法步骤如下:
- 对于给定的一个向量x,令最初的未排序向量u等于x,并且最初的已排序向量s的长度为0。
- 寻找u中的最小元素,然后把它从u中移出来,放在向量s的最末端。
- 重复执行第2步,直至u中没有元素为止。
显然,此时若给出一个可以返回一个向量最小元素的函数会使整个过程变得非常方便。代码如下:
#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)))
- 插入排序法。与选择排序法类似,算法步骤如下:
- 对于给定的一个向量x,令最初的未排序向量u等于x,并且最初的已排序向量s的长度为0。
- 将u中的最后一个元素插入s中,并且保持s是有序的。
- 重复执行第2步,直至u中没有元素为止。
将一个元素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) }
- 冒泡排序法。冒泡排序法和选择排序法与插入排序法还是有很大区别的。它的执行方式是不断地对向量x=(a1,...,an)相邻元素进行比较,具体步骤如下:
- 对于i=1,...,n-1,如果ai>ai+1,则交换ai和ai+1的位置。
- 重复执行第1步,直到没有需要交换的为止。
代码实现如下:
#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) } }
- 快速排序法。快速排序法可以说是目前(平均)排序最快的算法之一,也是被广为使用的一种排序方法。这个方法最初于1960年由C.A.R.霍尔提出,其采取的是“分治算法”策略:使用递归算法的思想将一个问题分解成两个小(容易)的问题来处理。给定一个向量x=(a1,...,an),算法的具体步骤如下:
- 如果n=0或者n=1,则对x的排序完成,计算结束。
- 如果n>1,则将向量(a1,...,an)分割成lower和upper两个子向量,其中lower包含x中所有小于a1的元素,upper包含x中所有大于a1的元素(等于a1的元素放在lower或upper中均可)。
- 对lower和upper进行排序。记这两个子向量排好序后的向量分别为(b1,...,bi)和(c1,...,cj),则向量x排好序后的结果为(b1,...,bi,a,c1,...,cj)。
使用递归函数来实现快速排序法的过程,代码如下:
#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
推荐阅读
-
R 中的选择/插入/刷新/快速排序
-
气泡排序、插入排序、选择排序和快速排序的原理
-
排序算法的图形比较:快速排序、插入排序、选择排序、冒泡排序
-
气泡排序、选择排序、插入排序、山排序、堆排序、快速排序的递归版本。(可直接使用,懒人必备)。
-
[排序算法] 四种排序算法的理论基础 + Python 代码:气泡排序、插入排序、选择排序、快速排序 - 插入排序(稳定排序)
-
MAX_LEN) {
int pivot = partition(arr, left, right);
quicksort_optimized(arr, left, pivot - 1);
quicksort_optimized(arr, pivot + 1, right);
} else {
// 使用插入排序处理小数组
}
}
```
- 合并相同值进行分割:在每次划分后,我们将与枢轴相等的元素聚集在一起,以降低后续迭代中的重复处理。例如:
原序列: 1 4 6 7 6 6 7 6 8 6
- 选取枢轴(6)并划分:1 4 6 7 1 6 7 6 8 6
- 划分结果(未处理相等项):1 4 6 6 7 6 7 6 8 6
- 处理相等项后的划分结果:1 4 6 6 6 6 7 8 7
- 下次划分得到的子序列:1 4 和 7 8 7
通过这样的优化,我们可以明显减少迭代次数,从而提高排序效率。">
改进版快速排序:针对部分有序列的策略与优化技巧" - 随机选枢轴:当数据部分有序时,传统快速排序通过固定枢轴可能导致效率低下。为此,我们采用随机选取枢轴的方法,代码如下: ```c int SelectPivotRandom(int arr[], int low, int high) { srand(time(0)); int pivotPos = (rand() % (high - low)) + low; swap(arr[pivotPos], arr[low]); return arr[low]; } ``` - 优化小数组交换:针对小且部分有序的数组,快速排序不如插入排序高效。因此,当待排序序列长度小于等于10时,我们会切换至插入排序: ```c #define MAX_LEN 10 void quicksort_optimized(int *arr, int left, int right) { int length = right - left; if (length > MAX_LEN) { int pivot = partition(arr, left, right); quicksort_optimized(arr, left, pivot - 1); quicksort_optimized(arr, pivot + 1, right); } else { // 使用插入排序处理小数组 } } ``` - 合并相同值进行分割:在每次划分后,我们将与枢轴相等的元素聚集在一起,以降低后续迭代中的重复处理。例如: 原序列: 1 4 6 7 6 6 7 6 8 6 - 选取枢轴(6)并划分:1 4 6 7 1 6 7 6 8 6 - 划分结果(未处理相等项):1 4 6 6 7 6 7 6 8 6 - 处理相等项后的划分结果:1 4 6 6 6 6 7 8 7 - 下次划分得到的子序列:1 4 和 7 8 7 通过这样的优化,我们可以明显减少迭代次数,从而提高排序效率。