完结
#include <stdlib.h> #include <stdio.h> #include <time.h> #define Maxsize 100
typedef struct { int R[Maxsize + 1]; int length; } SqList; void InsertSort(
SqList&L) { int i, j; int count = 0; for (i = 2; i <= L.length; i++) if (L.R[i]
< L.R[i - 1]) { count++; L.R[0] = L.R[i]; L.R[i] = L.R[i - 1]; for (j = i - 2; L
.R[0] < L.R[j]; j--, count++) L.R[j + 1] = L.R[j]; L.R[j + 1] = L.R[0]; } printf
("\n直插法比较次数是:%d", count); } int ShellInsert(SqList &L, int dk) { int i, j; int
count= 0; for (i = dk + 1; i <= L.length; i++) if (L.R[i] < L.R[i - dk]) { count
++; L.R[0] = L.R[i]; for (j = i - dk; j > 0 && L.R[0] < L.R[j]; j -= dk, count++
) L.R[j + dk] = L.R[j]; L.R[j + dk] = L.R[0]; } return count; } void ShellSort(
SqList&L, int dita[], int t) { int k, count = 0, sum = 0; for (k = 0; k < t; k++
) { count = ShellInsert(L, dita[k]); sum += count; } printf("\n希尔排序比较次数是:%d",
sum); } int Partition(SqList &L, int low, int high, int &count) { count = 0; int
pivotkey; L.R[0] = L.R[low]; pivotkey = L.R[low]; while (low < high) { count++;
while (low < high && L.R[high] >= pivotkey) { high--; count++; } if (low < high)
{ L.R[low++] = L.R[high]; count++; } while (low < high && L.R[low] <= pivotkey)
{ low++; count += 2; } if (low < high) { L.R[high--] = L.R[low]; count++; } } L.
R[low] = L.R[0]; return low; } void QSort(SqList &L, int low, int high, int &
count) { int pivotloc, sum; if (low < high) { count++; pivotloc = Partition(L,
low, high, sum); count += sum; QSort(L, low, pivotloc - 1, count); QSort(L,
pivotloc+ 1, high, count); } } void Merge(int *R, int low, int m, int high, int
&count) { int i = low, j = m + 1, p = 0; int *R1; R1 = (int *)malloc((high - low
+ 1) * sizeof(int)); if (!R1) return; while (i <= m && j <= high) { R1[p++] = (R
[i] <= R[j]) ? R[i++] : R[j++]; count += 2; } while (i <= m) { R1[p++] = R[i++];
count++; } while (j <= high) { R1[p++] = R[j++], count++; } for (p = 0, i = low
; i <= high; p++, i++) R[i] = R1[p]; } void MergeSort(SqList &L, int low, int
high, int &count) { int mid; int sum = 0; if (low < high) { mid = (low + high) /
2; MergeSort(L, low, mid, count); MergeSort(L, mid + 1, high, count); Merge(L.R,
low, mid, high, sum); count += sum; } } int main() { int i; SqList L, L0; int
dita[3]; int count = 0, count1 = 0; srand((unsigned)time(NULL) + (unsigned)rand(
)); for (i = 1; i <= 100; i++) { L.R[i] = rand() % 100; L0.R[i] = L.R[i]; }
printf("100个随机数是:\n"); for (i = 1; i <= 100; i++) { if (i % 10) printf("%5d", L0
.R[i]); else { printf("%5d", L0.R[i]); printf("\n"); } } L.length = L0.length =
100; /*直插排序*/ InsertSort(L); printf("\n直插排序结果:\n"); for (i = 1; i <= 100; i++) {
if (i % 10) printf("%5d", L.R[i]); else { printf("%5d", L.R[i]); printf("\n"); }
} for (i = 1; i <= 100; i++) { L.R[i] = L0.R[i]; } /*更新L*/ /*希尔排序*/ dita[0] = 5;
dita[1] = 3; dita[2] = 1; ShellSort(L, dita, 3); printf("\n希尔排序结果:\n"); for (i
= 1; i <= 100; i++) { if (i % 10) printf("%5d", L.R[i]); else { printf("%5d", L.
R[i]); printf("\n"); } } for (i = 1; i <= 100; i++) { L.R[i] = L0.R[i]; }
/*更新L*/ /*快速排序*/ QSort(L, 1, L.length, count); printf("\n快速排序比较次数是:%d\n", count)
; printf("快速排序结果:\n"); for (i = 1; i <= 100; i++) { if (i % 10) printf("%5d", L.
R[i]); else { printf("%5d", L.R[i]); printf("\n"); } } /*归并排序*/ for (i = 1; i <=
100; i++) { L.R[i] = L0.R[i]; } /*更新L*/ MergeSort(L, 1, 100, count1); printf(
"\n归并排序比较次数是:%d\n", count1); printf("归并排序结果:\n"); for (i = 1; i <= 100; i++) {
if (i % 10) printf("%5d", L.R[i]); else { printf("%5d", L.R[i]); printf("\n"); }
} system("pause"); }

技术
©2019-2020 Toolsou All rights reserved,
盘点国产PC操作系统哪家强?机房收费系统之组合查询自定义注解的方式的使用场景:解决业务分发CRC与模二除法的部分理解2021 年了,为什么还有人怀念手机呼吸灯?HVV 2020 | HVV期间漏洞总结「三」PHP中字符串的处理【Java知识点详解 3】序列化与反序列化vue 路由跳转四种方式 (带参数)航拍:特斯拉上海工厂Model Y已经大量下线