Skip to content
Menu
Nameless的摸鱼笔记 Nameless的摸鱼笔记
  • 示例页面
Nameless的摸鱼笔记 Nameless的摸鱼笔记

【C语言】检测排序算法效率的算法

Posted on 2022年4月7日2022年4月7日 by Nameless

废话

事情是这个样子的,前几天看了c语言一个非常神奇的用法就是可以函数里面套函数

当时是参考一个师傅博客里面的demo:

#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>
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;
}

int test_your_func(int arr[],void(*func)(int arr[],int l, int r))
{
	int a,b;
	a=time(0);
	func(arr,1,len);
	b=time(0);
	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的数组的运行时间为:%d\n",len,test_your_func(s,bubble_sort));
						break;
					case 2:
						printf("对于简单选择排序且元素个数为:%d的数组的运行时间为:%d\n",len,test_your_func(s,SelectSort));
						break;
					case 3:
						printf("对于简单插入排序且元素个数为:%d的数组的运行时间为:%d\n",len,test_your_func(s,Insert_Sort));
						break;
					case 4:
						printf("对于归并排序且元素个数为:%d的数组的运行时间为:%d\n",len,test_your_func(s,mergeSort));
						break;
					case 5:
						printf("对于快速排序且元素个数为:%d的数组的运行时间为:%d\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;
}

1、程序设计思路

1.测试的算法为:冒泡排序、简单选择排序、简单插入排序、归并排序、快速排序等

2.随机数组的生成通过c语言的srand和rand函数即可实现,并且根据需要的随机数的大小封装成一个函数

3.对排序算法的检测通过一个统一的函数,参数为需要排序的数组和排序算法(即函数作为参数),输出为算法(函数)运行的时间

4.函数的选择具体详细到一个菜单,方便用户交互

2、运行截图

3、不足和可改进的点

1.参数的个数是死定下来的,对不同的函数没有灵活性,后续可以使用变长参数的函数进一步优化

2.函数死定下来不能让用户输入,后续可能优化为测试任意算法的时间复杂度的封装程序

3.时间应该用浮点数来表示,更能看出差异

发表回复 取消回复

要发表评论,您必须先登录。

近期文章

  • 关于Nokelock蓝牙锁破解分析
  • 基于树莓派的蓝牙调试环境搭建
  • shell之外的往事:机械兔子
  • [Googlectf2022]硬件题weather
  • 嵌入式设备组播路由攻击实战

近期评论

    归档

    • 2023年4月
    • 2023年3月
    • 2023年1月
    • 2022年10月
    • 2022年9月
    • 2022年8月
    • 2022年7月
    • 2022年5月
    • 2022年4月
    • 2022年3月
    • 2022年2月

    分类

    • fuzz
    • hardware
    • Linux
    • oi
    • PWN
    • python
    • shell之外的往事
    • 嵌入式开发
    • 未分类
    • 比赛题解
    • 程序设计实战

    其他操作

    • 登录
    • 条目feed
    • 评论feed
    • WordPress.org

    朋友们

    chuj
    夜魅楠孩
    x1ng
    pankas
    杨宝
    h4kuy4
    大能猫
    t0hka
    hash_hash
    nightu
    yolbby
    JBNRZ
    oacia
    l0tus
    Korey0sh1

    ©2022 Nameless的摸鱼笔记

    蜀ICP备2022004715号

    ©2023 Nameless的摸鱼笔记 | Powered by WordPress & Superb Themes