快速排序的两种实现思路和非递归实现--C++实现

思路一：

       第一种是根据算法导论上的思想：取数组的最后一个元素为主元，i初始化为最低位元素的前一个位置，j指向遍历数组中待排序的元素，当j所指元素比主元小的时候i= i + 1，然后交换i和j所指的元素，j不断遍历，遇到小于主元的就进行交换，这样就能一直维持这样一个序列，i之前的元素(包括i所指元素本身)都是比主元小的元素，i到j之间都是比主元大的元素，j(包括j所指元素)之后都是待排序的元素，最后交换主元和第一个比主元大的元素就可以完成划分。
       算法导论具体介绍如下：
           快速排序是基于分治模式处理的，对一个典型子数组A[p…r]排序的分治过程为三个步骤：

           具体实现快速排序的伪代码：

           具体例子分析详情：

           C++代码实现如下：

++

//1、进行区域的划分
int getPartition(vector<int> &nums, int low, int height)
{
	int keyVal = nums[height];
	int i = low - 1;
	for (int j = low; j < height; j++)
	{
		
		if (nums[j] <= keyVal)
		{
			i = i + 1;
			swap(nums[i], nums[j]);
		}
	}
	swap(nums[i + 1], nums[height]);
	return i+1;
}

//2、递归调用划分区域函数，进行快速排序
void quickSort(vector<int> &nums,int low,int height) {

	if (low<height)
	{
		int mid = getPartition(nums, low, height);
		quickSort(nums, low, mid-1);
		quickSort(nums, mid + 1, height);
	}
}

思路二：

       第二种是严蔚敏的数据结构(C语言版)上的思想：取数组的第一个元素为主元，左(left)、右(height)两指针进行遍历，先右边开始边查找比主元小的（比主元大时height直接减减），找到就直接覆盖左边所指的元素，然后从左边开始查找比主元大的元素，找到就直接覆盖右边所指的元素，依次循环进行。最后low不小于height时把所取的主元付给low所指的位置，完成划分。
       数据结构(C语言版)具体介绍如下：

           具体实现快速排序的伪代码：

           具体例子分析详情：

           C++代码实现如下：

++

//1、进行区域的划分
int getPartition(vector<int> &nums, int low, int height)
{
	int keyVal = nums[low];
	while (low<height)
	{
		while (low < height&&nums[height] >= keyVal)
			height--;
		nums[low] = nums[height];
		while (low < height&&nums[low] <= keyVal)
			low++;
		nums[height] = nums[low];
	}
	nums[low] = keyVal;
	return low;
}

//2、递归调用划分区域函数，进行快速排序
void quickSort(vector<int> &nums,int low,int height) {

	if (low<height)
	{
		int mid = getPartition(nums, low, height);
		quickSort(nums, low, mid-1);
		quickSort(nums, mid + 1, height);
	}
}

最后呈上快速排序的非递归实现：

---

++

void quickSortNonRecursive(vector<int> &nums, int low, int height)
{
	stack<int> s;
	if (low<height)
	{
		int mid = getPartition(nums, low, height);
		if (mid-1>low)
		{
			s.push(low);
			s.push(mid - 1);
		}
		if (mid+1<height)
		{
			s.push(mid + 1);
			s.push(height);
		}
	
		while (!s.empty())
		{
			int qHeight = s.top();
			s.pop();
			int pLow = s.top();
			s.pop();
			int pqMid = getPartition(nums, pLow, qHeight);
			if (pqMid - 1 > pLow)
			{
				s.push(pLow);
				s.push(pqMid - 1);
			}
			if (pqMid + 1 < qHeight)
			{
				s.push(pqMid + 1);
				s.push(qHeight);
			}
		}
	
	}
}

      其实经过测试非递归的算法比递归实现还要慢。 因为递归算法使用的栈由程序自动产生，栈中包含：函数调用时的参数和函数中的局部变量。如果局部变量很多或者函数内部又调用了其他函数，则栈会很大。每次递归调用都要操作很大的栈，效率自然会下降。而对于非递归算法，每次循环使用自己预先创建的栈，因此不管程序复杂度如何，都不会影响程序效率。但是对于上面的快速排序，由于局部变量只有一个mid，栈很小，所以效率并不比非递归实现的低。

      具体的关于快速排序的优化，见文章快速排序优化。