为什么我的快速排序和别人的不一样?

时间:2020-8-2 作者:admin


(对于第一版,错误已经修改了一部分)
首先对于快排,基准数据使用第一个,中间,最后一个,或者随机一个,那么对排序过程有没有影响?
开始之前,我想说今天参加科了大讯飞笔试,碰到一个题,是这样的

/*
*初始数据是25, 84, 21, 47, 15, 27, 68, 35, 20
*经过排序,每趟输出结果如下,让你用这种排序方法去提交
*/
15 20 21 25 47 27 68 35 84 
15 20 21 25 47 27 68 35 84 
15 20 21 25 47 27 68 35 84 
15 20 21 25 35 27 47 68 84 
15 20 21 25 27 35 47 68 84 
15 20 21 25 27 35 47 68 84 

我干开始看到的时候,一想,这肯定是快排吧?毕竟就爱考这,结果我手动走了一遍,???为什么第一趟结果就不一样??
于是我又试了其他几种,没一个对得上,那怎么办?等笔试结束了,同学说就是快排,我???为什么对不上?

初步结论

我们沟通了一下彼此的快排方法,发现真的过程不一样,他用的i,j指针同时找到时才交换,而我用的是没找到一个就交换,导致过程就不一样。
具体区别就是
为什么我的快速排序和别人的不一样?

别人的

附上我实现的代码,分别取第一个,最后一个和中间作为基准,看看结果

public static void kuaipai_mid(int[] a, int low, int high) {
		if (low < high) {
			int i = low, j = high;
			int mid = low + high >> 1;
			int tmp = a[mid];
			a[mid] = a[low];
			a[low] = tmp;
			while(i <j) {
				while (i<j && a[j] >= tmp) {	j--;	}
				while (i<j && a[i] <= tmp) {	i++;	}
				if(i < j) {
					int flag = a[i];
					a[i] = a[j];
					a[j] = flag;
				}
			}
			a[low] = a[i];
			a[i] = tmp;
			Print(a);
			System.out.println();
			kuaipai_mid(a, low, i-1);
			kuaipai_mid(a, i+1, high);
		}
	}
	public static void kuaipai_last(int[] a, int low, int high) {
		if (low < high) {
			int i = low, j = high;
			int tmp = a[high];
			while(i <j) {
				while (i<j && a[i] <= tmp) {	i++;	}
				while (i<j && a[j] >= tmp) {	j--;	}
//				while (i<j && a[i] <= tmp) {	i++;	}
				if(i < j) {
					int flag = a[i];
					a[i] = a[j];
					a[j] = flag;
				}
			}
			a[high] = a[i];
			a[i] = tmp;
			Print(a);
			System.out.println();
			kuaipai_last(a, low, i-1);
			kuaipai_last(a, i+1, high);
		}
	}
	public static void kuaipai(int[] a, int low, int high) {
		if (low < high) {
			int i = low, j = high;
			int tmp = a[low];
			while(i <j) {
				while (i<j && a[j] >= tmp) {	j--;	}
				while (i<j && a[i] <= tmp) {	i++;	}
				if(i < j) {
					int flag = a[i];
					a[i] = a[j];
					a[j] = flag;
				}
			}
			a[low] = a[i];
			a[i] = tmp;
			Print(a);
			System.out.println();
			kuaipai(a, low, i-1);
			kuaipai(a, i+1, high);
		}
	}

结果是

================first=============
15 20 21 25 47 27 68 35 84 
15 20 21 25 47 27 68 35 84 
15 20 21 25 47 27 68 35 84 
15 20 21 25 35 27 47 68 84 
15 20 21 25 27 35 47 68 84 
15 20 21 25 27 35 47 68 84 
================last=============
20 84 21 47 25 27 68 35 15 
20 15 21 47 25 27 68 35 84 
20 15 21 47 25 27 68 84 35 
20 15 21 47 25 68 27 84 35 
20 15 25 47 21 68 27 84 35 
20 15 25 21 47 68 27 84 35 
================mid=============
15 84 21 47 25 27 68 35 20 
15 20 21 25 84 27 68 35 47 
15 20 21 25 84 27 68 35 47 
15 20 21 25 35 27 47 68 84 
15 20 21 25 27 35 47 68 84 
15 20 21 25 27 35 47 68 84 

一第一个数为基准,确实结果一模一样,但是以最后一个数为基准,
以中间为基准,结果是不对的。
那么我想问题是不是出在这里?
为什么我的快速排序和别人的不一样?
因为之前第一个为基准的时候,是从右边开始的,那对于最后一个作为基准,我再从左边开始会怎么样?
结果就是

================last=============
15 20 21 47 25 27 68 35 84 
15 20 21 47 25 27 68 35 84 
15 20 21 27 25 35 68 47 84 
15 20 21 25 27 35 68 47 84 
15 20 21 25 27 35 47 68 84  

答案正确了,过程没对上!!!!!

我的

那我用的方法是什么样的?
我过往的快排学习主要来自三个地方,一、课本,二、菜鸟教程三、各种博客

public static void kuaipai_last(int[] nums, int low, int high) {
		if (low<high) {
			int i = low, j = high;
			int tmp = nums[high];
			while (i < j) {
				while (i<j && nums[i] < tmp) {		i++;	}
				if(i < j)
				nums[j--] = nums[i];
				while (i<j && nums[j] >= tmp) {		j--;	}
				//这里不一样
				if(i < j)
				nums[i++] = nums[j];
			}
			nums[i] = tmp;
			Print(nums);
			System.out.println();
			kuaipai_last(nums, low, i-1);
			kuaipai_last(nums, i+1, high);
		}
	}
	public static void kuaipai(int[] nums, int low, int high) {
		if (low<high) {
			int i = low, j = high;
			int tmp = nums[low];
			while (i < j) {
				while (i<j && nums[j] >= tmp) {		j--;	}
				//这里不一样
				if(i < j)
				nums[i++] = nums[j];
				while (i<j && nums[i] < tmp) {		i++;	}
				if(i < j)
				nums[j--] = nums[i];
			}
			nums[i] = tmp;
			Print(nums);
			System.out.println();
			kuaipai(nums, low, i-1);
			kuaipai(nums, i+1, high);
		}
	}
	public static void kuaipai_mid(int[] nums, int low, int high) {
		if (low<high) {
			int i = low, j = high;
			//在这里需要计算mid,并更low交换一下元素
			int mid = low + high >> 1;
			int tmp = nums[mid];
			nums[mid] = nums[low];
			nums[low] = tmp;
			while (i < j) {
				while (i<j && nums[j] >= tmp) {		j--;	}
				//这里不一样
				if(i < j)
				nums[i++] = nums[j];
				while (i<j && nums[i] < tmp) {		i++;	}
				if(i < j)
				nums[j--] = nums[i];
			}
			nums[i] = tmp;
			Print(nums);
			System.out.println();
			kuaipai_mid(nums, low, i-1);
			kuaipai_mid(nums, i+1, high);
		}
	}

看到这里大家应该明白是哪里不一样了,就是一直是一个坑跟着一个指针在动,输出结果如下

================first=============
20 15 21 25 47 27 68 35 84 
15 20 21 25 47 27 68 35 84 
15 20 21 25 35 27 47 68 84 
15 20 21 25 27 35 47 68 84 
15 20 21 25 27 35 47 68 84
================last=============
15 20 21 47 84 27 68 35 25 
15 20 21 25 84 27 68 35 47 
15 20 21 25 35 27 47 68 84 
15 20 21 25 27 35 47 68 84 
15 20 21 25 27 35 47 68 84 
================mid=============
15 84 21 47 25 27 68 35 20 
15 20 21 25 84 27 68 35 47 
15 20 21 25 84 27 68 35 47 
15 20 21 25 47 27 35 68 84 
15 20 21 25 27 47 35 68 84 
15 20 21 25 27 35 47 68 84   

按照上边别人的方法,以最后一个作为基准时,尝试从左边开始移动,结果如下
为什么我的快速排序和别人的不一样?
(以上代码之前有错误,在大佬指点下,修改了之后用两组数组测试了没问题)

int[] nums = {25, 84, 21, 47, 15, 27, 68, 35, 20};
int[] nums1 = {47, 29, 71, 99, 78, 19, 24, 47};

so?顺序看着还是不一样,但是我这方法也不是奇技淫巧啊,过程为什就是对不上?

展示一下某本书上的快排过程
为什么我的快速排序和别人的不一样?
为什么我的快速排序和别人的不一样?
为什么我的快速排序和别人的不一样?
为什么我的快速排序和别人的不一样?
为什么我的快速排序和别人的不一样?

我用这组数据测一下

用我的奇技淫巧结果对上了
为什么我的快速排序和别人的不一样?
试试之前别人的方法
为什么我的快速排序和别人的不一样?
结果能对上了,但是明显过程也对不上。

此刻我只想微笑表情

看着结果我陷入了沉思,可能是代码也有问题吧,求解答,非常感谢。

总结如下,两种方法目前都学吧,之前学的快排理解还是有问题的,这次完整走了一遍之后,虽然还没理出两种方法到底有没有正统之分,但理得挺清楚了

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。