정렬 1 (정렬 을 직접 삽입 하고 반 으로 접 으 며 정렬 을 삽입 합 니 다. 힐 정렬, 거품 정렬, 빠 른 정렬, 정렬 선택)

#include
#include
#include


/*               
* 1.    （compare）
* 2.      （more）
*/



typedef int KeyType;

//        
typedef struct
{
     
	KeyType key;
	//....        
}RecType;




//       
void swap(RecType& i, RecType& j)
{
     
	RecType tmp;
	tmp = i;
	i = j;
	j = tmp;
}


//------------------------------------------------------    ----------------------------

//    					
/*     n*n；
    
  */
								
void Insert(RecType R[], int n)
{
     
	int i, j;
	RecType tmp;
	for (i = 1; i < n; i++)
	{
     
		if (R[i - 1].key > R[i].key)/*[0,i-1]     ，i       */
		{
     
			tmp = R[i];
			j = i - 1;
			do/*    */
			{
     
				R[j + 1] = R[j];
				j--;
			} while (j >= 0 && R[j].key > tmp.key);	/*                     ，         .
													                 */
			R[j + 1] = tmp;
		}
	}
}




//      
/*
*      n*n，          
    
  */
void BinInsertSort(RecType R[], int n)
{
     
	int i, j, low, high, mid;

	RecType tmp;
	for (i = 1; i < n; i++)
	{
     
		if (R[i].key < R[i - 1].key)
		{
     
			low = 0;
			high = i - 1;
			tmp = R[i];
			while (low <= high)			/*             */
			{
     
				mid = low + high;
				if (tmp.key < R[mid].key)
					high = mid - 1;
				else
					low = mid + 1;
			}
			for (j = i-1;j >= high + 1;j--)/*    */
				R[j + 1] = R[j];
			R[high + 1] = tmp;
		}
	}
}



//    	
/*              ，           */
/*     n 1.3  
*     
*    
*/
void ShellSort(RecType R[], int n)
{
     
	int i, j, d;
	RecType tmp;
	d = n / 2;					/*    */
	while (d > 0)					/*  d  ，          */
	{
     
		for (i = d;i < n;i++)
		{
     
			j = i - d;
			tmp = R[i];
			while (j >= 0 && R[j].key > tmp.key)/*      */
			{
     
				R[j + d] = R[j];
				j = j - d;
			}
			R[j + d] = tmp;
		}
		d = d / 2;					/*       1*/
	}
}


//------------------------------------------------------------------------    --------------------------------------------------

//    
/*     n*n
    
  */
void BubbleSort(RecType R[], int n)
{
     
	int i, j;
	bool exchange;										/*    */
	for (i = 0;i < n - 1;i++)
	{
     
		exchange = false;
		for (j = n - 1; j > i; j--)
		{
     
			if (R[j].key < R[j - 1].key)
			{
     
				swap(R[j], R[j - 1]);
				exchange = true;
			}
		}
		if (!exchange)				/*       ，           */
			return;
	}
}


//    
/*     nlog2n
*     
*    
*/
int partition(RecType R[], int s, int t)		/* i       i 
												 i       i */
{
     
	int i = s, j = t;
	RecType tmp = R[i];
	while (i < j)
	{
     
		while (j > i && R[j].key >= tmp.key)
			j--;
		R[i] = R[j];
		while (i < j && R[i].key <= tmp.key)
			i++;
		R[j] = R[i];
	}
	R[i] = tmp;
	return i;

}

void QuickSort(RecType R[], int s, int t)
{
     
	int i;
	if (s < t)
	{
     
		i = partition(R, s, t);
		QuickSort(R, s, i - 1);			//    
		QuickSort(R, i + 1, t);			//    
	}
}


//    
/*
     n*n
    
  */
void SelectSort(RecType R[], int n)
{
     
	int i, j, k;
	for (i = 0;i < 10;i++)
	{
     
		k = i;
		for (j = i + 1;j < 10;j++)
		{
     
			
			if (R[j].key < R[k].key)		/*         */
				k = j;
		}
		if (k != i)
			swap(R[k], R[i]);
	}
}


//    
void show(RecType R[])
{
     
	int i;
	for (i = 0;i < 10;i++)
		printf("%d  ", R[i].key);
	printf("
");
}


int main()
{
     
	RecType R[10];
	int i;
	
	srand((int)time(NULL));/*       */
	for (i = 0;i < 10;i++)
		R[i].key =rand()%9;
	show(R);
	//Insert(R, 10);
	//BinInsertSort(R, 10);
	//ShellSort(R, 10);					/*       */
	//BubbleSort(R, 10);
	//QuickSort(R, 0,9);
	//SelectSort(R, 10);
	show(R);


	
}