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

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

声发射定位算法 Matlab 仿真项目源码+文档说明(高分项目)

声发射定位算法 Matlab 仿真项目源码+文档说明(高分项目),含有代码注释,新手也可看懂,个人手打98分项目,导师非常认可的高分项目,毕业设计、期末大作业和课程设计高分必看,下载下来,简单部署,就可以使用。该项目可以直接作为毕设、期末大作业使用,代码都在里面,系统功能完善、界面美观、操作简单、功能齐全、管理便捷,具有很高的实际应用价值,项目都经过严格调试,确保可以运行! 声发射定位算法 Matlab 仿真项目源码+文档说明(高分项目)声发射定位算法 Matlab 仿真项目源码+文档说明(高分项目)声发射定位算法 Matlab 仿真项目源码+文档说明(高分项目)声发射定位算法 Matlab 仿真项目源码+文档说明(高分项目)声发射定位算法 Matlab 仿真项目源码+文档说明(高分项目)声发射定位算法 Matlab 仿真项目源码+文档说明(高分项目)声发射定位算法 Matlab 仿真项目源码+文档说明(高分项目)声发射定位算法 Matlab 仿真项目源码+文档说明(高分项目)声发射定位算法 Matlab 仿真项目源码+文档说明(高分项目)声发射定位算法 Matlab 仿真项目源码+
recommend-type

Monkey测试,推包文件

monkey测试,推包文件
recommend-type

【中科院1区】Matlab实现向量加权平均算法INFO-RF锂电池健康状态估计算法研究.rar

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

【源码+数据库脚本+项目讲解】基于JavaWeb+mysql实现的企业电子商城

一、项目简介 本项目是一套基于JavaWeb电子商城,主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都经过严格调试,eclipse 确保可以运行! 该系统功能完善、界面美观、操作简单、功能齐全、管理便捷,具有很高的实际应用价值 二、技术实现 jsp+servlet+mysql 三、开发运行环境 jdk1.8 Tomcat8及其以上版本 Mysql5.5及以上版本 四、系统功能 首页 销售排行 新品上架 特价商品 查看订单 购物车 会员修改 加入购物车 继续购物 去收银台结账 清空购物车 修改数量等功能 详情 https://blog.csdn.net/weixin_43860634/article/details/130983090
recommend-type

Android圆角进度条控件的设计与应用

资源摘要信息:"Android-RoundCornerProgressBar" 在Android开发领域,一个美观且实用的进度条控件对于提升用户界面的友好性和交互体验至关重要。"Android-RoundCornerProgressBar"是一个特定类型的进度条控件,它不仅提供了进度指示的常规功能,还具备了圆角视觉效果,使其更加美观且适应现代UI设计趋势。此外,该控件还可以根据需求添加图标,进一步丰富进度条的表现形式。 从技术角度出发,实现圆角进度条涉及到Android自定义控件的开发。开发者需要熟悉Android的视图绘制机制,包括但不限于自定义View类、绘制方法(如`onDraw`)、以及属性动画(Property Animation)。实现圆角效果通常会用到`Canvas`类提供的画图方法,例如`drawRoundRect`函数,来绘制具有圆角的矩形。为了添加图标,还需考虑如何在进度条内部适当地放置和绘制图标资源。 在Android Studio这一集成开发环境(IDE)中,自定义View可以通过继承`View`类或者其子类(如`ProgressBar`)来完成。开发者可以定义自己的XML布局文件来描述自定义View的属性,比如圆角的大小、颜色、进度值等。此外,还需要在Java或Kotlin代码中处理用户交互,以及进度更新的逻辑。 在Android中创建圆角进度条的步骤通常如下: 1. 创建自定义View类:继承自`View`类或`ProgressBar`类,并重写`onDraw`方法来自定义绘制逻辑。 2. 定义XML属性:在资源文件夹中定义`attrs.xml`文件,声明自定义属性,如圆角半径、进度颜色等。 3. 绘制圆角矩形:在`onDraw`方法中使用`Canvas`的`drawRoundRect`方法绘制具有圆角的进度条背景。 4. 绘制进度:利用`Paint`类设置进度条颜色和样式,并通过`drawRect`方法绘制当前进度覆盖在圆角矩形上。 5. 添加图标:根据自定义属性中的图标位置属性,在合适的时机绘制图标。 6. 通过编程方式更新进度:在Activity或Fragment中,使用自定义View的方法来编程更新进度值。 7. 实现动画:如果需要,可以通过Android的动画框架实现进度变化的动画效果。 标签中的"Android开发"表明,这些知识点和技能主要面向的是Android平台的开发人员。对于想要在Android应用中实现自定义圆角进度条的开发者来说,他们需要具备一定的Android编程基础,并熟悉相关的开发工具和库。 在"RoundCornerProgressBar-master"压缩包文件的文件名称列表中,我们可以推测这个资源包含了完整的项目代码,包括源代码、资源文件、布局文件、可能的示例代码以及必要的文档说明。开发者通过下载和解压缩这个包,可以得到一个完整的项目,从而可以直接查看代码实现细节,或是将其集成到自己的项目中。 最终,对于希望使用"Android-RoundCornerProgressBar"的开发者,关键在于理解自定义View的创建过程、圆角图形的绘制技术,以及如何在Android应用中集成和使用这些自定义控件。通过上述知识点的学习和实践,开发者能够掌握在Android应用中创建美观且功能丰富的用户界面所需的技能。
recommend-type

管理建模和仿真的文件

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

【R语言lattice包实战】:从案例到技巧,图形制作不再难

![R语言数据包使用详细教程lattice](http://pfister.ee.duke.edu/images/Nguyen-arxiv11-fig2.jpg) # 1. R语言与lattice包概述 R语言作为统计分析领域内广泛应用的编程语言,凭借其强大的图形功能而受到数据科学家的青睐。在R语言中,lattice包是绘图系统的重要组成部分,它基于trellis图形系统设计,能够高效地创建多变量条件图。本章节将引导读者对lattice包有一个初步的了解,并概述其功能和应用范围。 ## 1.1 R语言中的图形系统 R语言提供了一系列的图形系统,基础图形系统(base graphics)是其
recommend-type

输入正整数n.打出长度为n的菱形

好的,以下是打印菱形的代码实现: ``` #include <stdio.h> #include <stdlib.h> int main() { int n, i, j; printf("请输入一个正整数n:"); scanf("%d", &n); if(n % 2 == 0) { // 如果输入的n是偶数,将其加1变成奇数 n++; } for(i = 0; i < n / 2 + 1; i++) { for(j = 0; j < n / 2 - i; j++) { printf(
recommend-type

mui框架实现带侧边栏的响应式布局

资源摘要信息:"mui实现简单布局.zip" mui是一个基于HTML5的前端框架,它采用了类似Bootstrap的语义化标签,但是专门为移动设备优化。该框架允许开发者使用Web技术快速构建高性能、可定制、跨平台的移动应用。此zip文件可能包含了一个用mui框架实现的简单布局示例,该布局具有侧边栏,能够实现首页内容的切换。 知识点一:mui框架基础 mui框架是一个轻量级的前端库,它提供了一套响应式布局的组件和丰富的API,便于开发者快速上手开发移动应用。mui遵循Web标准,使用HTML、CSS和JavaScript构建应用,它提供了一个类似于jQuery的轻量级库,方便DOM操作和事件处理。mui的核心在于其强大的样式表,通过CSS可以实现各种界面效果。 知识点二:mui的响应式布局 mui框架支持响应式布局,开发者可以通过其提供的标签和类来实现不同屏幕尺寸下的自适应效果。mui框架中的标签通常以“mui-”作为前缀,如mui-container用于创建一个宽度自适应的容器。mui中的布局类,比如mui-row和mui-col,用于创建灵活的栅格系统,方便开发者构建列布局。 知识点三:侧边栏实现 在mui框架中实现侧边栏可以通过多种方式,比如使用mui sidebar组件或者通过布局类来控制侧边栏的位置和宽度。通常,侧边栏会使用mui的绝对定位或者float浮动布局,与主内容区分开来,并通过JavaScript来控制其显示和隐藏。 知识点四:首页内容切换功能 实现首页可切换的功能,通常需要结合mui的JavaScript库来控制DOM元素的显示和隐藏。这可以通过mui提供的事件监听和动画效果来完成。开发者可能会使用mui的开关按钮或者tab标签等组件来实现这一功能。 知识点五:mui的文件结构 该压缩包文件包含的目录结构说明了mui项目的基本结构。其中,"index.html"文件是项目的入口文件,它将展示整个应用的界面。"manifest.json"文件是应用的清单文件,它在Web应用中起到了至关重要的作用,定义了应用的名称、版本、图标和其它配置信息。"css"文件夹包含所有样式表文件,"unpackage"文件夹可能包含了构建应用后的文件,"fonts"文件夹存放字体文件,"js"文件夹则是包含JavaScript代码的地方。 知识点六:mui的打包和分发 mui框架支持项目的打包和分发,开发者可以使用其提供的命令行工具来打包项目,生成可以部署到服务器的静态资源。这一步通常涉及到资源的压缩、合并和优化。打包后,开发者可以将项目作为一个Web应用分发,也可以将其打包为原生应用,比如通过Cordova、PhoneGap等工具打包成可在iOS或Android设备上安装的应用。 知识点七:mui的兼容性和性能优化 mui框架对老旧设备也做了兼容性考虑,保证应用在低端设备上也有较好的性能表现。性能优化方面,mui提供了多种工具和最佳实践,例如使用懒加载、避免全局变量污染、减少DOM操作等策略来提高应用的运行速度和用户体验。 以上内容是根据标题、描述以及文件名称列表推测出的关于mui实现简单布局的知识点。开发者可以通过分析和实践上述知识点来更好地理解和运用mui框架,从而构建出高效且用户友好的移动应用界面。