数据结构-- 递归 排序

一.递归

一.递归的介绍
递归是一种数学上分而自治的思想
A.将原问题分解为规模较小的问题进行处理
1.分解后的问题与原问题的类型完全相同，但是规模较小
2.通过小规模问题的解，能够轻易求得原问题的解
B.问题的分解时有限的(递归不能无限进行)
1.当边界条件不满足时，分解问题(递归继续进行)
2.当边界条件满足时，直接求解(递归结束)

C.递归在程序设计中的应用
a.递归函数
1.函数体中存在自我调用的函数
2.递归函数必须有递归出口(边界条件)
3.函数的无限递归将导致程序崩溃
示例:

int sum(unsigned int n)
{
    int ret;

    if(n==1)
    {
        ret=1;
    }
    if(n>1)
    {
        ret=n+sum(n-1);
    }

    return ret;
}

int fac(unsigned int n)
{
    if(n>=3)
    {
        return fac(n-1)+fac(n-2);
    }
    if((n==1)||(n==2))
    {
        return 1;
    }

    return 0;
}

二.递归的应用
单向链表的转置

struct Node
{
    int data;
    Node* next;
};

Node* creat(int v,int len)
{
    Node* ret=NULL;
    Node* slider=NULL;

    for(int i=0;i<len;i++)
    {
        Node* n=new Node();

        n->data=v++;
        n->next=NULL;

        if(slider==NULL)
        {
            slider=n;
            ret=n;
        }
        else
        {
            slider->next=n;
            slider=n;
        }
    }

    return ret;
}

void destroy(Node* list)
{
    while(list)
    {
        Node* del=list;
        list=list->next;
        delete del;
    }
}

void print(Node* list)
{
    while(list)
    {
        cout<<list->data<<"->";
        list=list->next;
    }
    cout<<"NULL"<<endl;
}

Node* reserve(Node* list)//递归的实现
{
    Node* ret=NULL;
    if((list==NULL)||(list->next==NULL))
    {
        ret=list;
    }
    else
    {
        Node* guad=list->next;
        ret=reserve(list->next);
        guad->next=list;
        list->next=NULL;
    }
    return ret;
}

单向排序链表的合并

Node* merge(Node* list1, Node* list2)
{
  Node* ret = NULL;
  if(NULL == list1)
  {
    ret = list2;
  }
  else if(NULL == list2)
  {
    ret = list1;
  }
  else if(list1->data < list2->data)
  {
    list1->next = merge(list1->next,list2);
    ret = list1;
  }
  else
  {
    list2->next = merge(list2->next, list1);
    ret = list2;
  }
  return ret;
}

二.排序

排序的一般定义
排序时计算机内经常进行的一种操作，其目的是将一组无序的数据元素调整为有序的数据元素

排序的数学定义
假设含n个数据元素的序列为{R1,R2....Rn}其相应的关键字序列为{K1,K2....，Kn},这些关键字相互之间可以进行比较，即:在它们之间存在一个关系:Kp1<=Kp2......<=Kpn，将此固有关系将上式记录序列重新排列为{Rp1,Rp2....,Rpn}的操作称为排序
排序的稳定性
如果在序列中有两个元素r[i]和r[j]，它们的关键字K[i]==K[j],且在排序之前，对象r[i]排在r[j]前面；如果在排序之后，对象r[i]仍在r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的
排序的审判
时间性能
1.关键性能差异体现在比较和交换的数量
辅助存储空间‘
1.为完成排序操作需要的额外的存储空间
2.必要时可以“空间换时间”
算法的实现复杂性
1.过于复杂的排序法可能影响可读性和维护性
各种排序的实现
A.选择排序的基本思想
每次(例如第i次,i=o,1,......n-2)从后面n-i个待排的数据元素中选出关键字最小的元素，作为有序元素序列第i个元素
图示

 template <typename T>
        static void select(T array[],int len)
        {
            for(int i=0;i<len;i++)
            {
                int min=i;//从第i个元素开始

                for(int j=i+1;j<len;j++)//将最小值与剩下的元素进行比较
                {
                    if(array[min]>array[j])
                    {
                        min=j;
                    }
                }
                if(min!=i)
                {
                    Swap(array[i],array[min]);

                }
                //Swap(arrar[0],arrar[min]);
            }
         }

插入排序的基本思想
当插入第i(i>=1)个数据元素时，前面的V[0],V[1],...,V[i-1]已经排好序，这时，用V[i]的关键字与V[i-1],V[i-2],...,V[0]关键字进行比较，找到位置后将V[i]插入，原来位置上的对象向后顺移

 template <typename T>
         static void insert(T array[],int len)
         {
             for(int i=0;i<len;i++)
             {
                 int k=i;
                 T temp=array[i];
                 for(int j=i-1;j>=0;j--)
                 {
                     if(array[j]>temp)//如果array[j]下的值大于temp,将array[j]往后移动一位
                     {
                        array[j+1]=array[j];
                        k=j;
                     }
                     else
                     {
                         break;
                     }
                 }
                 if(k!=i)
                 {
                     array[k]=temp;
                 }
             }
         }

冒泡排序的基本思想
每次从后向前进行(假设为第i次),j=n-1,n-1,...,i,两两比较V[j-1]和V[j]的关键字；如果发生逆序，则交换V[j-1]和V[j]

         template <typename T>//冒泡排序
         static void Bubble(T array[],int len)
         {
             bool exchange=true;
             for(int i=0;(i<len)&&exchange;i++)//从后往前的实现
             {
                 exchange=false;

                 for(int j=len-1;j>i;j--)
                 {
                     if(array[j]<array[j-1])
                     {
                        Swap(array[j-1],array[j]);
                     }
                 }
             }
         }

希尔排序的基本思想
将待排序列划分为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序

        template <typename T>
         static void Shell(T array[],int len)
         {
             int d=len;

             do
             {
                d=d/3+1;//d为增量 d的值在排序的过程中由大到小逐渐缩小，直至最后一趟排序减为1

                for(int i=d;i<len;i+=d)
                {
                    //cout<<i;
                    int k=i;
                    T temp=array[i];
                    for(int j=i-d;j>=0;j-=d)
                    {
                        if(array[j]>temp)
                        {
                           array[j+d]=array[j];
                           k=j;
                           //cout<<k;
                        }
                        else
                        {
                            break;
                        }
                    }
                    if(k!=i)
                    {
                        array[k]=temp;
                    }
                }
             }while(d>1);
         }

归并排序的基本思想
将两个或两个以上的有序序列合并成一个新的有序序列
有序序列V[0]...V[m]和V[m+1]....V[n-1]====>V[0]...V[n-1]这种归并方法称为2路归并
归并的套路
1.将3个有序序列归并为一个新的有序序列，称为3路归并
2.将N个有序序列归并为一个新的有序序列，称为N路归并
3.将多个有序序列归并为一个新的有序序列，称为多路归并

         template <typename T>//归并排序的实现
         static void Merge(T array[],int len)
         {
             T* helper=new T[len];//申请的辅助空间

             if(helper!=NULL)
             {
                 Merge(array,helper,0,len-1);
             }
         }

                template <typename T>
        static void Merge(T src[],T helper[],int begin,int mid,int end)
        {
            int i=begin;
            int j=mid+1;
            int k=begin;

            while((i<=mid)&&(j<=end))
            {
                if(src[i]<src[j])
                {
                    helper[k++]=src[i++];
                }
                else
                {
                    helper[k++]=src[j++];
                }
            }

            while(i<=mid)
            {
                helper[k++]=src[i++];
            }
            while(j<=end)
            {
                helper[k++]=src[j++];
            }

            for(i=begin;i<=end;i++)
            {
                src[i]=helper[i];
            }
        }

        template <typename T>
        static void Merge(T src[],T helper[],int begin,int end)
        {
            if(begin==end)
            {
                return;
            }
            else
            {
                int mid=(begin+end)/2;

                Merge(src,helper,begin,mid);
                Merge(src,helper,mid+1,end);
                Merge(src,helper,begin,mid,end);
            }
        }

快速排序的基本思想
任取序列在的某个数据元素作为基准将整个序列划分为左右两个子序列
1.左侧子序列在中所有元素都小于或等于基准元素
2.右侧子序列中所有元素都大于基准元素
3.基准元素排在这两个子序列中间

         template <typename T>//快速排序
         static void Quick(T array[],int len)
         {
             Quick(array,0,len-1);
         }

                 template <typename T>
        static int Partiton(T array[],int begin,int end)
        {
            T pv=array[begin];

            while(begin<end)
            {
                while((begin<end)&&(array[end]>pv))
                {
                    end--;
                }
                Swap(array[begin],array[end]);

                while((begin<end)&&(array[begin]<=pv))
                {
                    begin++;
                }
                Swap(array[begin],array[end]);
            }

            array[begin]=pv;

            return begin;
        }

        template <typename T>
        static void Quick(T array[],int begin,int end)
        {
            if(begin<end)
            {
                int pivot=Partiton(array,begin,end);

                Quick(array,begin,pivot-1);
                Quick(array,pivot+1,end);
            }
        }