ACM总结（各类排序的实现）

其中最基础的有直接插入排序，简单选择排序与冒泡排序，不用多说了。
希尔排序：
先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。
快速排序：
其实是起泡排序的一种改进，它解决了起泡排序中只有相邻元素之间才能交换的问题。它首先确定一个轴值（pivot(它是比较的基准)），将待排序记录划分成两部分，左侧记录均小于或等于轴值，右侧记录均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。
堆排序：
首先将待排序序列调整成一个堆，此时，选出了堆中所以记录的最大者即堆顶的记录，将堆顶记录移走，然后将剩余记录再调整成堆，重复上述操作，直到堆中只有一个记录。
归并排序：
将若干个有序序列逐步归并，最终归并为一个有序数列。（有待学习emmm~）
可添加swap()函数，使得代码更简洁

void swap(int a,int b)
{
int temp;
temp=a;
a=b;
b=temp;
}

这是以下排序的时间性能：

#include 
#include 
#include 
#include 
#include 
using namespace std;
class Sort{
public :
    Sort(int r[],int n);//构造函数，生成待排序数列
    ~Sort();//析构函数
    //插入排序：
    void InsertSort();//直接插入排序
    void ShellSort();//希尔排序
    //交换排序：
    void BubbleSort();//冒泡排序
    void QuickSort(int first,int last);//快速排序
    //选择排序：
    void SelectSort();//简单选择排序
    void HeapSort();//堆排序
    //归并排序：
    void MergeSort1(int first,int last);//二路归并递归排序
    void MergeSort2();//二路归并非递归排序
    void Print();//输出
private:
    int Partition(int first,int last);//快速排序，一次划分
    void Sift(int k,int last);//堆排序，堆调整
    void Merge(int first1,int last1,int last2);//归并排序，合并相邻有序数列
    void MergePass(int h);//归并排序，一趟归并
    int *data;//待排序数列
    int length;
};
Sort::Sort(int r[],int n){
data=new int[n];
for(int q=0;q=0&&temp=1;d=d/2)//增量为d进行直接插入排序
{
for(i=d;i=0&&tempdata[j+1]){
    temp=data[j];data[j]=data[j+1];data[j+1]=temp;
    exchange=j;//记录每一次交换的位置
}}}}
//
int Sort::Partition(int first,int last){
    int i=first,j=last,temp;//初始化一次划分的区间
    while(i=last)return;//区间长度为1，递归结束
    else{
        int pivot=Partition(first,last);//一次结束
        QuickSort(first,pivot-1);//对左侧子序列进行快速排序
        QuickSort(pivot+1,last);//对右侧子序列进行快速排序
        }
    }
//简单选择排序：
void Sort::SelectSort(){
    int i,j,index,temp;
    for(i=0;idata[j]){break;}//已经是堆
        else{
            temp=data[i];
            data[i]=data[j];
            data[j]=temp;
            i=j;
            j=2*i+1;//被调整结点位于结点j的位置
            }
        }
    }
void Sort::HeapSort(){
    int i,temp;
    for(i=ceil(length/2)-1;i>=0;i--)//从最后一个分支结点至根节点调整
    {Sift(i,length-1);}
    for(i=1;i>n;
    fill_n(a,n+5,0);
    for(int q=0;q>a[q];
    }
    Sort l(a,n);
    //l.ShellSort();
    //l.InsertSort();
    //l.BubbleSort();
    //l.QuickSort(0,n-1);
    //l.SelectSort();
    //l.HeapSort();
    //l.MergeSort1(0,n-1);
    l.MergeSort2();
    l.Print();
    return 0;
}

继续加油吧！