quicksort.h

来自「八种排序算法」· C头文件 代码 · 共 34 行

//快速排序
//算法思想：设数组a中存放了n个数据元素,;pw为数组的低端下标,high维数组的高端下标,从数组a中任取一个元素(通常取a[low])作为标准,
//调整数组a中各个元素的位置,使排在标准元素面前的元素的关键字均小于标准元素的关键字,排在标准元素后面的元素的关键字均大于等于
//标准元素的关键字。这样一次过程结束后，一方面讲标准元素放在了未来排好序的数组中该表尊元素应位于的未知上，另一方面将数组中
//的元素以标准元素为中心分成了两个子数组,位于标准元素左边子数组中元素的关键字均小于标准元素的关键字，位于标准元素右边子数组
//元素的关键字均大于等于标准元素的关键字。对于这两个子数组中的元素分别再进行方法雷同的递归快速排序。递归算法的出口条件是
//high>low;
//算法实现:
void QuickSort(DataType a[],int low,int high)
//用递归方法对数据元素a[low]……a[high]进行快速排序
{
	int i=low,j=high;
	DataType temp=a[low];		//取第一个元素为标准元素

	while (i<j)
	{
		while(i<j&&temp.key<=a[j].key)	j--;		//在数组的右端扫描
		if(i<j)
		{
			a[i]=a[j];
			i++;
		}
		while (i<j&&a[i].key<temp.key)	i++;		//在数组的左端扫描
		if(i<j)
		{
			a[j]=a[i];
			j--;
		}
	}
	a[i]=temp;

	if(low<i) QuickSort(a,low,i-1);		//对左端子集合进行扫描
	if(i<high) QuickSort(a,j+1,high);	//对右端子集合进行扫描
}