算法 排序 【快速排序】

目录

一、快排思想和时空复杂度

二、举例

三、代码 


一、快排思想和时空复杂度

快速排序是一种交换排序,采用了分治的策略。

基本思想是:

1.先从数列中,取一个数作为基准数pivot,通常我们取区间的第一个元素;

2.创建两个指针,left指针指向待排序列的第一个元素,right指针指向待排序列的最后一个元素。

3.从right指针开始,找到第一个比pivot小的元素,然后让left指针指向的元素等于right指针此时指向的元素;

因为left首次指向的元素是pivot,所以被覆盖了没有关系。

4.然后再从left开始,找到第一个比pivot大的元素,让right指向的元素等于left指向的元素。

因为right指向的元素已经复制了一份到了pivot的前面,所以被覆盖了也没有关系。

5.重复上述操作,直到left=right。

此时将pivot元素放在left和right同时指向的位置即可。

6.这一趟排序将整个待排序列分为了三个子序列:

第一个:[0,pivot-1]

第二个:[pivot]

第三个:[pivot+1,length]

然后,我们再递归地对第一个和第三个子序列进行快速排序即可。

当然我们需要一个递归出口,就是如果left一开始就大于等于了right,那么说明此时区间只有一个元素。

时间复杂度分析:

由于每一次排序我们都需要进行O(N)级别的交换,

而每一次排序都需要将表划分为两个子表,再进行递归

所以递归次数平均下来是O(LOG2N)级别的。

综上,快排的时间复杂度是O(NLOG2N)。

但是,如果刚开始的排序表是逆序的或者基本有序的,就会退化成冒泡排序。

此时的时间复杂度为O(N^2)。

空间复杂度分析: 

由于快排是递归的,需要借助一个递归工作栈,其容量与递归调用的最大深度一致。

最好情况下和平均情况下是O(LOG2N),因为基于二分法;最坏情况是O(N),因为需要进行n-1次递归调用。

二、举例

以一个数组作为示例,取区间第一个数为基准数。

算法 排序 【快速排序】

初始时,i = 0;  j = 9;   X = a[i] = 72

由于已经将 a[0] 中的数保存到 X 中,可以理解成在数组 a[0] 上挖了个坑,可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

数组变为:

算法 排序 【快速排序】

 

i = 3;   j = 7;   X=72

再重复上面的步骤,先从后向前找,再从前向后找。

从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;

从i开始向后找,当i=5时,由于i==j退出。

此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。

数组变为:

算法 排序 【快速排序】

可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。   

 

三、代码 

void quickSort(vector<int>& v,int L,int R)
{
	if (L >= R)
	{
		return;
	}
	int left = L;
	int right = R;
	int pivot = v[left];
	while (left < right)
	{
		//找到右指针指向的第一个比pivot小的元素
		while (left < right && v[right] >= pivot)
		{
			right--;
		}
		if (left < right)
		{
			v[left] = v[right];
		}
		while (left < right && v[left]<=pivot)
		{
			left++;
		}
		if (left < right)
		{
			v[right] = v[left];
		}
		if (left >= right)
		{
			v[left] = pivot;
		}
	}
	quickSort(v, L, right - 1);
	quickSort(v, right + 1, R);
}

 

上一篇:JUnit 假定先决条件


下一篇:昨晚试试 数据行转列,差点翻了车