完成程序 1.voidInsertionSort(ElementTypeA[],intN) 2.voidBubbleSort(ElementTypeA[],intN) 3.ElementTypeMedian3(ElementTypeA[],intLeft,intRight) voidQsort(ElementTypeA[],intLeft,intRight) 4.voidMerge(ElementTypeA[],ElementTypeTmpA[],intL,intR,intRightEnd) voidMsort(ElementTypeA[],ElementTypeTmpA[],intL,intRightEnd)
时间: 2024-02-26 15:54:47 浏览: 13
1. void InsertionSort(ElementType A[], int N) {
int j, P;
ElementType Tmp;
for (P = 1; P < N; P++) {
Tmp = A[P];
for (j = P; j > 0 && A[j - 1] > Tmp; j--)
A[j] = A[j - 1];
A[j] = Tmp;
}
}
2. void BubbleSort(ElementType A[], int N) {
int P, i, flag = N;
ElementType Tmp;
while (flag > 0) {
P = flag;
flag = 0;
for (i = 1; i < P; i++) {
if (A[i - 1] > A[i]) {
Tmp = A[i];
A[i] = A[i - 1];
A[i - 1] = Tmp;
flag = i;
}
}
}
}
3. ElementType Median3(ElementType A[], int Left, int Right) {
int Center = (Left + Right) / 2;
if (A[Left] > A[Center])
Swap(&A[Left], &A[Center]);
if (A[Left] > A[Right])
Swap(&A[Left], &A[Right]);
if (A[Center] > A[Right])
Swap(&A[Center], &A[Right]);
Swap(&A[Center], &A[Right - 1]);
return A[Right - 1];
}
void Qsort(ElementType A[], int Left, int Right) {
int i, j;
ElementType Pivot;
if (Right - Left >= Cutoff) {
Pivot = Median3(A, Left, Right);
i = Left;
j = Right - 1;
for (;;) {
while (A[++i] < Pivot) {}
while (A[--j] > Pivot) {}
if (i < j)
Swap(&A[i], &A[j]);
else
break;
}
Swap(&A[i], &A[Right - 1]);
Qsort(A, Left, i - 1);
Qsort(A, i + 1, Right);
} else
InsertionSort(A + Left, Right - Left + 1);
}
4. void Merge(ElementType A[], ElementType TmpA[], int L, int R, int RightEnd) {
int LeftEnd = R - 1;
int Tmp = L;
int NumElements = RightEnd - L + 1;
while (L <= LeftEnd && R <= RightEnd) {
if (A[L] <= A[R])
TmpA[Tmp++] = A[L++];
else
TmpA[Tmp++] = A[R++];
}
while (L <= LeftEnd)
TmpA[Tmp++] = A[L++];
while (R <= RightEnd)
TmpA[Tmp++] = A[R++];
for (int i = 0; i < NumElements; i++, RightEnd--)
A[RightEnd] = TmpA[RightEnd];
}
void Msort(ElementType A[], ElementType TmpA[], int L, int RightEnd) {
int Center;
if (L < RightEnd) {
Center = (L + RightEnd) / 2;
Msort(A, TmpA, L, Center);
Msort(A, TmpA, Center + 1, RightEnd);
Merge(A, TmpA, L, Center + 1, RightEnd);
}
}