빠른 정렬, 거품 정렬, 무더기 정렬, 셸 정렬의 귀속과 비귀속 실현

5961 단어 종합 자원
본고는 제가 대충 쓴 테스트 프로그램들이 간단한 사고방식만 제공하고 있습니다. 귀속 조건이 충분하지 않을 수도 있으니 양해해 주십시오!
먼저 가장 간단한 거품 정렬을 소개합니다.
일반적으로 우리의 작법은 다음과 같다(약간 최적화된 후).
void bubble_sort(int a[],int lenth)
{
        if(a==NULL || lenth<1) return ;
        int change=0;
        for(int i=0;i=i;j--)
                {
                        if(a[j]>a[j+1])
                        {
                                a[j]=a[j]^a[j+1];
                                a[j+1]=a[j]^a[j+1];
                                a[j]=a[j]^a[j+1];
                                change=1;
                        }
                }
                if(change==0)return ;

        }
}
그중에 두 개의 순환을 썼다는 것을 알 수 있다.
다음은 순환 대신 하나의 귀속을 사용합니다.
//**************************************************
a -  
lenth -   
index -    i  
**************************************************/
void bubble_sort_cr(int a[],int& lenth,int index)
{
        if(index=index;i--)
              {
                     if(a[i]>a[i+1])
                      {
                              a[i]^=a[i+1];
                              a[i+1]^=a[i];
                              a[i]^=a[i+1];
                      }
             }
                bubble_sort_cr(a,lenth,index+1);
        }
}

그중에 순환이 하나밖에 없다는 것을 알 수 있다.
다음은 순환 변수 대신 귀속 함수를 사용합니다.
/**********************recursion method for bubble sort*******************************
a -  
lenth -   
index -    i  
cur -   i  
***************************************************************************************/
void rc_swap(int a[],int& lenth,int& index,int cur)
{       
        if(index<=cur)
        {       
                if(a[cur]>a[cur+1])
                {       
                        a[cur]^=a[cur+1];
                        a[cur+1]^=a[cur];
                        a[cur]^=a[cur+1];
                }
                rc_swap(int a[],lenth,index,cur-1);
        }
}
void bubble_sort_cr(int a[],int& lenth,int index)
{
        if(index

코드에 순환이 없음을 알 수 있습니다.
다음은 빠른 정렬의 귀속 구현입니다.
// , 
int partition(int a[],int low,int high)
{
        int key=a[low];
        while(low=a[low])low++;
                a[high]=a[low];
        }
        a[low]=key;
        return low;
}
/***************** *******************************/
/**********recursion method ************/
void quick_sort(int a[],int low,int high)
{
        if(low st;


        if(low

무더기 정렬의 귀속과 비귀속은 무더기에 대한 조정 과정에 나타난다
// :
#include 
using namespace std;
typedef void (*HAfun)(int a[],int s,int lenth);
/***************heap sort non recursion*************************
arry - the arrary which we want to sort
s- start index
m- end index
the arry meet with big top heap except arry[s]
so we should adjust the heap to a real big top heap
***************************************************************/
void heapAdjust(int a[],int s,int m)
{
        int rc=a[s];
        for(int j=2*s+1;j<=m;j=2*j+1)
        {
                if(ja[j])break;
                a[s]=a[j];
                s=j;
        }
        a[s]=rc;
}

/**********************heap srot recursion*****************************
arry - the arrary which we want to sort
s- start index
m- end index
the arry meet with big top heap except arry[s]
so we should adjust the heap to a real big top heap
***************************************************************/
void heapAdjust_rcs(int a[],int s,int& lenth)
{
        int largest=s;
        int left=(s<<1)+1;
        int right=(s<<1)+2;
        if(lefta[right]?left:right;
                largest = a[largest]>a[s]?largest:s;
        }
        if(left==lenth)
        {
                largest= a[left]>a[largest]?left:largest;
        }
        if(largest!=s)
        {
                a[s] ^= a[largest];
                a[largest] ^= a[s];
                a[s] ^= a[largest];
                heapAdjust_rcs(a,largest,lenth);
        }

}

/********************************************************************
heapAdjustfun - the function point which can reference to #define 
a - arrary to sort
lenth - the length of arrary
*******************************************************************/
void heapSort(HAfun heapAdjust ,int a[],int& lenth)
{
        for(int i=(lenth-1)/2;i>=0;--i)
        {
                heapAdjust(a,i,lenth-1);
        }
        for(int i=lenth-1;i>=1;--i)
        {
                a[0] ^= a[i];
                a[i] ^= a[0];
                a[0] ^= a[i];
                heapAdjust(a,0,i-1);
        }
}
/************************************************************************/
void print(int a[],int lenth)
{
        for(int i=0;i

셸 정렬은 다음과 같습니다.
void shell_sort(int a[],int lenth)
{
        if(a==NULL||lenth<=1)return ;
        for(int step=lenth/2;step>0;step/=2)
        {
                for(int i=step;i=0 && tmp
양휘 삼각형의 인쇄:
// n  0 - n/2  
#include 
using namespace std;
#define LINE 10
//  n r 
long combi(int n,int r)
{
        if(n

the end !

좋은 웹페이지 즐겨찾기