빠른 정렬, 거품 정렬, 무더기 정렬, 셸 정렬의 귀속과 비귀속 실현
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 !