实验2：编程语言认知
一：实验目的
1：强化对编译器两端的认识。
2：了解语言多样性。
3：了解语言特性对语言实现的影响。
二：实验环境
自选多个不同的语言环境。
| 编号 | 所用语言 | 程序编写的软件环境 |
| 1 | C | Dev-C++ |
| 2 | C++ | Dev-C++ |
| 3 | Python | Visual Studio Code |
| 4 | Java | IntelliJ IDEA Community |
| 5 | R | RStudio |
| 6 | JavaScript | Visual Studio Code |
| 7 | Matlab | MATLAB R2022a |
三：实验要求
使用三种以上（如C、C++、C#、Python、Java）的不同语言实现：对数组中的数据快速排序，并对语言易用性、程序性能进行比较分析，撰写实验报告。
四：算法思想
快速排序的基本思想是：通过一趟排序将待排数组分割成独立的两部分，其中一部分数组的关键字均比另一部分数组的关键字小，则可分别对这两部分数组进行排序，以达到整个数组排序的目的。
五：实验过程
（1）写出快速排序程序流程图。
（2）选择三种以上语言环境。
（3）编写快速排序程序。
（4）结果验证截图。
（5）撰写实验报告。
六：实验内容
1：快排的程序流程图
快排算法的主要思想是：先从数组中取出一个基准数(一般情况下取左边第一个数)，通过一趟排序将要排序的数组划分为独立的两个部分，要求是一趟排序完成后，基准数的左边的数都小于基准数，基准数的右边的数都大于基准数。然后按照此方法对这两部分数组分别进行快速排序，整个排序过程用递归进行，直至整个数组变成有序数组。
根据算法思想，可以画出快排的程序流程图。
主函数（main、quicksort）部分如下图所示。
分块函数（part）部分如下图所示。
2：各类编程语言的快排代码与结果
【0】测试用例设计
在本次实验中，测试用例采用1到10000降序排列的整数。即数组的第一项为10000，相邻的前后两个项的间隔为1，数组的最后一项为1。
为了防止程序的偶然性，本次实验将在每种语言编写的程序下运行5次，并计算5次运行所消耗的时间，取其平均值作为该编程语言在快速排序算法上的程序性能指标。
【1】C语言
（1）程序快排代码
本次实验在C语言上编写的快排代码如下表所示。
| #include <stdio.h> #include <malloc.h> #include <time.h> // segment-each-part function int part(int *arr, int low, int high){ int t=arr[high],i=low-1,j;
for(j=low;j<high;j++){ if(arr[j]<=t){ i++; int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } }
int swap=arr[i+1]; arr[i+1]=arr[high]; arr[high]=swap; return i+1; } // quick-sort function void QuickSort(int *arr, int low, int high){ if(low<high){ int mid=part(arr,low,high); QuickSort(arr,low,mid-1); QuickSort(arr,mid+1,high); } } int main(){ // input part int n=10000; // printf("please input total number: "); // scanf("%d",&n); int *arr=(int*)malloc(sizeof(int)*n); int i=0; // printf("please input each figure: "); for(i=0;i<n;i++){ // scanf("%d",&arr[i]); arr[i]=10000-i; }
/* printf("the test example of array is as follows: \n"); for(i=0;i<n;i++){ // scanf("%d",&arr[i]); printf("%d ",arr[i]); } printf("\n"); */
// quick sort & timing clock_t start=clock(); QuickSort(arr,0,n-1); clock_t end=clock();
// output part printf("the result after quick sort is as follows: \n"); for(i=0;i<n;i++){ printf("%d ",arr[i]); } printf("\n\n\n");
double period=((double)(end-start))/CLOCKS_PER_SEC; printf("the calculation time is: %f \n", period); return 0; } |
（2）程序测试结果
测试用例在执行文件下的5次运行结果如下图所示。
【2】C++
（1）程序快排代码
本次实验在C++上编写的快排代码如下表所示。
| #include <iostream> #include <vector> #include <ctime> using namespace std; // segment-each-part function int part(vector<int>& arr, int low, int high) { int t=arr[high],i=low-1,j; for(j=low;j<high;j++){ if (arr[j]<=t){ i++; int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } int swap=arr[i + 1]; arr[i+1]=arr[high]; arr[high]=swap; return i+1; } // quick-sort function void QuickSort(vector<int>& arr, int low, int high){ if(low<high) { int mid=part(arr,low,high); QuickSort(arr,low,mid-1); QuickSort(arr,mid+1,high); } } int main(){ int n=10000; vector<int> arr(n); for(int i=0;i<n;i++){ arr[i]=10000-i; } // quick sort & timing clock_t start=clock(); QuickSort(arr,0,n-1); clock_t end=clock(); // output part cout << "the result after quick sort is as follows: \n"; for(int i=0;i<n;i++){ cout<<arr[i]<<" "; } cout<<endl<<endl<<endl; double period=((double)(end-start))/CLOCKS_PER_SEC; cout<<"the calculation time is: "<<period; return 0; } |
（2）程序测试结果
测试用例在执行文件下的5次运行结果如下图所示。
【3】Python
（1）程序快排代码
本次实验在Python上编写的快排代码如下表所示。
| import time # segment-each-part function def part(arr, low, high): t = arr[high] i = low - 1 for j in range(low, high): if arr[j] <= t: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 # quick-sort function def quick_sort(arr, low, high): stack = [(low, high)] while stack: low, high = stack.pop() if low < high: mid = part(arr, low, high) stack.append((low, mid - 1)) stack.append((mid + 1, high)) if __name__ == "__main__": n = 10000 arr = [10000 - i for i in range(n)] # quick sort & timing start_time = time.time() quick_sort(arr, 0, n - 1) end_time = time.time() # output part print("the result after quick sort is as follows: ") print(*arr) period = end_time - start_time print("the calculation time is:", period, "seconds") |
（2）程序测试结果
测试用例在执行文件下的5次运行结果如下图所示。
【4】Java
（1）程序快排代码
本次实验在Java上编写的快排代码如下表所示。
| import java.util.Arrays; |
（2）程序测试结果
测试用例在执行文件下的5次运行结果如下图所示。
【5】R
（1）程序快排代码
本次实验在R上编写的快排代码如下表所示。
| partition <- function(arr, low, high) { pivot <- arr[high] i <- low - 1
for (j in low:(high-1)) { if (arr[j] <= pivot) { i <- i + 1 temp <- arr[i] arr[i] <- arr[j] arr[j] <- temp } }
temp <- arr[i + 1] arr[i + 1] <- arr[high] arr[high] <- temp
return(list('i' = i + 1, 'arr' = arr)) } quick_sort <- function(arr, low, high) { stack <- list(c(low, high))
while (length(stack) > 0) { indices <- stack[[length(stack)]] stack <- stack[-length(stack)] low <- indices[1] high <- indices[2]
if (low < high) { res <- partition(arr, low, high) mid <- res$i arr <- res$arr stack <- c(stack, list(c(low, mid - 1)), list(c(mid + 1, high))) } }
return(arr) } # Main block n <- 10000 arr <- n:1 # Timing the quick sort start_time <- Sys.time() arr <- quick_sort(arr, 1, n) # Ensure arr is reassigned with the sorted array end_time <- Sys.time() # Output cat("The result after quick sort is as follows (first 10 elements shown for brevity):\n") print(arr) period <- end_time - start_time cat("The calculation time is:", period) |
（2）程序测试结果
测试用例在执行文件下的5次运行结果如下图所示。
【6】JavaScript
（1）程序快排代码
本次实验在JavaScript上编写的快排代码如下表所示。
| <!DOCTYPE html> <html> <head> <title>Quick Sort JavaScript</title> </head> <body> <script> function partition(arr, low, high) { let pivot = arr[high]; let i = low - 1; for (let j = low; j < high; j++) { if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; // Swapping using destructuring } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Swap pivot into the correct place return i + 1; } function quickSort(arr, low, high) { let stack = [[low, high]]; while (stack.length > 0) { const [start, end] = stack.pop(); if (start < end) { const mid = partition(arr, start, end); stack.push([start, mid - 1]); stack.push([mid + 1, end]); } } } function main() { const n = 10000; const arr = Array.from({ length: n }, (_, index) => 10000 - index); const startTime = new Date().getTime(); // Start timing quickSort(arr, 0, n - 1); const endTime = new Date().getTime(); // End timing // Output part console.log("The result after quick sort is as follows: "); console.log(arr.join(" ")); // Joining array elements for cleaner output const period = (endTime - startTime) / 1000; // Convert milliseconds to seconds console.log("The calculation time is:", period, "seconds"); } main(); </script> </body> </html> |
（2）程序测试结果
测试用例在执行文件下的5次运行结果如下图所示。
【7】Matlab
（1）程序快排代码
本次实验在Matlab上编写的快排代码如下表所示。
| function QuickSortDemo % 主函数入口 n = 10000; arr = 10000:-1:1; % 生成一个从10000递减到1的数组 tic; % 开始计时 arr = QuickSort(arr, 1, n); % 快速排序 toc; % 结束计时并输出所用时间 % 输出排序后的数组 fprintf('The result after quick sort is as follows:\n'); disp(arr(1:100)); % 仅展示前100个元素以节省空间 end function arr = QuickSort(arr, low, high) % 快速排序函数 if low < high [arr, mid] = Partition(arr, low, high); % 分区操作 arr = QuickSort(arr, low, mid-1); % 递归排序左半部分 arr = QuickSort(arr, mid+1, high); % 递归排序右半部分 end end function [arr, mid] = Partition(arr, low, high) % 分区函数 pivot = arr(high); i = low - 1; for j = low:high-1 if arr(j) <= pivot i = i + 1; temp = arr(i); arr(i) = arr(j); arr(j) = temp; % 交换元素 end end % 把基准值换到中间 temp = arr(i+1); arr(i+1) = arr(high); arr(high) = temp; mid = i + 1; end |
（2）程序测试结果
测试用例在执行文件下的5次运行结果如下图所示。
3：编程语言对比分析
（1）语言易用性
编程语言的易用性可以根据以下几个维度来进行评估：语法简洁性、内置函数库的支持、内存管理、类型系统、开发和调试工具的可用性。
在本次实验快速排序算法的实现中，各类编程语言的可用性对比，如下表所示。
| 编程语言 | 易用性等级 | 原因 |
| C | 较低 | C语言需要手动管理数组的内存，且语法较为繁琐。实现快排时，指针操作和手动交换元素增加了实现难度。 |
| C++ | 中等 | C++在C的基础上增加了类、模板、STL等面向对象和泛型编程的特性，使得编写快排更灵活。 |
| Python | 较高 | Python的简洁语法、动态类型系统和丰富的标准库保证了实现过程非常简单快捷。 |
| Java | 中等 | Java提供了强类型系统和丰富的标准库，但语法更繁琐。实现快排需要明确处理数组索引和递归逻辑。 |
| R | 较低 | R语言更多地依赖于循环和条件判断，与R擅长的数据操作范式略有不同。 |
| JavaScript | 中等 | JavaScript的动态类型和灵活的数组操作使得实现快排较为简单，但递归深度有一定限制。 |
| Matlab | 较高 | Matlab对递归有很好的支持，用户不需要担心递归导致的栈溢出问题，同时数组的索引、切片和赋值操作非常简洁明了。 |
综上所述，在编程语言的易用性方面，Python和Matlab位于第一梯队，C++、Java和JavaScript位于第二梯队，C和R位于第三梯队。
（2）程序性能
统计各类编程语言在相同复杂度问题下的快速排序结果，如下表所示。其中，时间的单位均为秒（second）。
| 编程语言 | 测试1时间 | 测试2时间 | 测试3时间 | 测试4时间 | 测试5时间 | 平均耗时 |
| C | 0.121 | 0.126 | 0.122 | 0.123 | 0.12 | 0.1224 |
| C++ | 0.263 | 0.268 | 0.269 | 0.275 | 0.278 | 0.2706 |
| Python | 3.17 | 3.346 | 3.147 | 3.32 | 3.2 | 3.2366 |
| Java | 0.0373 | 0.0368 | 0.0374 | 0.0349 | 0.0384 | 0.03696 |
| R | 4.859 | 4.984 | 4.873 | 4.867 | 4.921 | 4.9008 |
| JavaScript | 0.078 | 0.091 | 0.08 | 0.078 | 0.082 | 0.0818 |
| Matlab | 0.241 | 0.111 | 0.101 | 0.115 | 0.101 | 0.1338 |
由上表可知，从平均耗时的角度来看，各个编程语言从快到慢的排序依次为：Java、JavaScript、C、Matlab、C++、Python、R。
由此可知，各个编程语言在执行相同复杂度的快速排序问题时，性能表现存在显著差异。这些差异主要受到语言的运行环境、编译器优化水平、以及语言本身的设计方法等因素的影响。
七：心得与思考
1：在Python中，递归调用次数超过默认的最大递归深度限制，会导致递归错误（RecursionError），显示如下报错。
| File "c:\Users\86158\Desktop\import time.py", line 19, in quick_sort mid = part(arr, low, high) ^^^^^^^^^^^^^^^^^^^^ RecursionError: maximum recursion depth exceeded. |
为了解决这个问题，可以使用以下两种方法。（1）增加递归深度限制：通过 sys.setrecursionlimit() 函数来增加递归深度限制，但可能会导致堆栈溢出。（2）改用非递归实现：使用例如堆栈等方法来模拟递归的调用过程，避免递归深度限制的问题，使程序更加灵活和可控。
2：在Java中，公共类的类名必须与文件名完全相同（包括大小写）。否则会出现如下报错。
| User PS C:\Users\86158\IdeaProjects\untitled1> javac sort.java sort.java:3: 错误: 类 QuickSort 是公共的, 应在名为 QuickSort.java 的文件中声明 public class QuickSort { ^ 1 个错误 |
3：Java文件的运行需要先安装JDK（Java开发工具包），然后通过javac指令编译Java文件，最后通过java指令运行Java程序。
4：在Dev环境下中的C语言，使用for循环的时候不能和C++一样，将迭代变量第一次定义在循环内部，而需要写在循环外面。示例如下。
| C语言写法 |
| int i; for(i=0;i<100;i++) |
| C++写法 |
| for(int i=0;i<100;i++) |
5：不是所有编程语言都能在大量数据的情况下实现递归。在本次实验中，C语言、C++、Java、Matlab可以实现快排的递归写法，而Python、R、JavaScript需要通过非递归的写法实现，否则堆栈会出现溢出的情况（爆栈）。
6：各类编程语言的执行性能原因分析，如下表所示。
| 编程语言 | 程序性能 | 原因 |
| C | 中等 | C语言的编译器能够生成高度优化的机器码，属于接近硬件层面的编程语言。 |
| C++ | 中等 | C++相比C而言，在提供更多抽象和特性的同时，也可能引入了一些性能开销。 |
| Python | 较低 | Python是一种解释型语言，其运行时性能相比编译型语言通常较低。 |
| Java | 较高 | Java虚拟机（JVM）的高度优化，包括即时编译器（JIT）的使用，可以在运行时将Java字节码转换为接近本地代码的性能。 |
| R | 较低 | R语言主要用于统计分析和图形表示，其在数据处理方面非常强大，但在执行计算密集型算法时可能不如专为性能优化设计的语言。 |
| JavaScript | 较高 | JavaScript引擎（如V8）的显著优化，以及现代浏览器对JavaScript执行的优化，极大提高了其性能。 |
| Matlab | 中等 | MATLAB专为数值计算和科学计算设计，其解释执行的特性可能在某些情况下影响性能。 |