代码实现(用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
阅读全文