void X_Sort(ElementType A[], int N);
//冒泡排序
void Bubble_Sort(ElementType A[], int N) {
    for(P = N - 1; P >= 0; P--) {
        flag = 0;
        for(i = 0; i < P; i++) {
            if(A[i] > A[i+1]) {
                Swap(A[i],A[i+1]);
                flag = 1;
            }
        }
        if (flag == 0) { break; } //全程无交换
    }
}
//插入排序
void Insertion_Sort(ElementType A[], int N) {
    for(P = 1; P < N; P++) {
        Tmp = A[P];
        for(i = P; i > 0 && A[i-1] > Tmp; i--) {
            A[i] = A[i-1];
        }
        A[i] = Tmp;
    }
}
//选择排序
void Selection_Sort(ElementType A[], int N) {
    for (int i = 0; i < N; i++) {
        MinPosition = ScanForMin(A, i , N - 1);
        Swap(A[i], A[MinPosition]) ;
    }
}
//希尔排序 （by Donald Shell）

void Shel_sort(ElementType A[], int N) {
    for (D = N/2; D > 0; D /= 2) { //希尔增量序列
        for (P = D; P < N; P++) { //插入排序
            Tmp = A[P];
            for (i = P; i >= D && A[i-D] > Tmp; i -= D) {
                A[i] = A[i-D];
            }
            A[i] = Tmp
        }
    }
}
//堆排序
//1
void Heap_Sort(ElementType A[], int N) {
    BuildHeap(A);
    for (i = 0; i < N; i++) {
        TmpA[i] = DeleteMin(A);
    }
    for (i = 0; i < N; i++) {
        A[i] = TmpA[i];
    }
}
//2
void Heap_Sort(ElementType A[], int N) {
    for (i = N/2; i >= 0; i--) {
        PercDown(A, i, N);
    }
    for (i = N - 1; i > 0; i--) {
        Swap(&A[0], &A[i]);
    }
} 
//归并排序
// L左边起始位置， R右边起始位置， RightEnd= 右边终点位置
void Merge(ElementType A[], ElementType TmpA[], int L, int R, int RightEnd) {
    LeftEnd = R - 1;
    Tmp = L;
    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(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);
    }
}

void Merge_sort(ElementType A[], int N) {
    ElementType *TmpA;
    TmpA = malloc(N * sizeof(ElementType));
    if( TmpA != NULL) {
        MSort(A, TmpA, 0, N-1);
        free(TmpA);
    } else Error("空间不足");
}

void Merge(ElementType A[], int L, int R, int RightEnd);
void MSort(ElementType A[], int L, int RightEnd);

//非递归算法
void Merge_pass(ElementType A[], ElementType TmpA[], int N, int length) {
    for (i = 0; i <= N-2*length; i += 2*length) { //当前有序子列的长度
        Merge1(A, TmpA, i, i+length, i+2*length-1);
    }
    if (i + length < N) {
        Merge(A, TmpA, i, i+length, N-1);
    } else {
        for(j = i; j < N; j++) {
            TmpA[j] = A[j];
        } 
    }
}

void Merge_sort (ElementType A[], int N) {
    int length = 1; //初始化子序列长度
    ElementType *TmpA;
    TmpA = malloc(N * sizeof(ElementType));
    if (TmpA != NULL) {
        while(length < N) {
            Merge_pass(A, TmpA, N, length);
            length *= 2;
            Merge_pass(TmpA, A, N, length);
            length *= 2;
        }
        free(TmpA);
    } else {
        Error("空间不足");
    }
}
/*归并排序在外排序中应用*/
//快速排序
void Quicksort(ElementType A[], int Left, int Right) {
    if(Cutoff <= Right-Left) {
        Pivot = Median3(A, Left, Right);
        i = Left; j = Right - 1;
        for (;;) {
            while(A[++i] < Pivot) {NULL;}
            while(A[--j] > Pivot) { NULL;}
            if (i < j) {
                Swap(&A[i], &A[j]);
            } else {
                break;
            }
        }
        Swap(&A[i], &A[Right-1]);
        Quicksort(A, Left, i - 1);
        Quicksort(A, i+1, Right);
} else {
    Insertion_Sort(A+Left, Right-Left+1);
} 
}
ElementType Mediand3(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;
}
void Quick_Sort(ElementType A[], int N) {
    Quicksort(A, 0, N-1);
}
//表排序

//基数排序
//桶排序
void