【数据结构】快速排序

前端之家收集整理的这篇文章主要介绍了【数据结构】快速排序前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

一、快排的几种实现方法

1.左右指针法

a>算法思想:选定数组的最后一个数作为关键值(key),从左边开始遍历找比key大的,从右边找比key小的,找到后交换左右指针,让比key大的数据向后调,比key小的数据调到前面,等到左右指针相等的时候,把数组的最后一位和指针所指位置交换,这样一趟排序过后,key值的前面都是比它小的数,后面都比它大。此时key相当于划分了它左右两个区间,那么两个区间再次分别像刚才一样进行选key交换,会不断的划分新区间,直至区间只包含一个数,就有序了。


单趟排序的图示

我们知道,每次单趟排序之后将数组分为了两个区间,而每个区间也都需要分别排序,故我们可以考虑用递归去实现。

b>优化:假设每一次选的key值都是数组里最大或者最小的数,那快排就会变得很慢很慢,可以认为变成了冒泡排序,所以,key的选取比较关键,我们希望每次选到的是值比较居中的数,所以,key的选取使用三数取中法,即比较区间的第一个数,中间的数和最后一个数,选出值位于中间的数与最后一位交换,因为我们每次取的key是区间的最后一位,这样就尽可能的保证key的值贴近于中间值。

c>时间复杂度:快排每次都会划分区间,直至区间中只有一个数,这一过程跟二叉树结构比较类似,单趟排序交换数的过程近似相当于遍历了这n个数,外层需要高度次递归,故,时间复杂度为O(n*log n).

d>空间复杂度:递归了高度次,即空间复杂度为O(log n)

e>代码实现

//左右指针法
int PartSort(int* a,int begin,int end)  //单趟排序
{
	int left = begin;
	int right = end;
	int mid = GetBestKey(a,begin,end);   //三数取中法得到key
	swap(a[mid],a[end]);
	int key =a[end];
	while (left < right)
	{
		while (left < right && a[left] <= key)
		{
			left++;
		}
		
		while (left < right && a[right] >= key)
		{
			right--;
		}
		if (a[left]>a[right])
		    swap(a[left],a[right]);
			
	}
	swap(a[left],a[end]);
	return left;
}
void QuickSortR(int* a,int end)   //递归版
{
	int mid;
	
	if (begin < end)
	{
		mid = PartSort(a,end);
		QuickSortR(a,mid - 1);
		QuickSortR(a,mid + 1,end);
	}
}
//key取值的优化
int GetBestKey(int* a,int end)   
{
	if ((end - begin) < 1)
		return end;
	int mid = begin + (end - begin) / 2;
	if (a[begin] < a[end])
	{
		if (a[mid] < a[begin])
			return begin;
		else if (a[mid]>a[end])
			return end;
		else
			return mid;
	}
	else
	{
		if (a[end] > a[mid])
			return end;
		else if (a[mid] > a[begin])
			return begin;
		else
			return mid;
	}
}

2.挖坑法

a>算法思想:挖坑法其实和前后指针法也比较相似,区间的最后一个数保存在key里之后,最后一个位置就视为一个坑,先从左边开始找比key大的,找到了放进刚才的坑里,左边又产生了一个新坑,右边找比key小的,找到了填到左边的坑。最后左右相遇于坑处,key放到此处,单趟排序就结束了,之后再递归,和第一种方法一样。所以时间复杂度,空间复杂度和第一种方法一致。

b>优化:对排序整体进行优化,我们知道,当大量数据进行排序时,递归是划算的,可是如果当区间已经被划分的很小的话,不用去递归,改用直接插入排序也很快,因为区间很小,由快排的特性知,此时的小区间接近有序,而接近有序的时候插入排序是O(n)。还节省了快排递归时压栈的开销。(所有的快排方法都可以进行这样的优化)

c>代码实现

//挖坑法进行单趟排序
int PartSort1(int*a,int end)
{
	int mid = GetBestKey(a,end);
	swap(a[mid],a[end]);
	int key = a[end];
	int left = begin;
	int right = end;
	while (left < right)
	{
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[right] = a[left];
		while (left<right && a[right] >= key)
		{
			right--;
		}
		a[left] = a[right];
	}
	a[left] = key;
	return left;
}
void QuickSortR(int* a,int end)   //递归版
{
	int mid;
	
	if (begin < end)
	{
		
		mid = PartSort1(a,end);
		if (end - begin < 4)            //区间数值个数小于4的时候直接插入排序
		{
			InSertSort(a + begin,end - begin + 1);
		}
		mid = PartSort2(a,end);
	}
}

3.前后指针法

a>算法思想:定义两个指针prev和cur,cur指向区间第一个数,prev指向它的前一个。从左向右找比key小的,若当前数比key大,则cur向前移动,直到找到一个比key小的,此时prev向前移动一位,若prev和cur不指向同一位置,则prev所指位置的数值一定比cur大,所以交换prev和cur所指向的数。等到cur指向了最右边的数,再把最后一个数和prev的下一个位置的数交换,一趟排序就结束了。


前后指针法图示

b> 代码实现

//前后指针法
int PartSort2(int*a,int end)
{
	int prev = begin - 1;
	int cur = begin;
	int mid = GetBestKey(a,a[end]);
	int key = a[end];
	while (cur < end)
	{
		while (a[cur] < key && ++prev != cur)
		{
			swap(a[cur],a[prev]);
		}
		++cur;
	}
	swap(a[end],a[++prev]);
	return prev;
}
c>单趟排序后还要继续往下排,之前我们用的都是递归的方法,此处我们把它转化为 非递归,要用到栈。代码如下

void QuickSortNoR(int *a,int end)//非递归
{
	assert(a);
	stack<int> s;
	if (begin < end)
	{
		s.push(end);
		s.push(begin);

		while (!s.empty())
		{
			int left = s.top();
			s.pop();
			int right = s.top();
			s.pop();
			int mid = PartSort2(a,left,right);
			if (mid - 1 > left)
			{
				s.push(mid - 1);
				s.push(left);
			}
			if (right > mid + 1)
			{
				s.push(right);
				s.push(mid + 1);
			}

		}
	}
}
快排的三种方式都理解了之后,个人觉得前后指针法最简单,代码实现起来很容易,同时要注意,如果是大量数据排序的话,最好进行一下方法二里面提到的优化,一是能提高效率,二也能防止不断的递归导致栈溢出。 原文链接:https://www.f2er.com/datastructure/382389.html

猜你在找的数据结构相关文章