各种排序算法的整合

相关代码：

#include<iostream>
using namespace std;
//内部排序 插、交、选、归、基

/**
一、插入排序
1）直接插入排序，找到插入位置，插入位置的元素往后移动
2）折半插入排序，是对寻找插入位置的时间复杂度进行的优化，用到分治的思想
相应的每一趟中比较的次数会减少，每趟比较的次数为O(log2n);
3）希尔排序（缩小增量排序）,先追求表中的元素部分有序，在逐渐逼近全局有序
*/
/**
1、直接插入排序
*/
void InsertSort(int a[],int n)
{
    int i,j,temp;
    for(i=1;i<n;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];
            }
            temp=a[j+1];
        }
    }

}
/**
折半插入排序
*/
void BinaryInsertSort(int a[],int n)
{
    int i,j,left,right,mid,temp;
    for(i=1;i<n;i++)
    {
        //待插入元素temp
        temp=a[i];
        left=0;
        right=i-1;
        //我们的任务就是找到比待插入元素小的元素
        while(left<=right)
        {
            mid=(left+right)>>1;
            //当划分元素比待插入元素大，查找左半子表
            if(a[mid]>temp)
                right=mid-1;
            else
                left=mid+1;
        }
        //跳出循环时left>right,我们要插入的位置就是left位置（或者说是right后边的一个元素位置）
        //但要注意的是：往后移动元素时，要从后边开始往后移动，防止元素被覆盖掉
        for(j=i-1;j>=left;j--)//注意i的位置是待插入元素的位置
        {
            a[j+1]=a[j];
        }
        //跳出循环时j=left-1;
        a[j+1]=temp;
    }
}
/**
希尔排序，对间隔为d的元素进行直接插入排序，d在不断的缩小，
init:d=n/2-->d=1,每次d/=2;
不稳定
*/
void ShellSort(int a[],int n)
{
    int i,j,temp,d;
    for(d=n/2;d>=1;d/=2)
    {
        for(i=d;i<n;i++)
        {
            if(a[i]<a[i-d])
            {
                temp=a[i];
                for(j=i-d;j>=0&&a[j]>temp;j-=d)
                {
                    a[j+d]=a[j];
                }
                a[j+d]=temp;
            }
        }
    }
}
/**
二、交换排序
1）冒泡排序
2）快速排序
*/

//冒泡排序
void BubbleSort(int a[],int n)
{
    int i,j;
    //从前往后冒泡
    for(i=0;i<n-1;i++)//需要进行n-1趟冒泡
   {
       bool flag=false;//判断是否发生交换
        for(j=0;j<n-i;j++)
        {
            if(a[j]>a[j+1])
                swap(a[j],a[j+1]);
            flag=true;
        }
        if(flag==false)
            return;
    }
    //从后往前冒泡
//    for(i=0;i<n-1;i++)
//    {
//        bool flag=false;
//        for(j=n-1;j>i;j--)//j>i而且不能等于i，否则下边a[j-1]会出现越界
//        {
//            if(a[j]<a[j-1])
//                swap(a[j],a[j-1]);
//            flag=true;
//        }
//        if(flag==false)
//            return;
//    }

}
/**
快速排序
*/
int Partition(int a[],int left,int right)
{
    int temp=a[left];
    while(left<right)
    {
        while(a[right]>=temp&&left<right)
            right--;
        a[left]=a[right];//将比枢轴小的元素移动到左边
        while(a[left]<=temp&&left<right)
            left++;
        a[right]=a[left];//将比枢轴大的元素移动到右边
    }
    a[left]=temp;
    return left;
}
void QuickSort(int a[],int left,int right)
{
    int pivotpos=Partition(a,left,right);
    if(left<right)
    {
        QuickSort(a,left,pivotpos-1);
        QuickSort(a,pivotpos+1,right);
        return;
    }
}
//整合后的快速排序
//void QuickSort(int a[],int n,int left,int right)
//{
//    int i,j,temp;//temp为枢轴（基准）
//    i=left;
//    j=right;
//    temp=a[left];
//    if(left>right)
//        return;
//    while(i!=j)
//    {
//        while(a[j]>=temp&&i<j)
//            j--;
//        while(a[i]<=temp&&i<j)
//            i++;
//        if(i<j)
//        {
//            swap(a[i],a[j]);
//        }
//    }
//    a[left]=a[i];
//    a[i]=temp;
//    QuickSort(a,n,left,i-1);
//    QuickSort(a,n,i+1,right);
//    return ;
//}
/**
堆排序（heapsort）：
*/
void HeadAdjust(int a[],int k,int n)
{
    //将元素为k的子树进行调整，使得根>=左右孩子
    a[0]=a[k];//用a[0]记录子树的根节点
    for(int i=2*k;i<=n;i*=2)//k为子树的根节点不断向下筛选并调整，使这个子树是个大根堆
    {
        if(a[i]<a[i+1]&&i<n)
            i++;//取关键值较大的子节点的下标
        if(a[0]>=a[i])break;
        else
        {
            a[k]=a[i];//a[i]调整到双亲节点上
            k=i;//更新双亲节点的位置，继续向下筛选
        }
    }
    a[k]=a[0];//被筛选节点的值放入最终位置
}
//建立大根堆
void BuildMaxHeap(int a[],int n)
{
    //i=n/2代表非终端节点的个数
    for(int i=n/2;i>0;i--)
        HeadAdjust(a,i,n);
}

//堆排序
void HeapSort(int a[],int n)
{
    //初始建堆，时间复杂度为O(n)
    BuildMaxHeap(a,n);
    //进行n-1趟的调整
    for(int i=n;i>1;i--)
    {
        swap(a[i],a[1]);//固定堆顶元素
        HeadAdjust(a,1,i-1);//将剩下的i-1个元素整理成堆
    }
}

/**
归并排序
*/
//创建一个动态数组作为辅助数组
int n;
int *b=new int[n];//或者int *b=(int *)malloc(n*sizeof(int))
//归并两个有序表成一个新的有序表
void Merge(int a[],int left,int mid,int right)
{
    //表a[]中的a[left,mid]和a[mid+1,right]两段各自有序，将他们合并成一个有序表
    //将a[]中元素复制到辅助数组中去
    for(int i=0;i<n;i++)
        b[i]=a[i];
    int i,j,k;
    for(i=left,j=mid+1,k=left;i<=mid&&j<=right;k++)
    {
        if(b[i]<=b[j])
            a[k]=b[i++];
        else
            a[k]=b[j++];
    }
    while(i<=mid)
        a[k++]=b[i++];
    while(j<=right)
        a[k++]=b[j++];
}
//归并排序
void MergeSort(int a[],int left,int right)
{
    if(left<right)
    {
        int mid=(left+right)>>1;
        MergeSort(a,left,mid);
        MergeSort(a,mid+1,right);
        Merge(a,left,mid,right);
    }
}
int main()
{
    int a[100];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    MergeSort(a,0,n-1);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}