排序算法（练习）

/*
 *排序算法练习
 */

#include <iostream>    //注意C++头文件格式


#define OK 0
#define ERR -1

typedef int ElemType;
typedef int Status;

using namespace std;    //运用空间的书写格式


Status InsertSort(ElemType* r,int len)
{
    int i=0,j=0;

    for(i=2;i<=len;i++)    //要进行len-1次比较

    {
        if(r[i]<r[i-1])
        {
            r[0] = r[i];
            r[i] = r[i-1];    //有序数列最后一个元素后移，这是因为他已经和a[0]比较过了；流出空位，为a[0]插入做准备


            for(j=i-2;r[0]<r[j]&&j>0;j--)    //和哨兵r[0]相比较，大，则后移位

            {
                r[j+1]=r[j];    //有序数列向后移位

            }
            r[j+1]=r[0];
        }

    }

    return OK;
}

Status BubbleSort(ElemType* a,int len)
{
    ElemType tmp;    //用于交换数据

    int i,j;

    for(i=0;i<len;i++)    //一共要冒泡len次

    {
        for(j=1;j<len-i;j++)    //每次冒泡要比较len-i-1次,书上有错误,注意数组下标的范围

        {
            if(a[j-1]>a[j])
            {
                tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
            }
        }
    }

    return OK;
}

//对数组进行分区操作,返回分区点

int Patition(ElemType* r,int low,int high)
{
    r[0] = r[low];    //保护r[low]

    int pivotpos;
    ElemType pivotkey;
    pivotkey = r[low]; //将第一个元素作为轴点，保存到轴点中


    //开始分区

    while(low<high)
    {
        //取出高位上小于轴点的数

        while(r[high]>=pivotkey && low<high)
        {
            high--;
        }
        r[low] = r[high];    //高位小元素放到地位轴点位置


        //取出地位

        while(r[low]<=pivotkey && low<high)
        {
            low++;
        }
        r[high] = r[low];    //地位大元素放到高位轴点位置

    }
    r[low] = r[0];        //保护数据放入合适的位置


    pivotpos = low;    //找到了分区点


    return pivotpos;
}

//快速排序法

Status QuickSort(ElemType* r,int low,int high)
{
    int pos;    //定义曲轴位置

     if(low<high)    //递归限制条件

    {
        pos = Patition(r,low,high);

        QuickSort(r,low,pos-1);    //低数区递归


        QuickSort(r,pos+1,high);    //高数区递归

    }

    return OK;
}

Status ShellSort(ElemType* r,int len)
{
    int i,j,dk;

    for(dk=len/2;dk>0;dk--)    //增量递减

    {
        for(i=dk+1;i<=len;i++)
        {
            //进行一次插入法排序

            if(r[i]<r[i-dk])
            {
                r[0]=r[i];    //暂存r[i]

                //r[i]=r[i-dk];    //后移


                for(j=i-dk;r[0]<r[j] && j>0;j-=dk)
                {
                    r[j+dk]=r[j];
                }
                r[j+dk] = r[0];
            }
        }

    }

    return OK;
}

void main()
{
    int i=0,j=0,len=0;
    ElemType a[20],r[21],tmp;

    cout<<"请输入要排序的数：（CTRL+Z ENTER结束）"<<endl;
    while(scanf("%d",&tmp) != EOF)
    {
        a[i] = tmp;
        printf("Input data: %d \n",a[i]);    //scanf和printf对应使用

        r[i+1] = a[i];    //创建头空数组，为插入排序，快速排序做准备；r[0]作为辅助单元


        i++;
        len++;
    }
//    len-=1;


    //下面开始各种排序

/*
    //1、插入排序
    if(!InsertSort(r,len))    //元素个数与数组下表区别好啊
    {
        //打印排序后的数组
        for(i=1;i<=len;i++)
        {
            cout<<"排序后数据:"<
        }
    }
*/
/*
    //2、冒泡算法-BubbleSort
    if(!BubbleSort(a,len))    //元素个数与数组下表区别好啊
    {
        //打印排序后的数组
        for(i=0;i
        {
            cout<<"排序后数据:"<
        }
    }
*/
/*
    //3、快速排序法练习
    if(!QuickSort(r,1,len))    //元素个数与数组下表区别好啊
    {
        //打印排序后的数组
        for(i=0;i
        {
            cout<<"排序后数据:"<
        }
    }
*/

    //4、Shell排序算法

    if(!ShellSort(r,len))    //元素个数与数组下表区别好啊

    {
        //打印排序后的数组

        for(i=1;i<=len;i++)
        {
            cout<<"排序后数据:"<<r[i]<<endl;
        }
    }

}

 sort.rar