欢迎大家来到IT世界,在知识的湖畔探索吧!

#头条创作挑战赛#

前言

  上文写到了快速排序的前置知识：快速排序（一）荷兰旗问题，这里开始正式学习快速排序。

初始快速排序

  假设我有这样一个数组，以数组的末尾值X作为划分的值，小于X的放在数组的左边，大于X的放在数组的右边。这样的话X处于中间位置对于整个数组来说X有序了，X就不用动了，然后继续这样操作左组和右组，每次操作，都会有固定的值处于中间位置排好序，这样只要完成这个递归就可以完成对数组的排序了。

  这样的话基于荷兰旗问题，每次排序之后，我只要得到等于X的左右下标，就可以基于这个下标，继续递归操作左右数组。

代码思路

• 我需要一个荷兰旗操作的方法，返回等于X的下标数组dx
• 我需要一个递归的方法
• 左组以L到dx[0]-1
• 右组以dx[1]+1到R
• 注意递归结束条件，L>=R

❤️代码实现

	/**	 * 快速排序入口	 * @param arr	 */	public static void kspxrk(int[] arr) {		if (arr == null || arr.length < 2) {			return;		}		kspx(arr, 0, arr.length - 1);	}	/**	 * 递归实现	 * @param arr	 * @param L	 * @param R	 */	public static void kspx(int[]arr,int L,int R) {		//考虑递归结束条件		if(L>=R) {			return;		}		int[] dx = hlqcz(arr, L, R);		kspx(arr, L, dx[0]-1);		kspx(arr, dx[1]+1, R);	}	/**	 * 荷兰旗问题操作	 * @param arr	 * @param L	 * @param R	 * @return	 */	public static int[] hlqcz(int[] arr , int L ,int R ) {		// L大于R 的时候，越界了		if(L>R) {			return new int[] {-1,-1};		}		//L == R 的时候，左边结束，右边也结束了		if(L==R) {			return new int[] {L,R};		}		//左边界		int less = L - 1;		//右边界		int more = R;		//当前下标,从左开始		int index = L;		//当前下标，碰触右边界结束		while (index<more) {			if(arr[index]==arr[R]) {				//如果当前值 和 最右位置值相等，最右位置值作为划分值，当前下标+1，数据不动				index++;			}else if(arr[index]<arr[R]) {				//如果当前值 小于 划分值，当前值和左边界+1的值交换，然后左边界+1，当前下标+1				swap(arr, index++, ++less);			}else {				//如果当前值 大于 划分值，当前值和右边界-1的值交换，然后有边界-1，当前下标不动				swap(arr, index, --more);			}		}		//当前下标碰到右边界了		//当前位置的值和R位置的值进行交换，R位置的值是划分值，也就是说它一定在中间		swap(arr, more, R);		//返回中间的值的下标		return new int[] {less+1,more};	}	/**	 * 数组的l位置的数 和 R位置的数，交换	 * @param arr	 * @param l	 * @param r	 */	public static void swap (int[] arr,int l ,int r) {		int t = arr[l];		arr[l] = arr[r];		arr[r] = t;	}

欢迎大家来到IT世界,在知识的湖畔探索吧!

快速排序进阶–随机快排

  上面我们用到的数组，用最右侧的数作为划分值，那么就有极端值，最右侧值最大或最小，以及刚好是中间，复杂度分别是O(N^2) 和O（N*logN）,那么为了减少复杂度，就有了随机快排，也就是我随机选一个值，放在最右侧作为划分值。

❤️代码实现

欢迎大家来到IT世界,在知识的湖畔探索吧!	/**
	 * 随机快排
	 * @param arr
	 * @param L
	 * @param R
	 */
	public static void kspxrk2(int[] arr, int L, int R) {
		if (L >= R) {
			return;
		}
		//L-R区间随机一个位置的数和R位置的数交换
		swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
		int[] equalArea = hlqcz(arr, L, R);
		kspx(arr, L, equalArea[0] - 1);
		kspx(arr, equalArea[1] + 1, R);
	}