Java 快排三指针扫描代码解说

关于快排的前两种我就不描述了，主要讲讲三指针扫描分区的思路讲解跟代码实现。

例如

[2, 4, 9, 7, 5, 6, 4, 3, 2, 2, 2 , 20, 23, 56, 0, 1, 1, 2]
变为
[0, 1, 1, 2, 2, 2, 2, 2, 4, 9, 7, 5, 6, 4, 3, 20, 23, 56 ]
传入迭代的两个数组分别为[0, 1, 1,] 和 [4, 9, 7, 5, 6, 4, 3, 20, 23, 56 ]
所以省去了重复比较5个2元素的时间

我的思路比较死脑经（利用双指针扫描的方法）

设置三个数组下标指针，e（重复元素的起点位置），left，right，设置一个标志flag = 0；

当没有与主元（用来分区的元素，通常是数组第一个）相同的元素时，就是正常的双指针扫描，注意的是e指针跟着left前进


当第一次遇到 arr【left】 = 主元 时

1. 此时 e指针 赋值 为 left
2. 标志位 flag = 0；
3. 并且left像右移动；

					e = left;
					flag = 1;
					left++;

或者当第一次遇到 arr【right】 = 主元 时
交换left位 与 right 元素并且right像左移动；

					swap(arr, left, right);
					right--;

当发现了主元 有 重复 元素后
left指针向右扫描
当遇到 arr[left] < 主元 时
或当arr[left] = 主元right指针向左扫描

	while (arr[left] <= privot) {
			if (arr[left] < privot) {
				swap(arr, left, e);//交换e指针与left指针元素的位置，
				e++;               //e指针向右移
				left++;            //left指针向右移
			}else if (arr[left] == privot) {
				left++;        //left指针向右移
			}
			}
			while(arr[right] > privot) {  //right指针向==左==扫描
				right--;
			}
			//  left指针 找到 大于 主元元素     并且     right指针  找到 小于主元元素时 交换
			swap(arr, right, left);
		

技术条件： 当 left < right 时

//三元素 e s bigger 划分
	public static void quickSort1(int[] arr, int p, int r) {
		if (p < r) {
			int e = partition3(arr, p, r).get(0);
			int bigger = partition3(arr, p, r).get(1);
			quickSort(arr, p, e-1);
			quickSort(arr, bigger+1, r);
		}
	}

//三指针扫描 
		public static Map partition3(int[] arr, int p, int r) {
			Map map = new HashMap();
			int privot = arr[p];
			int e = p+1;
			int left = p+1;
			int right = r;
			int flag = 0; 
			while (left <= right) {
				
				
				if (flag == 0 && arr[left] != privot) {
					while (left <= right && arr[left] < privot) {
						left++;
						e++;
					}
					while (left <= right && arr[right] > privot) {
						right--;
					}
					if (left < right) swap(arr, left, right);
				}
				else if (arr[left] == privot) {
					e = left;
					
					flag = 1;
					left++;
					
				}
				else if (arr[right] == privot) {
					swap(arr, left, right);
					right--;
				}else {
					while (arr[left] <= privot) {
						if (arr[left] < privot) {
							swap(arr, left, e);
							e++;
							left++;
						}else if (arr[left] == privot) {
							left++;
						}
					}
					while(arr[right] > privot) {
						right--;
					}
					swap(arr, right, left);
					
				}
				
				System.out.println(Arrays.toString(arr));
				
			}
			swap(arr, p, e-1);
			map.put(0, e-1);
			map.put(1, right);
			return map;
		}