排序之五：快速排序（C语言实现）

朴灿烈づ我的快乐病毒、 2022-06-14 02:28 179阅读 0赞

快速排序是对冒泡排序进行改进后形成的排序方法。快速排序的基本思想是：取待排序的结点序列中某个结点的值作为控制值，采用某种方式把这个控制值放到适当的位置，使得这个位置的左边的所有结点的值都小于这个控制值，而这个结点位置的右边的所有结点的值都大于这个控制值。

快速排序算法的C语言函数实现如下所示：

/*	快速排序算法的函数实现
     *		array[] : 待排序数组
     *		left    : 数组的最左边的下标
     *		right	: 数组的最右边的下标
     */
    void quick_sort(int array[], int left, int right)
    {
    	int i, j;
    	int temp;		// 用来存放临时的元素值
    	int control;	// 快速排序的控制值
    
    	if(left < right)	// 判断数组下标的界限
    	{
    		i = left;
    		j = right + 1;
    		control = array[left];	// 将最左边的值作为控制值
    		
    		do{
    			do{
    				i++;
    			}while(array[i] < control);
    
    			do{
    				j--;
    			}while(array[j] > control);
    
    			if(i < j)	// 将不符合control值条件的值进行交换
    			{
    				temp     = array[i];
    				array[i] = array[j];
    				array[j] = temp;
    			}
    			
    		}while(i < j);
    
    		/* 确定control值所在元素在序列中的位置 */
    		temp = array[left];
    		array[left] = array[j];
    		array[j] = temp;
    
    		/* 递归进行快速排序 */
    		quick_sort(array, left, j - 1);
    		quick_sort(array, j + 1, right);
    		
    	}
    }

测试的代码实现如下：

/* 程序的入口函数 */
    int main()
    {
    	int a[ARRAY_LENGTH];
    	int i;
    
    	/* 输入10个整形元素 */	
    	printf("Input %d numbers : \n", ARRAY_LENGTH);
    	for(i = 0; i < ARRAY_LENGTH; i++)
    	{
    		scanf("%d", &a[i]);
    	}
    
    	printf("****************************************************************\n");
    
    	/* 把排序前元素都打印出来 */
    	printf("The elements before sort is : \n");
    	for(i = 0; i< ARRAY_LENGTH; i++)
    	{
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    
    	printf("****************************************************************\n");
    
    	/* 对元素进行有小到大的顺序进行排序 */
    	quick_sort(a, 0, ARRAY_LENGTH - 1);
    	
    	/* 把排序后元素都打印出来 */
    	printf("The elements after sort is : \n");
    	for(i = 0; i < ARRAY_LENGTH; i++)
    	{
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    
    	return 0;	
    }

编译并运行结果如下所示：

![SouthEast][]

[SouthEast]: /images/20220614/5887b16f80f14ebc93efbdd451190c68.png