-
-
[原创]【C语言】测试排序算法运行效率的算法
-
发表于: 2022-4-27 19:06
-
事情是这个样子的，前几天看了c语言一个非常神奇的用法就是可以函数里面套函数
当时是参考一个师傅博客（师傅的博客连接找不到了。。）里面的demo：
当时整个人都沸腾了，正好今天要写程序设计实践的作业，就想着试着用用，任务是这个样子的：
然后拍桌子！我直接一个程序就整好了
1.测试的算法为：冒泡排序、简单选择排序、简单插入排序、归并排序、快速排序等
2.随机数组的生成通过c语言的srand和rand函数即可实现，并且根据需要的随机数的大小封装成一个函数
3.对排序算法的检测通过一个统一的函数，参数为需要排序的数组和排序算法（即函数作为参数），输出为算法（函数）运行的时间
4.函数的选择具体详细到一个菜单，方便用户交互
1.参数的个数是死定下来的，对不同的函数没有灵活性，后续可以使用变长参数的函数进一步优化
2.函数死定下来不能让用户输入，后续可能优化为测试任意算法的时间复杂度的封装程序
3.时间应该用浮点数来表示，更能看出差异
#include <stdio.h>#define YES 1#define NO 0///*判断函数，进行元素大小判断，increase判断大小比较*/
int compare(int a, int b, int increase)
{ if (increase > 0) {
if (a > b) return YES;
else return NO;
}
else
{
if (a < b) return YES;
else return NO;
}
}/*冒泡排序进行数组排序*/
void OrderArr(int arry[], int(*compare)(int, int, int), int length, int increase = 1)
{ for (int i = 0; i < length - 1; i++)
{
for (int j = 0; j < length - i - 1; j++)
{
if (compare(*(arry + j), *(arry + j + 1), increase))
{
int temp = *(arry + j + 1);
*(arry + j + 1) = *(arry + j);
*(arry + j) = temp;
}
}
}
}/*输出函数*/
void Print(int a[], int length)
{ for (int i = 0; i < length; i++)
{
printf("%d ", *(a + i));
}
printf("\n");
}int main()
{ int a[5] = { 1, 4, 2, 6, 3 };
//增序排列数组
OrderArr(a, compare, 5);
Print(a, 5);
//降序排列数组
OrderArr(a, compare, 5, -1);
Print(a, 5);
}#include <stdio.h>#define YES 1#define NO 0///*判断函数，进行元素大小判断，increase判断大小比较*/
int compare(int a, int b, int increase)
{ if (increase > 0) {
if (a > b) return YES;
else return NO;
}
else
{
if (a < b) return YES;
else return NO;
}
}/*冒泡排序进行数组排序*/
void OrderArr(int arry[], int(*compare)(int, int, int), int length, int increase = 1)
{ for (int i = 0; i < length - 1; i++)
{
for (int j = 0; j < length - i - 1; j++)
{
if (compare(*(arry + j), *(arry + j + 1), increase))
{
int temp = *(arry + j + 1);
*(arry + j + 1) = *(arry + j);
*(arry + j) = temp;
}
}
}
}/*输出函数*/
void Print(int a[], int length)
{ for (int i = 0; i < length; i++)
{
printf("%d ", *(a + i));
}
printf("\n");
}int main()
{ int a[5] = { 1, 4, 2, 6, 3 };
//增序排列数组
OrderArr(a, compare, 5);
Print(a, 5);
//降序排列数组
OrderArr(a, compare, 5, -1);
Print(a, 5);
}#include <time.h> #include <stdio.h>#include <stdlib.h>#include <iostream>using namespace std; const int N=1e6+10;
int len;
int s[N],result[N];
void bubble_sort(int arr[], int l,int r) { //冒泡排序
int i, j, temp;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}void SelectSort(int num[],int l,int r)
{ int i,j,k,temp;
for(i=0;i<len;i++)
{
k=i;//记录位置
for(j=i+1;j<len;j++)//查找后面的最小值
if(num[k]>num[j])
k=j;//记录位置
if(k!=i)//交换位置
{
temp=num[i];
num[i]=num[k];
num[k]=temp;
}
}
}void Insert_Sort(int arr[],int l,int r) {//降序
int length=len;
for (int i = 1; i < length; i++) {
while (arr[i] < arr[i - 1]) {
int tmp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = tmp;
i--;
}
}
}void merge(int arr[], int start, int mid, int end)
{ int k = 0;
int i = start;
int j = mid + 1;
while (i <= mid && j <= end) {
if (arr[i] < arr[j]){
result[k++] = arr[i++];
}
else{
result[k++] = arr[j++];
}
}
if (i == mid + 1) {
while(j <= end)
result[k++] = arr[j++];
}
if (j == end + 1) {
while (i <= mid)
result[k++] = arr[i++];
}
for (j = 0, i = start ; j < k; i++, j++) {
arr[i] = result[j];
}
}void mergeSort(int arr[], int start, int end) {
if (start >= end)
return;
int mid = ( start + end ) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}int partition(int arr[], int low, int high){
int key;
key = arr[low];
while(low<high){
while(low <high && arr[high]>= key )
high--;
if(low<high)
arr[low++] = arr[high];
while( low<high && arr[low]<=key )
low++;
if(low<high)
arr[high--] = arr[low];
}
arr[low] = key;
return low;
}void quick_sort(int arr[], int start, int end){
int pos;
if (start<end){
pos = partition(arr, start, end);
quick_sort(arr,start,pos-1);
quick_sort(arr,pos+1,end);
}
return;
}double test_your_func(int arr[],void(*func)(int arr[],int l, int r))
{ double a,b;
a=time(0LL);
func(arr,1,len);
b=time(0LL);
return b-a;
}int make_random_arr(int arr[])
{ int n;
srand(time(NULL));
puts("请输入数组元素个数:");
scanf("%d",&n);
for(int i=1;i<=n;i++)
arr[i]=rand();
return n;
}void menu() { system("cls");
printf("\n\n\n\n\n");
printf("\t\t|--------------------可测试的函数目录-----------|\n");
printf("\t\t|\t 0. 退出 |\n");
printf("\t\t|\t 1. 生成随机数组 |\n");
printf("\t\t|\t 2. 打印数组元素 |\n");
printf("\t\t|\t 3. 微调数组元素 |\n");
printf("\t\t|\t 4. 测试排序算法 |\n");
printf("\t\t|-----------------------------------------------|\n");
printf("\t\t请选择(0-5):");
}void swap(int *p1,int *p2)
{ int temp; //临时变量
temp = *p1;
*p1 = *p2;
*p2 = temp;
}void menu_of_function(){ system("cls");
printf("\n\n\n\n\n");
printf("\t\t|--------------------可测试的算法目录-----------|\n");
printf("\t\t|\t 0. 退出 |\n");
printf("\t\t|\t 1. 冒泡排序 |\n");
printf("\t\t|\t 2. 简单选择排序 |\n");
printf("\t\t|\t 3. 简单插入排序 |\n");
printf("\t\t|\t 4. 归并排序 |\n");
printf("\t\t|\t 5. 快速排序 |\n");
printf("\t\t|-----------------------------------------------|\n");
printf("\t\t请选择(0-5):");
}int main()
{ int n;
menu();
scanf("%d",&n);
while(n)
{
if(n==1) len=make_random_arr(s);
else if(n==2)
{
printf("当前数组的元素个数：%d\n",len);
for(int i=1;i<=len;i++)
printf("%d ",s[i]);
puts("");
system("pause");
}
else if(n==3)
{
puts("请输入需要交换的两个元素的下标：");
int a,b;
scanf("%d%d",&a,&b);
swap(&s[a],&s[b]);
}
else
{
int nn;
menu_of_function();
scanf("%d",&nn);
while(nn)
{
switch(nn)
{
case 1:
printf("对于冒泡排序且元素个数为:%d的数组的运行时间为:%.10lfS\n",len,test_your_func(s,bubble_sort));
break;
case 2:
printf("对于简单选择排序且元素个数为:%d的数组的运行时间为:%lf\n",len,test_your_func(s,SelectSort));
break;
case 3:
printf("对于简单插入排序且元素个数为:%d的数组的运行时间为:%lf\n",len,test_your_func(s,Insert_Sort));
break;
case 4:
printf("对于归并排序且元素个数为:%d的数组的运行时间为:%lf\n",len,test_your_func(s,mergeSort));
break;
case 5:
printf("对于快速排序且元素个数为:%d的数组的运行时间为:%lf\n",len,test_your_func(s,quick_sort));
break;
default:break;
}
system("pause");
menu_of_function();
scanf("%d",&nn);
}
}
menu();
scanf("%d",&n);
}
return 0;
}#include <time.h> #include <stdio.h>#include <stdlib.h>#include <iostream>using namespace std; const int N=1e6+10;
int len;
int s[N],result[N];
void bubble_sort(int arr[], int l,int r) { //冒泡排序
int i, j, temp;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}void SelectSort(int num[],int l,int r)
{ int i,j,k,temp;
for(i=0;i<len;i++)
{
k=i;//记录位置
for(j=i+1;j<len;j++)//查找后面的最小值
if(num[k]>num[j])
k=j;//记录位置
if(k!=i)//交换位置
{
temp=num[i];
num[i]=num[k];
num[k]=temp;
}
}
}void Insert_Sort(int arr[],int l,int r) {//降序
int length=len;
for (int i = 1; i < length; i++) {
while (arr[i] < arr[i - 1]) {
int tmp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = tmp;
i--;
}
}
}void merge(int arr[], int start, int mid, int end)
{ int k = 0;
int i = start;
int j = mid + 1;
while (i <= mid && j <= end) {
if (arr[i] < arr[j]){
result[k++] = arr[i++];
}
else{
result[k++] = arr[j++];
}
}
if (i == mid + 1) {
while(j <= end)
result[k++] = arr[j++];
}
if (j == end + 1) {
while (i <= mid)
result[k++] = arr[i++];
}
for (j = 0, i = start ; j < k; i++, j++) {
arr[i] = result[j];
}
}void mergeSort(int arr[], int start, int end) {
if (start >= end)
return;
int mid = ( start + end ) / 2;
mergeSort(arr, start, mid);
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
最后于 2022-5-7 12:25
被Nameless_a编辑
，原因：
|
|
|---|---|
