一、基本概念
排序：是指重新排列表中的元素，使得表中的元素按照某个规则有序。
二、评价指标
时间复杂度
空间复杂度
稳定性：稳定性是指排序完成之后，关键字相同的元素是否依然保持原有的顺序
三、排序算法
（一）插入排序
每次将一个待排序的元素插入到前面已经排序完成的子序列中，直到全部元素插入完成。

void InsertSort(int A[],int Len){
    int i,j,temp;
    for(i=1;i<Len;i++)
    {
        if(A[i]<A[i-1])
        {
            temp=A[i];
            for(j=i-1;j>=0&&A[j]>temp;--j)
            {
                A[j+1]=A[j];
            }
            A[j+1]=temp;
        }
    }
}

（二）希尔排序
先追求元素的部分有序，再追求全体有序。

void ShellSort(int A[],int Len){
    int d,i,j;
    for(d=Len/2;d>=1;d=d/2)
    {
        for(i=d+1;i<=Len;++i)
        {
            if(A[i]<A[i-d])
            {
                A[0]=A[i];
                for(j=i-d;j>0&&A[0]<A[j];j-=d)
                {
                    A[j+d]=A[j];
                }
                A[j+d]=A[0];
            }
        }
    }
}

（三）冒泡排序
按一定顺序两两比较相邻元素，决定是否交换。

void BubbleSort(int A[],int Len){
    for(int i=0;i<Len;i++)
    {
        bool flag=false;
        for(int j=Len-1;j>i;j--)
        {
            if(A[j-1]<A[j])
            {
                swap(A[j-1],A[j]);
                flag=true;
            }
        }
        if(flag==false)
        {
            return;
        }
    }
}

（四）快速排序

int Partition(int A[],int low,int high){
    int pivot=A[low];
    while(low<high)
    {
        while(low<high&&A[high]>=pivot)
        {
            high--;
        }
        A[low]=A[high];
        while(low<high&&A[low]<=pivot)
        {
            low++;
        }
        A[high]=A[low];
    }
    A[low]=pivot;
    return low;
}

void QuickSort(int A[],int low,int high){
    if(low<high)
    {
        int pivotpos=Partition(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);
    }
}

（五）简单选择排序

void SelectSort(int A[],int Len){
    for(int i=0;i<Len;i++)
    {
        int min=i;
        for(int j=i+1;j<Len;j++)
        {
            if(A[j]<A[min])
            {
                min=j;
            }
        }
        if(min!=j)
        {
            swap(A[i],A[min]);
        }
    }
}

（六）堆排序

void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];
    for(int i=2*k;i<=len;i*=2)
    {
        if(i<len&&A[i]<A[i+1])
        {
            i++;
        }
        if(A[0]>=A[i])
        {
            break;
        }
        else
        {
            A[k]=A[i];
            k=i;
        }
    }
    A[k]=A[0];
}

void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--)
    {
        HeadAdjust(A,i,len);
    }
}

（七）归并排序

int *B=(int *)malloc(sizeof(int)*len);

void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(k=low;k<=high;k++)
    {
        B[k]=A[k];
    }
    for(i=low,j=mid+1,k=i;i<mid&&j<high;k++)
    {
        if(B[i]<=B[j])
        {
            A[k]=B[i++];
        }
        else
        {
            A[k]=B[j++];
        }
    }
    while(i<=mid)
    {
        A[k++]=B[i++];
    }
    while(j<=high)
    {
        A[k++]=B[j++];
    }
}

void MergeSort(int A[],int low,int high){
    if(low<high)
    {
        int mid=(low+high)/2;
        MergeSort(A,low,mid);
        MergeSort(A,mid+1,high);
        Merge(A,low,mid,high);
    }
}