算法–快速排序 以及三路划分算法

算法—快速排序 以及三路划分排序

一般的快速排序:

思路:

1.一般选取最右边的值为pivot

2.从左端开始扫描,直到找到大于pivot,右端开始扫描,直到小于pivot,再交换。

3.继续执行2,直到左指针不小于右指针,最后在减缓左元素和pivot

4.在左右两边重复上面过程,直至元素个数为0或者1

一般的快速排序,无法解决和pivot大量重复的情况,这里就需要用到了三路划分。

三路划分快速排序: 平均时间复杂度O(NlgN)

基本思想是将区间划分为三个部分,左部分小于划分元素,中间部分等于划分元素,右部分大于划分元素,然后再在左右两部分进行子处理,

  1. 选择左端元素、右端元素和中间元素的中值作为pivot,也就是三者取中划分,避免最坏。
  2. 从左端开始扫描,直到找到大于等于pivot的元素,同时右端开始扫描,直到找到小于等于pivot的元素,交换停止扫描的两个元素。如果左指针等于pivot,与左边元素交换。并递增左边位置(初始化为文件最左位置)。如果右指针元素等于划分元素,那么与右端元素交换,并递减右端位置(初始化为文件最右位置)。
  3. 继续步骤2. 直到左指针不小于右指针
  4. 交换最左端区间和左指针左侧区间(不包括左指针元素),这一过程会递减左端位置;交换最右端区间和左指针右侧区间(包括左指针元素),这一过程会递增右端位置。
  5. 在最左端和最右端区间重复以上过程,直至元素个数为0或1。

划分过程中,与划分元素相等的元素分布在最左端和最右端,

在划分完成后处理子区间前,需要对调区间。

void quick_sort(int[] a,int _first,int _last){
	if(_first<_last-1){
		return;
	}

	int i=_first,j=_last-1,p=i,q=j,k;
	//1.三路划分 pivot取第一个、最后一个、中间数的中值;
	int pivot=_median(a[0],a[a.length-1],a[(a.length-1)/2]);

	while(true){
		//2.左边开始直到找到一个大于等于pivot的数值,右边开始查找,直到找到小于等于pivot的数值,交换
		while(a[i]<pivot){
			i++;
		}
		while(a[j]>pivot){
			j--;
		}

		if(!(i<j)){
		   break;
		}

		swap(a[i],a[j]); 

		//3.交换后,如果a[i]==pivot,那么a[i]和最左边元素a[p]位置交换,交换后p+1,
		if(a[i]==pivot){
			swap(a[p++],a[i]);
		}
		if(a[j]==pivot){
			swap(a[q--],a[j]);
		}

		//4.移动一位,进行继续比较
		++i;
		--j;
	}

	//5.第一轮比较结束,i==j, 子模块划分前,先进行区域交换。
	j=i-1;
	for(k=_first;k<p;--j,++k){
		swap(a[k],a[j]);
	}
	for(k=_last-1;k>q;++i,--k){
		swap(a[k],a[i]);
	}

	quick_sort(_first,j+1);
	quick_sort(i,_last);
}
Advertisements
算法–快速排序 以及三路划分算法

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s