快速排序优化及扫描分区法

发表于 | 分类于 | 阅读次数： | 字数： 2,898 | 阅读时长： 14

快速排序扫描分区法：

通过单向扫描，双向扫描，以及三指针分区分别实现快速排序算法。着重体现分区的思想。

一遍单向扫描法：

思路：

一遍扫描法的思路是，用两个指针将数组划分为三个区间，

扫描指针(scan_pos)左边是确认小于等于主元的，扫描指针到某个指针(next_bigger_pos)中间为未知的，因此我们将第二个指针(next_bigger_pos)成为位未知区间末指针，末指针的右边区间为确认大于主元的元素。

单向扫描

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class QuickSrot {

	public static void main(String[] args) {
        //随机获取15个整数
		int[] arr = util.ArrayUtil.arr(15);
		util.ArrayUtil.printArr(arr);
		quickSort(arr, 0, arr.length-1);
		util.ArrayUtil.printArr(arr);

	}

	public static void quickSort(int[] arr, int p, int r) {
		if(p < r) {
			int q = partition1(arr, p, r);
			quickSort(arr, p, q - 1);
			quickSort(arr, q + 1, r);
		}
	}
	// 单向扫描
	public static int partition1(int[] arr, int p, int r) {
		int pivot = arr[p];
		int sp = p + 1; //扫描指针
		int bigger = r; //右侧指针
		while(sp <= bigger) {
			if(arr[sp] <= pivot) {
				sp++;
			}else {
				util.Swap.swap(arr, sp, bigger);
				bigger--;
			}
		}
		util.Swap.swap(arr, p, bigger);
		return bigger;
	}

程序运行结果：

1
2
97 15 1 32 44 33 27 98 36 30 34 74 83 98 44 
1 15 27 30 32 33 34 36 44 44 74 83 97 98 98

双向扫描分区法：

思路：

双向扫描的思路是，头尾指针往中间扫描，从左找到大于主元的元素，从右找到小于等于主元的元素二者交换，继续扫描，直到左侧无大于元素，右侧无小于主元元素。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class QuickSrot {

	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(15);
		util.ArrayUtil.printArr(arr);
		quickSort(arr, 0, arr.length-1);
		util.ArrayUtil.printArr(arr);

	}

	
	public static void quickSort(int[] arr, int p, int r) {
		if(p < r) {
			int q = partition2(arr, p, r);
			quickSort(arr, p, q - 1);
			quickSort(arr, q + 1, r);
		}
	}
    
	//双向扫描分区法
	public static int partition2(int[] arr, int p, int r) {
		int left = p + 1; //左侧扫描指针
		int right = r; //右侧指针
		int pivot = arr[p];
		while(left <= right) {
			// left不停往右走，直到遇到大于住院的元素
			// 循环退出时，left一定是指向第一个大于主元的位置
			while(left <= right && arr[left] <= pivot) {
				left++;
			}
			// right不停往左走，直到遇到小于住院的元素
			// 循环退出时，right一定是指向从右到左第一个小于于主元的位置
			while(left <= right && arr[right] > pivot) {
				right--;
			}
			if(left < right)
				util.Swap.swap(arr, left, right);
		}
		// 循环退出时，两者交错，且right指向的最后一个小于等于主元的位置，也就是主元应该待得位置
		util.Swap.swap(arr, p, right);
		return right;
	}
}

程序运行结果：

1
2
53 4 87 32 24 99 18 74 91 56 52 24 38 76 30 
4 18 24 24 30 32 38 52 53 56 74 76 87 91 99

三分法：

思路：

当待排序数组中，如果有大量相同的元素，则可用三分区法，每次将与主元相等的元素找到，排行序，并记录这组主主元相等元素序列的开始下标和结束下标。在进行下次递归排序是，排除这部分相同的元素。从而减少递归次数。

三分法

如上图，紫色部分为拍好序的与主元相等的元素，在递归拍其它两边的元素时，可排除这部分元素。具体实现代码如下：

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package chapter3_排序;

public class QuickSort_Three {
	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(15);
		util.ArrayUtil.printArr(arr);
		quickSort(arr, 0, arr.length-1);
		util.ArrayUtil.printArr(arr);
	}

	public static void quickSort(int[] arr, int p, int r) {
		if(p < r) {
			int[] q = partition(arr, p , r);
			quickSort(arr, p, q[0] - 1);
			quickSort(arr, q[1] + 1, r);
		}
	}
	private static int[] partition(int[] arr, int p, int r) {
		int s = p + 1;  //左扫描指针
		int e = s; //记录与主元相等元素序列的开始下标
		int bigger = r; //右侧扫描指针
		int pivot = arr[p]; //主元
		while (s <= bigger) {
			while(s <= bigger && arr[s] <= pivot) {
				//当从一开始没有找到与主语相等的元素，且都小于主元时，指针右移
				if(s <= bigger && s == e && arr[s] < pivot) {
					s++; 
					e++;
				}
				//如过s!=e时，说明已经找到与主元相等的元素，且e记录的为与主元相等元素的开始下标
				//如果下一个元素小于主元，则将小于主元的元素和与主元相等序列的第一个元素交换位置
				if(s <= bigger && s != e && arr[s] < pivot) {
					util.Swap.swap(arr, s, e);
					e++;
					s++;
				}
				//如果遇到等于主元的元素，左扫描指针++， 记录与主元相等序列的开始下标e不变
				if(s <= bigger && arr[s] == pivot) {
					s++;
				}
			}
			//右侧扫描指针
			while(s <= bigger && arr[bigger] > pivot) {
				bigger--;
			}
			//将左侧指针指向大的元素与右侧小于主元的元素交换
			if(s <= bigger && arr[s] > arr[bigger]) {
				util.Swap.swap(arr, s, bigger);
			}
			
		}
		//最后，数组下标为p的开始元素，和与主元相等序列的前一个元素交换，e--
		util.Swap.swap(arr, p, --e);
		//返回与主元相等序列的开始下标和结束下标
		int[] q = {e, bigger};
		return q;
	}
}

程序运行结果：

1
2
5 5 1 8 8 5 6 3 8 2 6 1 6 3 0 
0 1 1 2 3 3 5 5 5 6 6 6 8 8 8

快速排序优化_三点中值法：

思路：

上面三个例子中，每次取得主元都是待排序子序列的开始第一个元素，很大可能不是属于中间的元素，从而容易加大递归的层数。

通过三点中值法，对比待排序序列的开始，中间，最后三个元素的大小，去中间值，更大概率能使主元选择成为中间的元素，从而减少递归层数。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package chapter3_排序;

import javax.rmi.CORBA.Util;

//工程实践中针对快速排序的其他优化
public class QuickSort1 {

	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(15);
		util.ArrayUtil.printArr(arr);
		quickSort(arr, 0, arr.length-1);
		util.ArrayUtil.printArr(arr);
	}

	public static void quickSort(int[] arr, int p, int r) {
		if(p < r) {
			int q = partition(arr, p , r);
			quickSort(arr, p, q - 1);
			quickSort(arr, q + 1, r);
		}
	}

	//三点中值法
	public static int partition(int[] arr, int p, int r) {
		//优化，在p, r, mid之间，选一个中间值作为主元
		int minIndex = p + ((r - p) >> 1);//中间下标
		int minValueIndex = -1;//中值的下标
		if(arr[p] <= arr[minIndex] && arr[p] >= arr[r]) {
			minValueIndex = p;
		}else if(arr[r] <= arr[minIndex] && arr[r] >= arr[p]) {
			minValueIndex = r;
		}else {
			minValueIndex = minIndex;
		}
		util.Swap.swap(arr, p, minValueIndex);
		int pivot = arr[p];
		int left = p + 1; //左侧指针
		int right = r; //右侧指针
		while(left <= right) {
			while(left <= right && arr[left] <= pivot) {
				left++;
			}
			while(left <= right && arr[right] > pivot) {
				right--;
			}
			if(left < right) {
				util.Swap.swap(arr, left, right);
			} 
		}
		util.Swap.swap(arr, p, right);
		return right;
	}
}

程序运行结果：

1
2
20 76 81 19 9 74 48 69 62 98 37 14 96 6 40 
6 9 14 19 20 37 40 48 62 69 74 76 81 96 98

快速排序优化_绝对中值法：

思路：

三点中值法也有很大的随机性，如果想要得到绝对的中值，可以通过绝对中法来获取主元。通过将待排序序以5分为一组，去中间值，取到整个数组的各组中间值，再将这些数组排序，主元取中间值。

一般因为寻找绝对中值，也会花费时间。所以使用三点中值法居多

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package chapter3_排序;

//工程实践中针对快速排序的其他优化
public class 快速排序_绝对中值法 {

	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(15);
		util.ArrayUtil.printArr(arr);
		quickSort(arr, 0, arr.length-1);
		util.ArrayUtil.printArr(arr);
	}

	public static void quickSort(int[] arr, int p, int r) {
		if(p < r) {
			int q = partition(arr, p , r);
			quickSort(arr, p, q - 1);
			quickSort(arr, q + 1, r);
		}
	}

	//绝对中值法
	public static int partition(int[] arr, int p, int r) {
		int pivot = getMedian(arr, p, r);
		int midValueIndex = search(arr, p, r, pivot);
		util.Swap.swap(arr, p, midValueIndex);
		int left = p + 1; //左侧指针
		int right = r; //右侧指针
		while(left <= right) {
			while(left <= right && arr[left] <= pivot) {
				left++;
			}
			while(left <= right && arr[right] > pivot) {
				right--;
			}
			if(left < right) {
				util.Swap.swap(arr, left, right);
			} 
		}
		util.Swap.swap(arr, p, right);
		return right;
	}

	public static int search(int[] arr, int p, int r, int pivot) {
		for(int i = p; i < r + 1; i++) {
			if(arr[i] == pivot)
				return i;
		}
		return -1;
	}

	public static int getMedian(int[] arr, int p, int r) {
		int size = r - p + 1;//数组长度
		// 每五个元素一组
		int groupSize = (size % 5 == 0) ? (size / 5) : (size / 5 + 1);
		int medians[] = new int[groupSize];
		int indexOfMedians = 0;
		//对每一组进行插入排序
		for(int i = 0; i < groupSize; i++) {
			//单独处理最后一组，因为最后一组可能不满5个元素
			if(i == groupSize - 1) { 
				// 排序最后一组
				InsertionSort.insertSort(arr, p + i*5, r);
				// 最后一组的中间那个
				medians[indexOfMedians++] = arr[(p + i * 5 + r) / 2];
			}else { //排序非最后一组的其他组
				InsertionSort.insertSort(arr, p + i * 5, p + i * 5 + 4);
				// 当前组排序后中间那个元素
				medians[indexOfMedians++] = arr[p + i * 5 + 2];
			}
		}
		// 对medians排序
		InsertionSort.insertSort(arr, 0, medians.length - 1);
		return medians[medians.length/2]; 
		
	}
}

程序运行结果：

1
2
39 27 73 78 80 69 42 99 19 87 74 14 50 15 21 
14 15 19 21 27 39 42 50 69 73 74 78 80 87 99

快速排序优化_待排序列较短时，用插入排序：

思想：

当待拍序列较短时，如果一直用递归，花费的时间远比，用插入排序长。所以当待拍序列小于一定长度时，可使用插入排序，提高速度。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package chapter3_排序;

//工程实践中针对快速排序的其他优化
public class 快速排序_优化 {

	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(25);
		util.ArrayUtil.printArr(arr);
		quickSort(arr, 0, arr.length-1);
		util.ArrayUtil.printArr(arr);
	}

	public static void quickSort(int[] arr, int p, int r) {
		if(p < r) {
			//待排序个数小于8个的时候，用插入排序
			if(r - p + 1 <= 8) {
				InsertionSort.insertSort(arr, p, r);
			}else {
				int q = partition(arr, p , r);
				quickSort(arr, p, q - 1);
				quickSort(arr, q + 1, r);
			}
		}
	}

	//三点中值法
		public static int partition(int[] arr, int p, int r) {
			//优化，在p, r, mid之间，选一个中间值作为主元
			int minIndex = p + ((r - p) >> 1);//中间下标
			int minValueIndex = -1;//中值的下标
			if(arr[p] <= arr[minIndex] && arr[p] >= arr[r]) {
				minValueIndex = p;
			}else if(arr[r] <= arr[minIndex] && arr[r] >= arr[p]) {
				minValueIndex = r;
			}else {
				minValueIndex = minIndex;
			}
			util.Swap.swap(arr, p, minValueIndex);
			int pivot = arr[p];
			int left = p + 1; //左侧指针
			int right = r; //右侧指针
			while(left <= right) {
				while(left <= right && arr[left] <= pivot) {
					left++;
				}
				while(left <= right && arr[right] > pivot) {
					right--;
				}
				if(left < right) {
					util.Swap.swap(arr, left, right);
				} 
			}
			util.Swap.swap(arr, p, right);
			return right;
		}
}

程序运行结果：

1
2
86 2 79 72 34 2 20 50 44 75 97 86 93 64 3 5 67 72 22 56 37 69 55 55 53 
2 2 3 5 20 22 34 37 44 50 53 55 55 56 64 67 69 72 72 75 79 86 86 93 97
坚持原创技术分享，您的支持将鼓励我继续创作！