软件设计师算法之分治法--快速排序_快速排序(分治法) 分数 10 全屏浏览 切换布局 作者 王东 单位 贵州师范学院 快速

                  快速排序也是通过分治法。它的思路是先确定第一个元素的位置，该位置之前的元素全部小于第一个元素，该位置之后的元素全部大于该元素。确定位置后，把数组分为了前后2部分，对这2部分执行递归操作，直达递归到数组为1的大小，即递归到了最底层，即完成了排序过程。

                 比如数组  5, 3，8, 1, 23, 14，首先选取第一个元素为,5，我们现在要确定5的位置。

                 首先，从后面开始和2（待确定位置的元素）比较，14 大于2，往前一个元素为23，仍然大于2，继续往前，直到看到元素1, 1比2小，交换这2个元素，

数组变为： 1 ， 3， 8，5， 23， 14

                 接着，我们从前面开始比较, 3比5小，往后为8，8比5大，交换这2个元素，

 数组变为： 1，3，5，8， 23，14 

                交换后，前后的位置已经重叠了。那么5的位置也确定了。可以看出，5的位置前面的元素都小于5，5后面的元素全部都大于5。对5前后的2部分执行递归操作，即可完成整个排序过程。

                代码如下：

void QuickSort(int data[],int dataLen)
{
	QuickSortHelp(data,0,dataLen-1);
}
 
void Exchange(int dataSrc[],int index1,int index2)
{
	int v = dataSrc[index1];
	dataSrc[index1] = dataSrc[index2];
	dataSrc[index2] = v;
}
 
void static QuickSortHelp(int dataSrc[],int start,int end)
{
	if(start<end)
	{
		int s = start;
		int e = end;
 
		int val = dataSrc[s];//待确定位置的元素,这里选择首个元素
		int valPos = s;
	
		while(s<e)
		{
			//先从最后面开始往前面扫描数组，一一和val比较
			while(s<e)
			{
				if(val<=dataSrc[e])
				{
					e--;
				}
				else
				{
					//待确定位置的元素比后面的大,交换
					Exchange(dataSrc,valPos,e);
					valPos = e;
					break;
				}
			}
			//再从前面开始往后面扫描数组,一一和val比较
			while(s<e)
			{
				if(val>=dataSrc[s])
				{
					s++;
				}
				else
				{
					//待确定位置的元素比前面的小,交换
					Exchange(dataSrc,valPos,s);
					valPos = s;
					break;
				}
			}
		}
 
		//待确定位置的val已经确定为valPos，valPos把数组分为了2半
		//对前后2半执行递归操作，直到划分的数组大小为1，那么都有序，排序递归也就递归到最底层了
		QuickSortHelp(dataSrc,start,valPos-1);
		QuickSortHelp(dataSrc,valPos+1,end);
	}
}