[原创]【C语言】测试排序算法运行效率的算法-编程技术-看雪-安全社区|安全招聘|kanxue.com

[原创]【C语言】测试排序算法运行效率的算法

2022-4-27 19:06 4908

[原创]【C语言】测试排序算法运行效率的算法

Nameless_a 活跃值

2022-4-27 19:06

4908

废话

事情是这个样子的，前几天看了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);
}

当时整个人都沸腾了，正好今天要写程序设计实践的作业，就想着试着用用，任务是这个样子的：

然后拍桌子！我直接一个程序就整好了

源码

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

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