end
#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 What is the number of comparisons in direct insertion ：%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 What is the number of Hill sort comparisons ：%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 A random number is ：\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; /* In line sort */ InsertSort(L); printf("\n In line sort results ：\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]; } /* to update L*/ /* Shell Sort */ dita[0] = 5;
dita[1] = 3; dita[2] = 1; ShellSort(L, dita, 3); printf("\n Hill sort results ：\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]; }
/* to update L*/ /* Quick sort */ QSort(L, 1, L.length, count); printf("\n What is the number of quicksort comparisons ：%d\n", count)
; printf(" Quick sort results ：\n"); for (i = 1; i <= 100; i++) { if (i % 10) printf("%5d", L.
R[i]); else { printf("%5d", L.R[i]); printf("\n"); } } /* Merge sort */ for (i = 1; i <=
100; i++) { L.R[i] = L0.R[i]; } /* to update L*/ MergeSort(L, 1, 100, count1); printf(
"\n What is the number of merge sort comparisons ：%d\n", count1); printf(" Merge sort results ：\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"); }

Technology
Daily Recommendation
views 2