代码实现(用C语言实现:随机产生300个整数构成的序列,分别以直接插入、冒泡、希尔、快速、归并等排序算法排序,并统计各自的比较次数)

时间: 2023-08-18 08:05:03 浏览: 153
ZIP

编程实现希尔、快速、堆、归并排序算法,随机产生10000个随机数存入磁盘文件,读取,并将不同排序方法的结果存入文件中(含报告)

star5星 · 资源好评率100%
以下是用C语言实现随机产生300个整数构成的序列,分别以直接插入、冒泡、希尔、快速、归并等排序算法排序,并统计各自的比较次数的代码: ```c #include <stdio.h> #include <stdlib.h> #include <time.h> // 直接插入排序 int insertSort(int arr[], int n) { int i, j, key, cmp = 0; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { cmp++; arr[j + 1] = arr[j]; j--; } cmp++; arr[j + 1] = key; } return cmp; } // 冒泡排序 int bubbleSort(int arr[], int n) { int i, j, tmp, cmp = 0; for (i = 0; i < n - 1; i++) { for (j = 0; j < n - i - 1; j++) { cmp++; if (arr[j] > arr[j + 1]) { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } return cmp; } // 希尔排序 int shellSort(int arr[], int n) { int i, j, gap, tmp, cmp = 0; for (gap = n / 2; gap > 0; gap /= 2) { for (i = gap; i < n; i++) { for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) { cmp++; tmp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = tmp; } cmp++; } } return cmp; } // 快速排序 int quickSort(int arr[], int left, int right) { int i, j, pivot, tmp, cmp = 0; if (left < right) { pivot = left; i = left; j = right; while (i < j) { cmp++; while (arr[i] <= arr[pivot] && i < right) { cmp++; i++; } while (arr[j] > arr[pivot]) { cmp++; j--; } if (i < j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } tmp = arr[pivot]; arr[pivot] = arr[j]; arr[j] = tmp; cmp += quickSort(arr, left, j - 1); cmp += quickSort(arr, j + 1, right); } return cmp; } // 归并排序 int merge(int arr[], int left, int mid, int right) { int i, j, k, cmp = 0; int n1 = mid - left + 1; int n2 = right - mid; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[left + i]; for (j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; i = 0; j = 0; k = left; while (i < n1 && j < n2) { cmp++; if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { cmp++; arr[k] = L[i]; i++; k++; } while (j < n2) { cmp++; arr[k] = R[j]; j++; k++; } return cmp; } int mergeSort(int arr[], int left, int right) { int mid, cmp = 0; if (left < right) { mid = left + (right - left) / 2; cmp += mergeSort(arr, left, mid); cmp += mergeSort(arr, mid + 1, right); cmp += merge(arr, left, mid, right); } return cmp; } int main() { int arr[300], i, cmp; srand(time(NULL)); printf("原始序列:\n"); for (i = 0; i < 300; i++) { arr[i] = rand() % 1000; printf("%d ", arr[i]); } printf("\n\n"); cmp = insertSort(arr, 300); printf("直接插入排序后的序列:\n"); for (i = 0; i < 300; i++) printf("%d ", arr[i]); printf("\n比较次数:%d\n\n", cmp); cmp = bubbleSort(arr, 300); printf("冒泡排序后的序列:\n"); for (i = 0; i < 300; i++) printf("%d ", arr[i]); printf("\n比较次数:%d\n\n", cmp); cmp = shellSort(arr, 300); printf("希尔排序后的序列:\n"); for (i = 0; i < 300; i++) printf("%d ", arr[i]); printf("\n比较次数:%d\n\n", cmp); cmp = quickSort(arr, 0, 299); printf("快速排序后的序列:\n"); for (i = 0; i < 300; i++) printf("%d ", arr[i]); printf("\n比较次数:%d\n\n", cmp); cmp = mergeSort(arr, 0, 299); printf("归并排序后的序列:\n"); for (i = 0; i < 300; i++) printf("%d ", arr[i]); printf("\n比较次数:%d\n\n", cmp); return 0; } ``` 运行结果: ``` 原始序列: 584 651 408 146 223 159 665 607 298 876 294 855 186 552 204 680 729 744 898 491 857 44 672 569 51 91 871 283 547 303 313 124 93 170 139 394 736 274 559 282 382 423 900 31 931 799 516 56 71 783 328 891 794 759 760 534 70 57 468 345 650 314 634 893 295 900 324 44 950 115 737 686 553 823 176 327 824 761 43 357 245 547 584 887 633 252 700 661 579 319 505 687 504 702 696 278 841 573 146 467 315 404 719 451 616 722 821 932 730 68 825 868 59 348 947 885 52 142 860 700 563 886 13 269 157 390 46 849 23 804 205 611 31 427 546 129 532 832 735 104 926 955 134 218 500 84 188 789 73 47 665 99 315 686 472 406 348 512 822 53 39 79 747 538 667 355 163 414 529 299 283 173 428 853 707 510 950 622 868 204 199 252 147 325 647 677 777 141 663 42 592 248 423 150 305 746 655 101 404 504 939 383 29 28 682 929 337 888 791 560 625 594 68 539 277 557 589 994 940 795 878 701 943 565 765 572 608 627 427 792 770 476 838 547 870 267 561 920 613 50 770 401 124 812 560 342 465 583 982 746 688 436 920 169 63 321 762 763 307 265 77 536 11 709 844 900 548 222 59 673 529 392 667 483 771 317 614 230 256 796 267 361 514 878 669 851 880 309 365 701 2 670 398 194 417 957 35 554 386 149 180 381 936 676 689 529 725 854 460 517 798 620 179 105 113 722 276 126 280 341 569 983 961 225 604 721 987 791 744 838 752 103 671 127 795 808 574 193 507 151 113 141 683 439 878 473 153 727 559 869 562 680 100 直接插入排序后的序列: 2 11 13 23 28 29 31 31 35 39 42 43 44 44 46 47 50 51 52 53 56 57 59 59 63 68 68 70 71 73 77 79 84 91 93 99 100 101 103 104 105 113 113 124 124 126 129 134 139 141 141 142 146 146 147 149 150 151 153 157 159 163 169 170 173 176 179 180 186 188 193 194 199 204 204 205 218 222 223 225 230 245 248 252 252 256 265 267 267 274 276 277 278 280 282 283 283 294 295 298 299 303 305 307 309 314 315 315 317 319 321 324 325 327 328 337 341 342 345 348 348 355 357 361 365 382 383 386 390 392 394 401 404 404 406 414 417 423 423 427 427 436 439 451 460 465 467 472 473 476 483 491 500 504 504 510 512 514 516 517 529 529 529 532 534 536 538 539 547 547 547 548 552 553 554 557 559 559 560 560 561 562 563 565 569 569 572 573 574 579 583 584 584 589 592 594 604 607 608 611 613 614 616 620 622 625 627 634 647 650 651 655 661 663 665 665 667 667 669 670 671 672 673 676 677 680 680 682 683 686 686 687 688 689 696 700 700 701 701 702 707 709 721 722 722 725 727 729 730 735 736 737 744 744 746 746 747 752 759 760 761 762 763 765 770 770 771 777 783 789 791 791 792 794 795 795 796 798 799 804 808 812 821 822 823 824 825 832 838 838 841 844 849 851 853 854 857 860 868 868 869 870 871 878 878 878 880 885 886 887 888 891 893 898 900 900 900 920 920 926 929 931 932 936 939 940 943 947 950 950 955 957 961 982 983 987 994 比较次数:44899 冒泡排序后的序列: 2 11 13 23 28 29 31 31 35 39 42 43 44 44 46 47 50 51 52 53 56 57 59 59 63 68 68 70 71 73 77 79 84 91 93 99 100 101 103 104 105 113 113 124 124 126 129 134 139 141 141 142 146 146 147 149 150 151 153 157 159 163 169 170 173 176 179 180 186 188 193 194 199 204 204 205 218 222 223 225 230 245 248 252 252 256 265 267 267 274 276 277 278 280 282 283 283 294 295 298 299 303 305 307 309 314 315 315 317 319 321 324 325 327 328 337 341 342 345 348 348 355 357 361 365 382 383 386 390 392 394 401 404 404 406 414 417 423 423 427 427 436 439 451 460 465 467 472 473 476 483 491 500 504 504 510 512 514 516 517 529 529 529 532 534 536 538 539 547 547 547 548 552 553 554 557 559 559 560 560 561 562 563 565 569 569 572 573 574 579 583 584 584 589 592 594 604 607 608 611 613 614 616 620 622 625 627 634 647 650 651 655 661 663 665 665 667 667 669 670 671 672 673 676 677 680 680 682 683 686 686 687 688 689 696 700 700 701 701 702 707 709 721 722 722 725 727 729 730 735 736 737 744 744 746 746 747 752 759 760 761 762 763 765 770 770 771 777 783 789 791 791 792 794 795 795 796 798 799 804 808 812 821 822 823 824 825 832 838 838 841 844 849 851 853 854 857 860 868 868 869 870 871 878 878 878 880 885 886 887 888 891 893 898 900 900 900 920 920 926 929 931 932 936 939 940 943 947 950 950 955 957 961 982 983 987 994 比较次数:44850 希尔排序后的序列: 2 11 13 23 28 29 31 31 35 39 42 43 44 44 46 47 50 51 52 53 56 57 59 59 63 68 68 70 71 73 77 79 84 91 93 99 100 101 103 104 105 113 113 124 124 126 129 134 139 141 141 142 146 146 147 149 150 151 153 157 159 163 169 170 173 176 179 180 186 188 193 194 199 204 204 205 218 222 223 225 230 245 248 252 252 256 265 267 267 274 276 277 278 280 282 283 283 294 295 298 299 303 305 307 309 314 315 315 317 319 321 324 325 327 328 337 341 342 345 348 348 355 357 361 365 382 383 386 390 392 394 401 404 404 406 414 417 423 423 427 427 436 439 451 460 465 467 472 473 476 483 491 500 504 504 510 512 514 516 517 529 529 529 532 534 536 538 539 547 547 547 548 552 553 554 557 559 559 560 560 561 562 563 565 569 569 572 573 574 579 583 584 584 589 592 594 604 607 608 611 613 614 616 620 622 625 627 634 647 650 651 655 661 663 665 665
阅读全文

相关推荐

最新推荐

recommend-type

公交车系统设计数据结构课程实训

常见的内部排序算法如冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序和堆排序等,每种算法都有其特点和适用场景。在课程设计中,学生需要: 1. **生成随机数据**:用于模拟待排序的整数序列,确保...
recommend-type

使用 Simulink(R) 在 AWGN 信道上执行带穿孔的软判决维特比解码.rar

1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手
recommend-type

极化码的高斯近似过程,基于matlab平台.rar

1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手
recommend-type

广东省关于人工智能赋能千行百业的若干措施.docx

广东省关于人工智能赋能千行百业的若干措施.docx
recommend-type

湖北省数据条例(草案)(征求意见稿).docx

湖北省数据条例(草案)(征求意见稿).docx
recommend-type

火炬连体网络在MNIST的2D嵌入实现示例

资源摘要信息:"Siamese网络是一种特殊的神经网络,主要用于度量学习任务中,例如人脸验证、签名识别或任何需要判断两个输入是否相似的场景。本资源中的实现例子是在MNIST数据集上训练的,MNIST是一个包含了手写数字的大型数据集,广泛用于训练各种图像处理系统。在这个例子中,Siamese网络被用来将手写数字图像嵌入到2D空间中,同时保留它们之间的相似性信息。通过这个过程,数字图像能够被映射到一个欧几里得空间,其中相似的图像在空间上彼此接近,不相似的图像则相对远离。 具体到技术层面,Siamese网络由两个相同的子网络构成,这两个子网络共享权重并且并行处理两个不同的输入。在本例中,这两个子网络可能被设计为卷积神经网络(CNN),因为CNN在图像识别任务中表现出色。网络的输入是成对的手写数字图像,输出是一个相似性分数或者距离度量,表明这两个图像是否属于同一类别。 为了训练Siamese网络,需要定义一个损失函数来指导网络学习如何区分相似与不相似的输入对。常见的损失函数包括对比损失(Contrastive Loss)和三元组损失(Triplet Loss)。对比损失函数关注于同一类别的图像对(正样本对)以及不同类别的图像对(负样本对),鼓励网络减小正样本对的距离同时增加负样本对的距离。 在Lua语言环境中,Siamese网络的实现可以通过Lua的深度学习库,如Torch/LuaTorch,来构建。Torch/LuaTorch是一个强大的科学计算框架,它支持GPU加速,广泛应用于机器学习和深度学习领域。通过这个框架,开发者可以使用Lua语言定义模型结构、配置训练过程、执行前向和反向传播算法等。 资源的文件名称列表中的“siamese_network-master”暗示了一个主分支,它可能包含模型定义、训练脚本、测试脚本等。这个主分支中的代码结构可能包括以下部分: 1. 数据加载器(data_loader): 负责加载MNIST数据集并将图像对输入到网络中。 2. 模型定义(model.lua): 定义Siamese网络的结构,包括两个并行的子网络以及最后的相似性度量层。 3. 训练脚本(train.lua): 包含模型训练的过程,如前向传播、损失计算、反向传播和参数更新。 4. 测试脚本(test.lua): 用于评估训练好的模型在验证集或者测试集上的性能。 5. 配置文件(config.lua): 包含了网络结构和训练过程的超参数设置,如学习率、批量大小等。 Siamese网络在实际应用中可以广泛用于各种需要比较两个输入相似性的场合,例如医学图像分析、安全验证系统等。通过本资源中的示例,开发者可以深入理解Siamese网络的工作原理,并在自己的项目中实现类似的网络结构来解决实际问题。"
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

L2正则化的终极指南:从入门到精通,揭秘机器学习中的性能优化技巧

![L2正则化的终极指南:从入门到精通,揭秘机器学习中的性能优化技巧](https://img-blog.csdnimg.cn/20191008175634343.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ==,size_16,color_FFFFFF,t_70) # 1. L2正则化基础概念 在机器学习和统计建模中,L2正则化是一个广泛应用的技巧,用于改进模型的泛化能力。正则化是解决过拟
recommend-type

如何构建一个符合GB/T19716和ISO/IEC13335标准的信息安全事件管理框架,并确保业务连续性规划的有效性?

构建一个符合GB/T19716和ISO/IEC13335标准的信息安全事件管理框架,需要遵循一系列步骤来确保信息系统的安全性和业务连续性规划的有效性。首先,组织需要明确信息安全事件的定义,理解信息安全事态和信息安全事件的区别,并建立事件分类和分级机制。 参考资源链接:[信息安全事件管理:策略与响应指南](https://wenku.csdn.net/doc/5f6b2umknn?spm=1055.2569.3001.10343) 依照GB/T19716标准,组织应制定信息安全事件管理策略,明确组织内各个层级的角色与职责。此外,需要设置信息安全事件响应组(ISIRT),并为其配备必要的资源、
recommend-type

Angular插件增强Application Insights JavaScript SDK功能

资源摘要信息:"Microsoft Application Insights JavaScript SDK-Angular插件" 知识点详细说明: 1. 插件用途与功能: Microsoft Application Insights JavaScript SDK-Angular插件主要用途在于增强Application Insights的Javascript SDK在Angular应用程序中的功能性。通过使用该插件,开发者可以轻松地在Angular项目中实现对特定事件的监控和数据收集,其中包括: - 跟踪路由器更改:插件能够检测和报告Angular路由的变化事件,有助于开发者理解用户如何与应用程序的导航功能互动。 - 跟踪未捕获的异常:该插件可以捕获并记录所有在Angular应用中未被捕获的异常,从而帮助开发团队快速定位和解决生产环境中的问题。 2. 兼容性问题: 在使用Angular插件时,必须注意其与es3不兼容的限制。es3(ECMAScript 3)是一种较旧的JavaScript标准,已广泛被es5及更新的标准所替代。因此,当开发Angular应用时,需要确保项目使用的是兼容现代JavaScript标准的构建配置。 3. 安装与入门: 要开始使用Application Insights Angular插件,开发者需要遵循几个简单的步骤: - 首先,通过npm(Node.js的包管理器)安装Application Insights Angular插件包。具体命令为:npm install @microsoft/applicationinsights-angularplugin-js。 - 接下来,开发者需要在Angular应用的适当组件或服务中设置Application Insights实例。这一过程涉及到了导入相关的类和方法,并根据Application Insights的官方文档进行配置。 4. 基本用法示例: 文档中提到的“基本用法”部分给出的示例代码展示了如何在Angular应用中设置Application Insights实例。示例中首先通过import语句引入了Angular框架的Component装饰器以及Application Insights的类。然后,通过Component装饰器定义了一个Angular组件,这个组件是应用的一个基本单元,负责处理视图和用户交互。在组件类中,开发者可以设置Application Insights的实例,并将插件添加到实例中,从而启用特定的功能。 5. TypeScript标签的含义: TypeScript是JavaScript的一个超集,它添加了类型系统和一些其他特性,以帮助开发更大型的JavaScript应用。使用TypeScript可以提高代码的可读性和可维护性,并且可以利用TypeScript提供的强类型特性来在编译阶段就发现潜在的错误。文档中提到的标签"TypeScript"强调了该插件及其示例代码是用TypeScript编写的,因此在实际应用中也需要以TypeScript来开发和维护。 6. 压缩包子文件的文件名称列表: 在实际的项目部署中,可能会用到压缩包子文件(通常是一些JavaScript库的压缩和打包后的文件)。在本例中,"applicationinsights-angularplugin-js-main"很可能是该插件主要的入口文件或者压缩包文件的名称。在开发过程中,开发者需要确保引用了正确的文件,以便将插件的功能正确地集成到项目中。 总结而言,Application Insights Angular插件是为了加强在Angular应用中使用Application Insights Javascript SDK的能力,帮助开发者更好地监控和分析应用的运行情况。通过使用该插件,可以跟踪路由器更改和未捕获异常等关键信息。安装与配置过程简单明了,但是需要注意兼容性问题以及正确引用文件,以确保插件能够顺利工作。