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

时间: 2023-08-18 18:05:03 浏览: 55
以下是用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

2024年欧洲化学电镀市场主要企业市场占有率及排名.docx

2024年欧洲化学电镀市场主要企业市场占有率及排名.docx
recommend-type

计算机本科生毕业论文1111

老人服务系统
recommend-type

探索Elasticsearch的节点角色:集群的构建基石

Elasticsearch是一个基于Lucene的搜索引擎,它提供了一个分布式、多租户能力的全文搜索引擎,具有HTTP web接口和无模式的JSON文档。Elasticsearch是用Java编写的,但也可以作为服务在多种操作系统上运行,包括Windows、Linux和macOS。 ### Elasticsearch的主要特点包括: 1. **分布式性质**:Elasticsearch天生设计为分布式,可以很容易地扩展到数百台服务器,处理PB级别的数据。 2. **实时搜索**:Elasticsearch提供了快速的搜索能力,可以实时索引和搜索数据。 3. **高可用性**:通过自动分片和复制,Elasticsearch确保了数据的高可用性和容错性。 4. **多租户**:Elasticsearch支持多租户,允许多个用户或应用共享同一集群资源。 5. **丰富的查询语言**:Elasticsearch提供了强大的查询语言,支持结构化、非结构化数据的复杂搜索需求。 6. **横向扩展**:Elasticsearch可以通过简单地增加节点来扩展集群。 等
recommend-type

JAVA语言考试系统的设计与实现(论文+源代码+文献综述+外文翻译+开题报告).zip

JAVA语言考试系统的设计与实现(论文+源代码+文献综述+外文翻译+开题报告)
recommend-type

2024高频作业题答案.zip

2024高频作业题答案.zip
recommend-type

BSC关键绩效财务与客户指标详解

BSC(Balanced Scorecard,平衡计分卡)是一种战略绩效管理系统,它将企业的绩效评估从传统的财务维度扩展到非财务领域,以提供更全面、深入的业绩衡量。在提供的文档中,BSC绩效考核指标主要分为两大类:财务类和客户类。 1. 财务类指标: - 部门费用的实际与预算比较:如项目研究开发费用、课题费用、招聘费用、培训费用和新产品研发费用,均通过实际支出与计划预算的百分比来衡量,这反映了部门在成本控制上的效率。 - 经营利润指标:如承保利润、赔付率和理赔统计,这些涉及保险公司的核心盈利能力和风险管理水平。 - 人力成本和保费收益:如人力成本与计划的比例,以及标准保费、附加佣金、续期推动费用等与预算的对比,评估业务运营和盈利能力。 - 财务效率:包括管理费用、销售费用和投资回报率,如净投资收益率、销售目标达成率等,反映公司的财务健康状况和经营效率。 2. 客户类指标: - 客户满意度:通过包装水平客户满意度调研,了解产品和服务的质量和客户体验。 - 市场表现:通过市场销售月报和市场份额,衡量公司在市场中的竞争地位和销售业绩。 - 服务指标:如新契约标保完成度、续保率和出租率,体现客户服务质量和客户忠诚度。 - 品牌和市场知名度:通过问卷调查、公众媒体反馈和总公司级评价来评估品牌影响力和市场认知度。 BSC绩效考核指标旨在确保企业的战略目标与财务和非财务目标的平衡,通过量化这些关键指标,帮助管理层做出决策,优化资源配置,并驱动组织的整体业绩提升。同时,这份指标汇总文档强调了财务稳健性和客户满意度的重要性,体现了现代企业对多维度绩效管理的重视。
recommend-type

管理建模和仿真的文件

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

【实战演练】俄罗斯方块:实现经典的俄罗斯方块游戏,学习方块生成和行消除逻辑。

![【实战演练】俄罗斯方块:实现经典的俄罗斯方块游戏,学习方块生成和行消除逻辑。](https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/70a49cc62dcc46a491b9f63542110765~tplv-k3u1fbpfcp-zoom-in-crop-mark:1512:0:0:0.awebp) # 1. 俄罗斯方块游戏概述** 俄罗斯方块是一款经典的益智游戏,由阿列克谢·帕基特诺夫于1984年发明。游戏目标是通过控制不断下落的方块,排列成水平线,消除它们并获得分数。俄罗斯方块风靡全球,成为有史以来最受欢迎的视频游戏之一。 # 2.
recommend-type

卷积神经网络实现手势识别程序

卷积神经网络(Convolutional Neural Network, CNN)在手势识别中是一种非常有效的机器学习模型。CNN特别适用于处理图像数据,因为它能够自动提取和学习局部特征,这对于像手势这样的空间模式识别非常重要。以下是使用CNN实现手势识别的基本步骤: 1. **输入数据准备**:首先,你需要收集或获取一组带有标签的手势图像,作为训练和测试数据集。 2. **数据预处理**:对图像进行标准化、裁剪、大小调整等操作,以便于网络输入。 3. **卷积层(Convolutional Layer)**:这是CNN的核心部分,通过一系列可学习的滤波器(卷积核)对输入图像进行卷积,以
recommend-type

绘制企业战略地图:从财务到客户价值的六步法

"BSC资料.pdf" 战略地图是一种战略管理工具,它帮助企业将战略目标可视化,确保所有部门和员工的工作都与公司的整体战略方向保持一致。战略地图的核心内容包括四个相互关联的视角:财务、客户、内部流程和学习与成长。 1. **财务视角**:这是战略地图的最终目标,通常表现为股东价值的提升。例如,股东期望五年后的销售收入达到五亿元,而目前只有一亿元,那么四亿元的差距就是企业的总体目标。 2. **客户视角**:为了实现财务目标,需要明确客户价值主张。企业可以通过提供最低总成本、产品创新、全面解决方案或系统锁定等方式吸引和保留客户,以实现销售额的增长。 3. **内部流程视角**:确定关键流程以支持客户价值主张和财务目标的实现。主要流程可能包括运营管理、客户管理、创新和社会责任等,每个流程都需要有明确的短期、中期和长期目标。 4. **学习与成长视角**:评估和提升企业的人力资本、信息资本和组织资本,确保这些无形资产能够支持内部流程的优化和战略目标的达成。 绘制战略地图的六个步骤: 1. **确定股东价值差距**:识别与股东期望之间的差距。 2. **调整客户价值主张**:分析客户并调整策略以满足他们的需求。 3. **设定价值提升时间表**:规划各阶段的目标以逐步缩小差距。 4. **确定战略主题**:识别关键内部流程并设定目标。 5. **提升战略准备度**:评估并提升无形资产的战略准备度。 6. **制定行动方案**:根据战略地图制定具体行动计划,分配资源和预算。 战略地图的有效性主要取决于两个要素: 1. **KPI的数量及分布比例**:一个有效的战略地图通常包含20个左右的指标,且在四个视角之间有均衡的分布,如财务20%,客户20%,内部流程40%。 2. **KPI的性质比例**:指标应涵盖财务、客户、内部流程和学习与成长等各个方面,以全面反映组织的绩效。 战略地图不仅帮助管理层清晰传达战略意图,也使员工能更好地理解自己的工作如何对公司整体目标产生贡献,从而提高执行力和组织协同性。