注:所有的快排针对无重复大量数据是很快的,但是针对有重复大量数据的排序是很慢的;

1.霍尔(hoare)版本

时间复杂度:O(N*logN)

稳定性:不稳定;在fun()函数while判断时一不小心就会存在越界和和死循环问题;

霍尔版本的快排,代码如下:主要实现再func()和quick()函数中

int func(int arr[],int left,int right) {
	int key = left;	//取最左边的值;或最右边的值是一样的;
	while (left < right) {	//相遇就结束了
		//右边找小
		while (left < right && arr[right] >= arr[key])	right--;//越界和死循环问题
		//左边找大
		while (left < right && arr[left] <= arr[key])	left++;
		swap(arr[left], arr[right]);
	}
	//相遇之后,left==right;再交换
	swap(arr[left], arr[key]);//如何保证相遇之时的值比keyi小,因为是right先走的,用它来保证
							//right先走,停下来的位置一定比key小或者相遇,L停下来是相遇或比key大,
							//因为取值是在最左边取的值,已知arr[left]==arr[key];
							//如果left先走,走到相遇,需要再比较一下
							//如果right先走,相遇之时就代表已经没有比key大的了
	return right;
}
void quicksort(int arr[],int begin,int end) {
	if (begin>=end) return; //结束条件判断;
	int key=func(arr, begin, end);
	//[begin,key-1]key[key+1,end]
	quicksort(arr,begin, key - 1);
	quicksort(arr, key + 1, end);
}
int main()
{	
	int a[10] = { 9,8,7,6,5,4,3,2,1,0 };
	int right = sizeof(a) / sizeof(int)-1;
	int left = 0;
	quicksort(a, left, right);	
	for (auto x : a) cout << x << endl;
	return 0;	
}	

2.挖坑法版本

叙述:将key位置(要比较的那个数)的数值保存起来,还是从右边找小,将小的放到坑里,再从左边找大,再放到小的那个坑里,相遇之时再把剩的key值放坑里;左边为坑右边找,右边为坑左边找,相遇之时就是坑,再把key的值放进去

时间复杂度:O(N*logN)

稳定性:不稳定;在fun()函数while判断时一不小心就会存在越界和和死循环问题;

只写实现方法,其余按照霍尔版本的代码写,程序可以照常运行

int func(int arr[],int left,int right) {
	int key = arr[left];	//将要比较的值保存起来;
	int hole = left;	//将坑挖出来
	while (left < right)
	{	//右边找小
		while (left < right && arr[right] >= key) right--;
		arr[hole] = arr[right];
		hole = right;
		//左边找大
		while (left < right && arr[left] <= key)left++;
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	return hole;
}

3.双指针版本

时间复杂度:O(N*logN)

稳定性:不稳定;

int func(int arr[],int left,int right) {
	int key = left;
	int prev = left;
	int cur = left+1;
	while (cur <= right){
		if (arr[cur] < arr[key] && ++prev != cur)swap(arr[prev], arr[cur]);
		cur++;
	}
	swap(arr[prev], arr[key]);
	key = prev;
	return key;
}

 这三种类型的快排,都是以最左边的arr[0]作为判断依据,不停的排序;在实际应用中,可以采取三点取中法来作为比较依据;代码是要改变的;

越无序,重复性越小的数据,使用此三种快排都可以;在实际应用中,就是双指针法最为稳妥;代码量最少

可是对于重复性特别大的数据,一般采用三指针法快排,来操作

力扣:283题,有异曲同工之妙,但是题型和写法完全不同,希望诸君仔细体会;

注:并不是故意的将所有的快排都列为不稳定;而是边界及判断问题,确实是学习的一大难点

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部