快速排序 递归版本和非递归方法 c代码

快速排序平均时间是T(n) =knln(n)，其中n为待排序序列中记录个数，k为某个常数。通常，快速排序被认为是，在所有同数量级(O(nlogn))的排序方法中，其平均性能最好，但是，若初始记录按关键字有序或者基本有序，快速排序将蜕变为冒泡排序，其时间复杂度为O(n^2)。

快速排序听起来挺简单，实现代码看起来也很简单。但简单只是相对而言，如果不理解其思路的话，现场写代码还是有一定难度，因此需要理解其思想再去写代码。

快速排序答题思路是先将排序序列按照枢轴值分成两个子集，左子集中的元素都小于枢轴值，右子集的元素都大于枢轴值，这里的关键是找到枢轴值的位置。然后使用递归对子集在进行同样的分割操作，递归终点就是子集中元素个数为一。枢轴值可以从序列中随机去一个出来，根据经验，“三者取中”的法则可最大改善快速排序在最坏情况下的性能。“三者取中”即在 arr[ i ],  arr[ j ],  arr[(i + j) / 2]取中值。

举个例子，序列array，长度为N，取枢轴值pivotKey = array[n/2], pivotLoc = n/2，设置两个指针low 和 high，从low开始，找到大于pivotKey的值，假设在i位置（i <  pivotLoc && array[i] > pivotKey），交换pivotLoc和i的值，这时候pivotLoc位置就变为i，这时候从high往前搜索，找到小于pivotLoc的值，然后和pivotLoc交换。如果low < high的话重复上述过程，直到low == high，这时候low == high == pivotLoc。得到两个子集array[0 ~ pivotLoc] 和 array[ pivotLoc +1, high]，递归调用即可，直到子集中元素个数为1返回。

c代码如下：

//两个数值互换
void swap(int *a, int *b)
{
    if (a == b)
        return;
	*a = *a ^ *b;
	*b = *a ^ *b;
	*a = *a ^ *b;
}

void quickSort(int *arr, int low, int high)
{
	int pivotKey, pivotLoc;
	int left = low;
	int right = high;
	if (low < high)
	{
		//保存枢轴点和枢轴值
		pivotLoc = (low + high) / 2;
		pivotKey = arr[pivotLoc];
		while (low < high)
		{
			while (low < pivotLoc && arr[low] <= pivotKey)low++;
			if (low < pivotLoc)
			{
				swap(arr+low, arr+pivotLoc);
				pivotLoc = low;
			}
			
			while(high > pivotLoc && arr[high] >= pivotKey)high--;
			if (high > pivotLoc)
			{
				swap(arr+high, arr+pivotLoc);
				pivotLoc = high;					
			}
		}

		quickSort (arr, left, pivotLoc);
		quickSort (arr, pivotLoc + 1, right);
	}
	return;
}

非递归版本，通常使用的是递归版本的快速排序，但是有时候也会遇到要求实现非递归版本的快速排序。之前听谁说过，递归的问题都可以使用栈来实现。快速排序也是一样。我们分析递归版本的快速排序，快速排序一遍后得到左右两个子集，这时候分别对两个左右子集递归调用快速排序。复又得到左右子集。知道子集中边界元素为1为止。这个过程，可以用栈来模拟，比如，一次排序后，左右子集的边界入栈。如果栈不为空，取出栈的子集边界，调用快速排序。复又得到左右子集边界，进栈。重复此过程，直到栈空。整个过程和树的宽度优先遍历类似。代码如下：

//快速排序，返回枢轴点
int quickSort(int *nums, int begin, int end) 
{
	int pivot, i = begin, j = end;

	pivot = nums[i];

	while (i < j)
	{
		
		while (j > i && nums[j] >= pivot)j--;
		if (j > i)
			swap (nums+j, nums+i);
		else
			break;
		while (i < j && nums[i] <= pivot)i++;
		if (i < j)
			swap (nums+j, nums+i);
		else
			break;		
	}

	return i;
}

void main()
{
	int top = 0, low = 0, high, pivot, stack[100] = {0};
	int nums[] = {10,3,1,8,4,5,2,9,8,6,5};
	int size = sizeof(nums)/sizeof(int);
	high = size - 1;
	
        //第一次快速排序
	pivot = quickSort (nums, 0, size - 1);
	
        //子集边界入栈
	if (pivot - 1 > low)
	{
		stack[top++] = pivot - 1;
		stack[top++] = low;
	}

	if (pivot + 1 < high)
	{
		stack[top++] = high;
		stack[top++] = pivot + 1;
	}

        //从栈中取出边界继续进行快速排序
	while (top > 0)
	{
		low = stack[--top];
		high = stack[--top];
                //复又得到左右边界，继续入栈
		pivot = quickSort (nums, low, high);

		if (pivot - 1 > low)
		{
			stack[top++] = pivot - 1;
			stack[top++] = low;
		}
		
		if (pivot + 1 < high)
		{
			stack[top++] = high;
			stack[top++] = pivot + 1;
		}
	}
}

参考资料：

1. 数据结构 : C语言版/ 严蔚敏，吴伟民编著

=============================================================================================

Linux应用程序、内核、驱动、后台开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。