快速排序遇到的问题

好久没有复习一些基础知识了，正好要找实习了，就想复习一下一些基础的算法。想自己把这些简单算法实现一下，没想到首先在快排这儿遇到问题了。刚开始我的快排代码是这样的：

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}
void QuickSort(int A[], int Left, int Right)
{
		int i, j;
		int mid = (Left + Right) / 2;
		int pivot = A[mid];
		swap(A[mid], A[Right]);
		i = Left - 1;
		j = Right;
		for (;;)
		{
			while (A[++i]<pivot){}
			while (A[--j]>pivot){}
			if (i < j)
				swap(A[i], A[j]);
			else
				break;
		}
		swap(A[i], A[Right]);
		QuickSort(A, Left, i - 1);
		QuickSort(A, i + 1, Right);
	
}

运行，结果stackoverflow，调试了一遍发现代码中j出现了越界的情况，原因是如果pivot是最小的，则j会一直减到小于0，出现了越界的情况，或者pivot最大，i会越界。于是修改代码，在while循环中，增加判断

while (i<j&&A[++i]<pivot){}
 while (j>i&&A[--j]>pivot){}

编译运行，还是出现了stackoverflow的问题，于是再次调试，终于发现在递归调用中出现了Left大于Right的情况。还是考虑pivot是最小值或最大值的情况，此时i和j同时指向了数组最后一个或第一个元素，i==j，于是跳出for循环。接着递归，此时就出现情况了。试想若i和j都指向第一个元素，则i-1出现了越界，若都指向了最后一个元素，则i+1出现了越界，这样程序就在这个地方出现问题了，解决方法是在前面加上Left<Right的判断，这样就解决了越界的问题。正确的代码及测试如下：

#include<iostream>
#include<ctime>
using namespace std;

const int Num = 200;
void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}
void QuickSort(int A[], int Left, int Right)
{
	if (Left < Right)
	{
		int i, j;
		int mid = (Left + Right) / 2;
		int pivot = A[mid];
		swap(A[mid], A[Right]);
		i = Left - 1;
		j = Right;
		for (;;)
		{
			while (i<j&&A[++i]<pivot){}
			while (j>i&&A[--j]>pivot){}
			if (i < j)
				swap(A[i], A[j]);
			else
				break;
		}
		swap(A[i], A[Right]);
		QuickSort(A, Left, i - 1);
		QuickSort(A, i + 1, Right);
	}
}
void PrintArray(int A[], int n)
{
	if (n >= 0)
	{
		for (int i = 0; i < n; i++)
		{
			cout << A[i] << "  ";
			if (1 % 10 == 0)
				cout << endl;
		}	
	}
}
int main()
{
	int A[Num];
	int i;
	srand((unsigned)time(NULL));
	for (i = 0; i < Num; i++)
		A[i] = (rand() % 100);
	QuickSort(A, 0, Num - 1);
	PrintArray(A, Num);
	system("pause");
}

总结：快排是一个用途非常广泛而且很“快”的排序方法，实现起来也很简单，可是如果不注意的话很容易出现数组越界，递归陷入死循环的问题，这个就要求对算法的实现原理非常清楚，在下标操作时注意数组越界的问题，否则就非常容易出现堆栈溢出的问题。

最后

以上就是可爱河马为你收集整理的快速排序遇到的问题的全部内容，希望文章能够帮你解决快速排序遇到的问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。