void InsertSort(int *a,int n){    int i,j;    int temp;    for (i=1;i<n;++i)    {        if (a[i]<a[i-1])        {            temp = a[i];            a[i] = a[i-1];            j = i-2;            while(j>=0 && temp<a[j])            {                a[j+1] = a[j];                --j;            }            a[j+1] = temp;        }    }}

void SelectSort(int *a,int n){    int i,j;    int min;    for (i=0;i< n-1;++i)    {        min = i;        for (j=i+1;j<n;++j)        {            if (a[j]<a[min])                min =j;        }        swap(a[min],a[i]);    }}

void BubbleSort(int *a,int n){    int i,j;    for (i=0;i< n-1;++i)    {        for (j=0;j< n-1-i;++j)        {            if (a[j]>a[j+1])                swap(a[j],a[j+1]);        }    }}void BubbleSortBetter(int *a,int n){    int i,j;    bool flag;    for (i=0;i< n-1;++i)    {        flag =true;        for (j=0;j< n-1-i;++j)        {            if (a[j]>a[j+1])            {                swap(a[j],a[j+1]);                flag =false;            }        }        if (flag)            break;    }}void BubbleSortBest(int *a,int n){    int exchange = n-1;    while (exchange)    {        int bound = exchange;        exchange = 0;        for (int i=0;i<bound;++i)        {            if (a[i]>a[i+1])            {                swap(a[i],a[i+1]);                exchange = i;            }        }    }}

int Partition(int *a,int p,int r){    int i=p,j=r;    int x = a[p];    while (i<j)    {        while (i<j && a[j]>=x)            --j;        if (i<j)            a[i++] = a[j];        while (i<j && a[i]<=x)            --i;        if (i<j)            a[j--] = a[i];    }    a[i] = x;    return i;}//算法导论之单项扫描Partition(A,p,r){    x =A[r];    i = p-1;    for j=p to r-1        if A[j]<=x            i = i+1            exchange A[i] with A[j]    exchange A[i+1] with A[r]    return i+1}void QuickSort(int *a,int p,int r){    if (p<r)    {        int q = Partition(a,p,r);        QuickSort(a,p,q-1);        QuickSort(a,q+1,r);    }}

void Merge(int *a,int first,int mid,int last,int *b){    int i= first,j= mid+1;    int k=0;    while (i<=mid && j<=last)    {        if (a[i]<a[j])            b[k++] = a[i++];        else            b[k++] = a[j++];    }    while(i<=mid)        b[k++] = a[i++];    while(j<=last)        b[k++] = a[j++];    for (i=0;i<k;++i)        a[first+i] = b[i];}void MergeSort(int *a,int first,int last,int *b){    if (first<last)    {        int mid = (first+last)/2;        MergeSort(a,first,mid,b);        MergeSort(a,mid+1,last,b);        Merge(a,first,mid,last,b);    }}

void MaxHeapify(int *A,int i,int n){    int l = 2*i+1;    int r = 2*i+2;    int largest;    if(l<n && A[l]>A[i])        largest = l;    else        largest = i;    if(r<n && A[r]>A[largest])        largest = r;    if (largest!=i)    {        swap(A[i],A[largest]);        MaxHeapify(A,largest,n);    }}void BuildMaxHeap(int *A,int n){    for (int i=(n-1)/2;i>=0;--i)        MaxHeapify(A,i,n);}void HeapSort(int *A,int n){    BuildMaxHeap(A,n);    for (int i= n-1;i>=1;--i)    {        swap(A[0],A[i]);        MaxHeapify(A,0,i);    }}