(十二)数据结构之快速排序算法实现

傷城~ 2022-06-08 06:29 115阅读 0赞

## 1、快速排序方法 ##

采用分而治之的方法：从待排序元素随机找到一个，以它为中间点，将所有比它大的放在一边，所有比它小的放在另一边，然后每一边在执行和上面相同的步骤。选取中间点（pivot）很关键，如果碰到和pivot相同的元素则停下来交换。

如果数据规模较小：小规模数据的快速排序可能还没有简单排序快，所以可以在程序中设定一个cutoff（阈值），大于它用快速排序，小于它则用简单排序方法比如插入排序。简单排序算法的实现可以参考这篇文章：[http://blog.csdn.net/tech\_pro/article/details/78016096][http_blog.csdn.net_tech_pro_article_details_78016096]。

## 2、具体实现 ##

### 2.1 算法实现 ###

/* 定义快速排序 */
    void Quick_Sort(ElementType A[],int N)
    {
    	Quicksort( A, 0, N-1 );
    }

Quicksort函数为具体排序算法实现主体：

/* 用递归实现，快速排序的核心 */
    static void Quicksort( ElementType A[], int Left, int Right )
    { 
    	int i, j;
    	ElementType Pivot;
    	int Cutoff = 100;
    
    	if(Cutoff <= Right-Left)
    	{
    		Pivot = Median3( A, Left, Right );
    		i = Left; 
    		j = Right - 1;
    
    		for( ; ; ) 
    		{
    			while ( A[ ++i ] < Pivot );
    			while ( A[ --j ] > Pivot );
    			if ( i < j )
    				Swap( &A[i], &A[j] );
    			else
    				break;
    		}
    		Swap( &A[i], &A[ Right-1 ] );
    
    		Quicksort( A, Left, i-1 );
    		Quicksort( A, i+1, Right );
    	}
    	else
    	{
    		Insertion_Sort(A+Left, Right-Left+1);
    	}
    }

它会调用Median3来选择每次排序的中间点，如果待排序数较少可以使用Insertion\_Sort插入排序来进行，Median3的具体实现如下：

/* 求中间点pivot，取传入数组的头、中、尾的中位数 */
    static ElementType Median3( ElementType A[], int Left, int Right )
    { 
    	int Center = ( Left + Right ) / 2;
    
    	/* 目标: A[ Left ] <= A[ Center ] <= A[ Right ] */
    	if ( A[ Left ] > A[ Center ] )
    		Swap( &A[ Left ], &A[ Center ] );
    	if ( A[ Left ] > A[ Right ] )
    		Swap( &A[ Left ], &A[ Right ] );
    	if ( A[ Center ] > A[ Right ] )
    		Swap( &A[ Center ], &A[ Right ] );
    	
    	Swap( &A[ Center ], &A[ Right-1 ] ); 			/* 将pivot藏到右边*/
    	
    	return A[ Right-1 ];
    }

### 2.2 完整示例代码 ###

/* 快速排序 */
    #include <stdio.h>
    
    /* 定义一些辅助数据结构或者类型 */
    typedef int ElementType;
    
    /* 定义一个用于交换的函数 */
    static void Swap(ElementType *a, ElementType *b)
    {
    	ElementType temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    }
    
    /* 插入排序，从小到大排序， */
    void Insertion_Sort( ElementType A[], int N )
    { 
    	int i, P;
    	ElementType Tmp;
    	for ( P=1; P<N; P++ ) 
    	{
    		Tmp = A[P]; 				/* 从第二个元素开始插入*/
    		for ( i=P; i>0 && A[i-1]>Tmp; i-- )
    			A[i] = A[i-1]; 			/* 移出空位*/
    		A[i] = Tmp; 				/* 把后续数据插入到合适的位置上去*/
    	}
    }
    
    
    /* 求中间点pivot，取传入数组的头、中、尾的中位数 */
    static ElementType Median3( ElementType A[], int Left, int Right )
    { 
    	int Center = ( Left + Right ) / 2;
    
    	/* 目标: A[ Left ] <= A[ Center ] <= A[ Right ] */
    	if ( A[ Left ] > A[ Center ] )
    		Swap( &A[ Left ], &A[ Center ] );
    	if ( A[ Left ] > A[ Right ] )
    		Swap( &A[ Left ], &A[ Right ] );
    	if ( A[ Center ] > A[ Right ] )
    		Swap( &A[ Center ], &A[ Right ] );
    	
    	Swap( &A[ Center ], &A[ Right-1 ] ); 			/* 将pivot藏到右边*/
    	
    	return A[ Right-1 ];
    }
    
    
    /* 用递归实现，快速排序的核心 */
    static void Quicksort( ElementType A[], int Left, int Right )
    { 
    	int i, j;
    	ElementType Pivot;
    	int Cutoff = 100;
    
    	if(Cutoff <= Right-Left)
    	{
    		Pivot = Median3( A, Left, Right );
    		i = Left; 
    		j = Right - 1;
    
    		for( ; ; ) 
    		{
    			while ( A[ ++i ] < Pivot );
    			while ( A[ --j ] > Pivot );
    			if ( i < j )
    				Swap( &A[i], &A[j] );
    			else
    				break;
    		}
    		Swap( &A[i], &A[ Right-1 ] );
    
    		Quicksort( A, Left, i-1 );
    		Quicksort( A, i+1, Right );
    	}
    	else
    	{
    		Insertion_Sort(A+Left, Right-Left+1);
    	}
    }
    
    /* 定义快速排序 */
    void Quick_Sort(ElementType A[],int N)
    {
    	Quicksort( A, 0, N-1 );
    }
    
    int main()
    {
    	int i;
    	ElementType temp;
    	ElementType array[10];
    
    	printf("Input 10 numbers : ");
    	for(i = 0; i < 10; i++)
    	{
    		scanf("%d", &temp);
    		array[i] = temp;
    	}
    
    	/* 原始数据输出 */
    	printf("***********************************Origin************************************\n");
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    
    	/* 快速排序后输出 */
    	printf("***********************************Quick*************************************\n");
    	Quick_Sort(array, sizeof(array)/sizeof(array[0]));
    	for(i = 0; i < 10; i++)
    		printf("%d ", array[i]);
    	printf("\n");
    	
    	return 0;
    }

[http_blog.csdn.net_tech_pro_article_details_78016096]: http://blog.csdn.net/tech_pro/article/details/78016096