大家一起来排序吧

放假在家的时候,就想总结一下的,大二上学期学了数据结构,现在大二快结束了,估计不总结下就又要还给老师了。

就我了解的排序算法,除了归并排序之外,基本写了写,如有错误之处,还希望各位指正。

同样,排序是一门学问,说起它的用途,算法,太多了,我的视野比较窄,还希望各位前辈能给予补充排序算法。

比如说 补充归并排序,都用手写一写,敲一敲吧。

我把它稍微加工(封装不敢,自己C++比较烂)了下,弄成了一个类,同时用了下模板。

代码文件:Sorting.h--------------类声明文件

Sorting.cpp-------------------类实现文件

Test.cpp-------------------类测试文件

下面上代码:
C/C++ code

//Sorting.h
const int MaxSize=100;
template<class T>
class Sorting
{
    public:
        Sorting(T a[],int n);
        void InsertDirectly();
        void MiddleSearchSort();
        int MiddleSearch(T data[],int low,int high,T value);//折半查找排序的折半查找函数
        void ShellSort();
        void ExchangeSort();
        void QuickSort(int first,int end);
        int Partition(T *pdata,int first,int end);//快排的一次划分算法
        void SelectSort();
        void HeapSort();
        void Sift(T a[],int k,int m);//调整堆算法

        //数据成员,但由于需要在外部访问,故属性设置为public
        int length;//待排序的数的个数
        T data[MaxSize];//待排序的数组
};





C/C++ code

//Sorting.cpp
#include "Sorting.h"
#include <iostream.h>

template <class T>
Sorting<T>::Sorting(T a[],int n)
{
    length=n;
    for (int i=0;i<length;i++)
    {
        data[i]=a[i];
    }
}

template<class T>
void Sorting<T>::InsertDirectly()
{
    //初始化一个b数组,其值从b[1]开始与a[0]相对.b[0]用来设置哨兵
    T *b=new T[length+1];
    for (int i=0;i<length;i++)
    {
        b[i+1]=data[i];
    }
    b[0]=0;
    for (int j=2;j<length+1;j++)
    {
        b[0]=b[j];
        for (int k=j-1;b[k]>b[0];k--)
        {
            b[k+1]=b[k];
        }
        b[k+1]=b[0];
    }
    //输出
    for (int n=1;n<length+1;n++)
    {
        cout<<b[n]<<' ';
    }
    cout<<endl;
}

template<class T>
void Sorting<T>::MiddleSearchSort()
{
    //初始化一个b数组,其值从b[1]开始与a[0]相对.b[0]用来设置哨兵
    T *b=new T[length+1];
    for (int i=0;i<length;i++)
    {
        b[i+1]=data[i];
    }
    b[0]=0;
    //使用折半查找来代替直接插入中的逐个移动
    int low;
    for (int j=2;j<length+1;j++)
    {
        b[0]=b[j];
        low=MiddleSearch(b,1,j-1,b[j]);
        for (int k=j-1;k>=low;k--)
        {
            b[k+1]=b[k];
        }
        b[low]=b[0];
    }
    //输出
    for (int n=1;n<length+1;n++)
    {
        cout<<b[n]<<' ';
    }
    cout<<endl;
}

template<class T>
int Sorting<T>::MiddleSearch(T data[],int low,int high,T value)
{
    int mid;
    while(high>=low)
    {
        mid=(low+high)/2;
        if (value>data[mid])
        {
            low=mid+1;
        } 
        else if(value<data[mid])
        {
            high=mid-1;
        }
        else
        {
            low=mid;
            break;
        }
    }
    return low;

}

template<class T>
void Sorting<T>::ExchangeSort()
{
    T *p=new T[length];
    for (int l=0;l<length;l++)
    {
        p[l]=data[l];
    }
    int exchange=length-1;//用来记录最后交换的位置
    T middleValue;//用于交换值的时候作为中间值
    int bound;//暂存exchange的值
    while(exchange)
    {
        bound=exchange;
        exchange=0;//初始化exchange,如果没有交换则退出循环
        for (int i=0;i<bound;i++)
        {
            //判断前一个和后一个的大小,如果后一个大的话,则交换.
            if(p[i]>p[i+1])
            {
                middleValue=p[i];
                p[i]=p[i+1];
                p[i+1]=middleValue;
                //记录每次交换的位置
                exchange=i;
            }
        }
    }
    for (int j=0;j<length;j++)
    {
        cout<<p[j]<<' ';
    }
    cout<<endl;
}

template<class T>
void Sorting<T>::QuickSort(int first,int end)
{
    int boundary;
    if (first<end)
    {
        boundary=Partition(data,first,end);
        QuickSort(first,boundary-1);
        QuickSort(boundary+1,end);
    }
}
template<class T>
int Sorting<T>::Partition(T *pdata,int first,int end)
{
    T exchangedata;//用于交换时作为中间值
    while(first<end)
    {
        while(pdata[first]<=pdata[end] && first<end) end--;
        if (first<end)
        {
            exchangedata=pdata[first];
            pdata[first]=pdata[end];
            pdata[end]=exchangedata;
            first++;
        }
        while(pdata[first]<pdata[end] && first<end) first++;
        if (first<end)
        {
            exchangedata=pdata[first];
            pdata[first]=pdata[end];
            pdata[end]=exchangedata;
            end--;
        }
    }
    return first;
}
template<class T>
void Sorting<T>::SelectSort()
{
    T *p=new T[length];
    for (int i=0;i<length;i++)
    {
        p[i]=data[i];
    }
    int index;//记录所选择的值
    T data;//用于交换数值时作为中间值
    //一共进行length-1次选择比较
    for (int k=0;k<length-1;k++)
    {
        index=k;
        for (int j=index;j<length-1;j++)
        {
            if (p[index]>p[j+1])
            {
                index=j+1;
            }
        }
        //如果不相同则交换
        if (index!=k)
        {
            data=p[index];
            p[index]=p[k];
            p[k]=data;
        }

    }
    for (int l=0;l<length;l++)
    {
        cout<<p[l]<<' ';
    }
    cout<<endl;
}
/*
template<class T>
void Sorting<T>::HeapSort()
{
    T *p=new T[length];
    for (int j=0;j<length;j++)
    {
        p[j]=data[j];
    }
    T data;//用于交换时的中间值
    //初始建堆,从最后一个非终端节点开始,直到根节点.
    for(int i=length/2-1;i>=0;i--)
        Sift(p,i,length-1);
    //重复执行移走堆顶以及重建堆的操作
    for (int k=0;k<length-1;k++)
    {
        data=p[0];
        p[0]=p[length-1-k];
        p[length-1-k]=data;
        Sift(p,0,length-2-k);
    }
    for (int l=0;l<length;l++)
    {
        cout<<p[l]<<' ';
    }
    cout<<endl;
}
template<class T>
void Sorting<T>::Sift(T a[],int k,int m)
{
    //置i为要筛的节点,j为i的左孩子
    int i,j;
    i=k;j=2*i;
    T data;//用于交换时的中间值
    while(j<=m)
    {
        //比较i的左右孩子,j为较大者
        if (j<m && a[j]<a[j+1])
        {
            j++;
        }
        if (a[i]>a[j])
        {
            //根节点已大于左右孩子中的较大者
            break;
        }
        else
        {
            data=a[i];
            a[i]=a[j];
            a[j]=data;
            i=j;j=2*i;//将节点置于原来节点j的位置
        }
    }
}
*/
template<class T>
void Sorting<T>::HeapSort()
{
    T *p=new T[length+1];
    for (int q=0;q<length;q++)
    {
        p[q+1]=data[q];
    }
    p[0]=0;
    T data;//用于交换时的中间值
    //初始建堆,从最后一个非终端节点开始,直到根节点.
    for(int i=length/2;i>=1;i--)
        Sift(p,i,length);
    //重复执行移走堆顶以及重建堆的操作
    for (int k=1;k<length;k++)
    {
        data=p[1];
        p[1]=p[length+1-k];
        p[length+1-k]=data;
        Sift(p,1,length-k);
    }
    for (int l=1;l<=length;l++)
    {
        cout<<p[l]<<' ';
    }
    cout<<endl;
}
template<class T>
void Sorting<T>::Sift(T a[],int k,int m)
{
    //置i为要筛的节点,j为i的左孩子
    int i,j;
    i=k;j=2*i;
    T data;//用于交换时的中间值
    while(j<=m)
    {
        //比较i的左右孩子,j为较大者
        if (j<m && a[j]<a[j+1])
        {
            j++;
        }
        if (a[i]>a[j])
        {
            //根节点已大于左右孩子中的较大者
            break;
        }
        else
        {
            data=a[i];
            a[i]=a[j];
            a[j]=data;
            i=j;j=2*i;//将节点置于原来节点j的位置
        }
    }
}
template<class T>
void Sorting<T>::ShellSort()
{
    T *p=new T[length+1];
    for (int q=0;q<length;q++)
    {
        p[q+1]=data[q];
    }
    p[0]=0;
    //以增量d进行直接插入排序
    for (int d=length/2;d>=1;d=d/2)
    {
        for (int i=d+1;i<=length;i+=d)//待插入记录每次向后移动d个位置
        {
            p[0]=p[i];//暂存被插入记录
            for (int j=i-d;j>0 && p[0]<p[j];j=j-d)
            {
                p[j+d]=p[j];//记录后移d个位置
            }
            p[j+d]=p[0];
        }
    }
    for (int l=1;l<=length;l++)
    {
        cout<<p[l]<<' ';
    }
    cout<<endl;
}





C/C++ code

//Test.cpp
#include "Sorting.cpp"
#include <iostream.h>
int main()
{
    double dbData[10];
    cout<<"请输入10个double数(用空格分隔):"<<endl;
    for (int i=0;i<10;i++)
    {
        cin>>dbData[i];
    }
    Sorting<double> st(dbData,10);
    cout<<"直接插入排序后:"<<endl;
    st.InsertDirectly();
    cout<<"折半查找排序后:"<<endl;
    st.MiddleSearchSort();
    cout<<"希尔排序之后:"<<endl;
    st.ShellSort();
    cout<<"选择排序后:"<<endl;
    st.SelectSort();
    cout<<"堆排序后:"<<endl;
    st.HeapSort();
    cout<<"交换排序后:"<<endl;
    st.ExchangeSort();
    cout<<"快速排序后:"<<endl;
    st.QuickSort(0,st.length-1);
    for (int j=0;j<st.length;j++)
    {
        cout<<st.data[j]<<' ';
    }
    cout<<endl;
    return 0;
}



下面是程序运行截图:


最后附上一张自己做排序算法比较的图(做得不好,可能有错误。):


大家回复盖楼补排序算法吧!让本贴的排序算法最多!COME ON!!!!!!

作者: xiaopo_poxiao   发布时间: 2011-06-12

郁闷 图小了。来个大的。

下面是程序运行截图:


最后附上一张自己做排序算法比较的图(做得不好,可能有错误。):

上面这张不清楚的话 大家可以右键--图片另存为。保存到自己电脑上看。

好了。大家快点补充排序算法吧!谢谢各位前辈!!!!!!

作者: xiaopo_poxiao   发布时间: 2011-06-12