數(shù)據(jù)結(jié)構(gòu)-- 遞歸 排序

一.遞歸

一.遞歸的介紹
遞歸是一種數(shù)學(xué)上分而自治的思想
A.將原問題分解為規(guī)模較小的問題進(jìn)行處理
1.分解后的問題與原問題的類型完全相同，但是規(guī)模較小
2.通過小規(guī)模問題的解，能夠輕易求得原問題的解
B.問題的分解時(shí)有限的(遞歸不能無限進(jìn)行)
1.當(dāng)邊界條件不滿足時(shí)，分解問題(遞歸繼續(xù)進(jìn)行)
2.當(dāng)邊界條件滿足時(shí)，直接求解(遞歸結(jié)束)

C.遞歸在程序設(shè)計(jì)中的應(yīng)用
a.遞歸函數(shù)
1.函數(shù)體中存在自我調(diào)用的函數(shù)
2.遞歸函數(shù)必須有遞歸出口(邊界條件)
3.函數(shù)的無限遞歸將導(dǎo)致程序崩潰
示例:

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;
}

二.遞歸的應(yīng)用
單向鏈表的轉(zhuǎn)置

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)//遞歸的實(shí)現(xiàn)
{
    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;
}

二.排序

排序的一般定義
排序時(shí)計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組無序的數(shù)據(jù)元素調(diào)整為有序的數(shù)據(jù)元素

排序的數(shù)學(xué)定義
假設(shè)含n個(gè)數(shù)據(jù)元素的序列為{R1,R2....Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2....，Kn},這些關(guān)鍵字相互之間可以進(jìn)行比較，即:在它們之間存在一個(gè)關(guān)系:Kp1<=Kp2......<=Kpn，將此固有關(guān)系將上式記錄序列重新排列為{Rp1,Rp2....,Rpn}的操作稱為排序
排序的穩(wěn)定性
如果在序列中有兩個(gè)元素r[i]和r[j]，它們的關(guān)鍵字K[i]==K[j],且在排序之前，對(duì)象r[i]排在r[j]前面；如果在排序之后，對(duì)象r[i]仍在r[j]的前面，則稱這個(gè)排序方法是穩(wěn)定的，否則稱這個(gè)排序方法是不穩(wěn)定的
排序的審判
時(shí)間性能
1.關(guān)鍵性能差異體現(xiàn)在比較和交換的數(shù)量
輔助存儲(chǔ)空間‘
1.為完成排序操作需要的額外的存儲(chǔ)空間
2.必要時(shí)可以“空間換時(shí)間”
算法的實(shí)現(xiàn)復(fù)雜性
1.過于復(fù)雜的排序法可能影響可讀性和維護(hù)性
各種排序的實(shí)現(xiàn)
A.選擇排序的基本思想
每次(例如第i次,i=o,1,......n-2)從后面n-i個(gè)待排的數(shù)據(jù)元素中選出關(guān)鍵字最小的元素，作為有序元素序列第i個(gè)元素
圖示

 template <typename T>
        static void select(T array[],int len)
        {
            for(int i=0;i<len;i++)
            {
                int min=i;//從第i個(gè)元素開始

                for(int j=i+1;j<len;j++)//將最小值與剩下的元素進(jìn)行比較
                {
                    if(array[min]>array[j])
                    {
                        min=j;
                    }
                }
                if(min!=i)
                {
                    Swap(array[i],array[min]);

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

插入排序的基本思想
當(dāng)插入第i(i>=1)個(gè)數(shù)據(jù)元素時(shí)，前面的V[0],V[1],...,V[i-1]已經(jīng)排好序，這時(shí)，用V[i]的關(guān)鍵字與V[i-1],V[i-2],...,V[0]關(guān)鍵字進(jìn)行比較，找到位置后將V[i]插入，原來位置上的對(duì)象向后順移

 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]往后移動(dòng)一位
                     {
                        array[j+1]=array[j];
                        k=j;
                     }
                     else
                     {
                         break;
                     }
                 }
                 if(k!=i)
                 {
                     array[k]=temp;
                 }
             }
         }

冒泡排序的基本思想
每次從后向前進(jìn)行(假設(shè)為第i次),j=n-1,n-1,...,i,兩兩比較V[j-1]和V[j]的關(guān)鍵字；如果發(fā)生逆序，則交換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++)//從后往前的實(shí)現(xiàn)
             {
                 exchange=false;

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

希爾排序的基本思想
將待排序列劃分為若干組，在每一組內(nèi)進(jìn)行插入排序，以使整個(gè)序列基本有序，然后再對(duì)整個(gè)序列進(jìn)行插入排序

        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);
         }

歸并排序的基本思想
將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)新的有序序列
有序序列V[0]...V[m]和V[m+1]....V[n-1]====>V[0]...V[n-1]這種歸并方法稱為2路歸并
歸并的套路
1.將3個(gè)有序序列歸并為一個(gè)新的有序序列，稱為3路歸并
2.將N個(gè)有序序列歸并為一個(gè)新的有序序列，稱為N路歸并
3.將多個(gè)有序序列歸并為一個(gè)新的有序序列，稱為多路歸并

         template <typename T>//歸并排序的實(shí)現(xiàn)
         static void Merge(T array[],int len)
         {
             T* helper=new T[len];//申請(qǐng)的輔助空間

             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);
            }
        }

快速排序的基本思想
任取序列在的某個(gè)數(shù)據(jù)元素作為基準(zhǔn)將整個(gè)序列劃分為左右兩個(gè)子序列
1.左側(cè)子序列在中所有元素都小于或等于基準(zhǔn)元素
2.右側(cè)子序列中所有元素都大于基準(zhǔn)元素
3.基準(zhǔn)元素排在這兩個(gè)子序列中間

         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);
            }
        }