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

时间: 2023-08-18 09:05:03 浏览: 47
以下是用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嵌入式大厂面经C++首创

2024嵌入式大厂面经C++首创提取方式是百度网盘分享地址
recommend-type

C++ 高性能爬虫代码,带UI

C++ 高性能爬虫代码,带UI
recommend-type

2024嵌入式面试资料裕日软件C笔试题

2024嵌入式面试资料裕日软件C笔试题提取方式是百度网盘分享地址
recommend-type

黑色素瘤分类数据集10015张7类别.7z

数据集类型:图像分类用,不可用于目标检测无标注文件 数据集格式:仅仅包含jpg图片,每个类别文件夹下面存放着对应图片 图片数量(jpg文件个数):10015 分类类别数:7 类别名称:[“0”,“1”,“2”,“3”,“4”,“5”,“6”] 更多信息:blog.csdn.net/FL1623863129/article/details/139561265
recommend-type

2024年高尿酸及痛风疾病医药行业分析报告.pptx

行业报告
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

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

MATLAB正态分布协方差分析:揭示正态分布变量之间的协方差

![MATLAB正态分布协方差分析:揭示正态分布变量之间的协方差](https://site.cdn.mengte.online/official/2021/11/20211128213137293.png) # 1. 正态分布概述 正态分布,又称高斯分布,是统计学中最重要的连续概率分布之一。它广泛应用于自然科学、社会科学和工程领域。 正态分布的概率密度函数为: ``` f(x) = (1 / (σ√(2π))) * exp(-(x - μ)² / (2σ²)) ``` 其中: - μ:正态分布的均值 - σ:正态分布的标准差 - π:圆周率 正态分布具有以下特性: - 对称性:
recommend-type

我正在开发一款个人碳足迹计算app,如何撰写其需求分析文档,请给我一个范例

为了更全面、清晰地定义个人碳足迹计算app的需求,需求分析文档应该包含以下内容: 1.项目简介:对该app项目的概述及目标进行说明。 2.用户分析:包括目标用户群、用户需求、行为等。 3.功能需求:对app的基本功能进行定义,如用户登录、数据录入、数据统计等。 4.非功能需求:对使用app的性能和质量等进行定义,如界面设计、数据安全、可扩展性等。 5.运行环境:包括app的开发环境和使用环境。 下面是一个范例: 需求分析文档 1. 项目简介 该app项目旨在为用户提供一款方便、易用、可定制的个人碳足迹计算平台,以促进环保和可持续性发展。 2. 用户分析 目标用户群:全球关
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。