随机化快速排序（快速排序 随机主元）java代码（递归实现）分治法（分而治之）

固定主元的快速排序：

1.首先选取一个主元（一般取数组的头部或者尾部为主元）；
2.把其他数与主元比较，如果比主元小，放主元左边，如果比主元大，放主元右边；（这个时候主元左边的数都只是比主元小，左边的数还没有从小到大排好，右边也是）。
3.对主元左边数组段重复1，2步骤；对右边也重复1，2步骤。

ps：上述步骤2的具体实现说明（主元以每次选取数组尾端元素为例）：
1.创建两个指针i，j；i初始值为数组头部元素下标减一，j为数组头部元素下标（i左边存放比主要小的元素，i到j存放比主元大的元素，等到j走到尾端要交换主元素时，i+1元素与主元交换即可）
2.j进行移动并与主元进行判断；如果j所对应元素小于主元，j++，i不操作；如果大于，i++，i和j所指元素进行交换，j++.

固定主元的弊端：

如果需要排序的序列为234561 ，那么会使得算法的时间复杂度为：O(n²).
为了避免这种情况，选择随机的主元是一个很好的方式。

随机主元的快速排序（随机化快速排序）：

也就是用系统生成随机数的方法去选择数组下标作为主元，选择后便与数组最后一个元素进行交换，之后的步骤就与固定主元的快速排序相同。
随机主元的快速排序它的时间复杂度的数学期望为：O(nlogn)。
步骤如下：
1.首先选取一个随机主元，与数组尾端元素进行交换.
2.把其他数与主元比较，如果比主元小，放主元左边，如果比主元大，放主元右边；（这个时候主元左边的数都只是比主元小，左边的数还没有从小到大排好）。
3.对主元左边数组段重复1，2步骤；对右边也重复1，2步骤。

ps:上述步骤2的具体实现参考固定主元的快速排序中的ps.

举例：
比如给定数组为945721683，下面我们对其进行分析：
开始——>（比主元大的用蓝色表示，比主元小的用橙色表示，i指向数组首端的前一个，j指向数组首端，即i=left-1，j=left）.
刚开始i指向空，j指向9.
1.随机选择主元，假设选择主元为6；
2.主元6与末尾8交换，变为：945721386
3.主元6与j所指9比较，比6小，j++，j指向4，数组变为：945721386
4.主元6与j所指4比较，比4大，i++，i此时指向9，i与j交换，j++，变为：495721386
5.主元6与j所指5比较，比5大，i++，i此时指向9，i与j交换，j++，变为：459721386
6.主元6与j所指7比较，比7小，j++，变为：457921386
7…省略2138的比较与上述类似，变为：452139786
8.j指向了数组最后一个，即主元，则i+1与主元交换，即9与主元6交换
9.然后递归调用本函数，左边参数的left = left，right = i；右边参数的left = i+2，right= right；递归出口条件为left>=right.

java代码实现随机化快速排序：

public void toQuickSort(int []arr,int left,int right) {
	if(left>=right) 
		return;
	int principalElement = left+(int)(Math.random()*(right-left+1));  //选取随机主元
	//把随机主元放到数组尾部
	int temp = arr[principalElement];
	arr[principalElement] = arr[right];
	arr[right] = temp;
	//数组中元素与主元比较
	int i = left-1;
	for(int j = left;j<=right;j++) {
		if(arr[j]<arr[right]) {
			i++;
			int temp1 = arr[i];
			arr[i] = arr[j];
			arr[j] = temp1;
		}
	}
	//最后把主元放到适当位置
	int temp2 = arr[right];
	arr[right] = arr[i+1];
	arr[i+1] = temp2;
	
	toQuickSort(arr,left,i);
	toQuickSort(arr,i+2,right);
}

函数调用，运行结果：

本文地址：https://blog.csdn.net/MrYushiwen/article/details/107258290