大話のデータ構造の迅速なソート

急速な順序付けの基本的な考え方は、順序付けによって記録を独立した2つの部分に分割し、そのうちの一部の記録のキーワードは、他の部分の記録のキーワードよりも小さい場合、それぞれこの2つの部分の記録を並べ替えて、真の順序を達成することができるということである.
高速ソートの時間複雑度:O(nlogn)

#include     
#include 
#include       
#include    
#include   
#define MAX_LENGTH_INSERT_SORT 7 /*                     */
#define MAXSIZE 10000  /*             ，        */
typedef struct
{
	int r[MAXSIZE+1];	/*          ，r[0]          */
	int length;			/*            */
}SqList;

/*   L   r    i j   */
void swap(SqList *L,int i,int j) 
{ 
	int temp=L->r[i]; 
	L->r[i]=L->r[j]; 
	L->r[j]=temp;
}

/***********************************/
/*        *****************/

/*     L      */
void QuickSort(SqList *L)
{ 
	QSort(L,1,L->length);
}

/*     L     L->r[low..high]      */
void QSort(SqList *L,int low,int high)
{ 
	int pivot;
	if(lowr[low..high]    ，     pivot */
			QSort(L,low,pivot-1);		/*           */
			QSort(L,pivot+1,high);		/*           */
	}
}

/*      L      ，       ，         */
/*       ( )      ( )  。 */
int Partition(SqList *L,int low,int high)
{ 
	int pivotkey;

	pivotkey=L->r[low]; /*                */
	while(lowr[high]>=pivotkey)
			high--;
		 swap(L,low,high);/*                 */
		 while(lowr[low]<=pivotkey)
			low++;
		 swap(L,low,high);/*                 */
	}
	return low; /*          */
}


/* **************************************** */

/*        ******************************** */

/*          */
int Partition1(SqList *L,int low,int high)
{ 
	int pivotkey;

	int m = low + (high - low) / 2; /*              */  
	if (L->r[low]>L->r[high])			
		swap(L,low,high);	/*          ，       */
	if (L->r[m]>L->r[high])
		swap(L,high,m);		/*          ，       */
	if (L->r[m]>L->r[low])
		swap(L,m,low);		/*          ，       */
	
	pivotkey=L->r[low]; /*                */
	L->r[0]=pivotkey;  /*          L->r[0] */
	while(lowr[high]>=pivotkey)
			high--;
		 L->r[low]=L->r[high];
		 while(lowr[low]<=pivotkey)
			low++;
		 L->r[high]=L->r[low];
	}
	L->r[low]=L->r[0];
	return low; /*          */
}

void QSort1(SqList *L,int low,int high)
{ 
	int pivot;
	if((high-low)>MAX_LENGTH_INSERT_SORT)
	{
		while(lowr[low..high]    ，     pivot */
			QSort1(L,low,pivot-1);		/*           */
			/* QSort(L,pivot+1,high);		/*           */
			low=pivot+1;	/*     */
		}
	}
	else
		InsertSort(L);
}

/*     L      */
void QuickSort1(SqList *L)
{ 
	QSort1(L,1,L->length);
}

/*     L        */
void InsertSort(SqList *L)
{ 
	int i,j;
	for(i=2;i<=L->length;i++)//i=2
	{
		if (L->r[i]r[i-1]) /*             ：  L->r[i]       */
		{
			L->r[0]=L->r[i]; /*     L->r[0]，     ?*/

			for(j=i-1;L->r[j]>L->r[0];j--)
				L->r[j+1]=L->r[j]; /*      */
			L->r[j+1]=L->r[0]; /*         */
		}
	}
}

/* **************************************** */
#define N 9
int main()
{
   int d[N]={50,10,90,30,70,40,80,60,20};

   SqList l0,l1,l2,l3,l4,l5,l6,l7,l8,l9,l10;
   
   for(int i=0;i