随机快速排序

快速排序的基准数随机选择版本：

package arithmetic.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 
 * @author alchimie
 * 
 * 随机快速排序(不稳定) 
 * 
 */
public class RandomQuickSort {
	Random random = new Random();
	
	public void randomQuickSort(int[] arrs) {
		randomQuickSort(arrs, 0, arrs.length - 1);
	}

	private void randomQuickSort(int[] arrs, int low, int high) {
		int p;
		if (low < high) {
			p = randomPartition(arrs, low, high);
			randomQuickSort(arrs, low, p - 1);
			randomQuickSort(arrs, p + 1, high);
		}
	}

	/*
	 * 划分基准数
	 */
	private int randomPartition(int[] arrs, int left, int right) {
		int i, j, p;
		// 随机选择基准数
		int ranInt = random.nextInt(right-left+1);
		int w = left + ranInt;
		p = arrs[w]; // p中存的就是基准数
		swap(arrs, left, w);
		
		i = left;
		j = right;
		while (i != j) {
			// 顺序很重要，要先从右边开始找，否则i指针有可能停留在比p大的数上，导致归位交换出错
			while (arrs[j] >= p && i < j)
				j--;
			// 再找右边的
			while (arrs[i] <= p && i < j)
				i++;
			// 交换两个数在数组中的位置
			if (i < j) {
				swap(arrs, i, j);
			}
		}
		// 最终将基准数归位
		arrs[left] = arrs[i];
		arrs[i] = p;
		System.out.println("基准数: " + p + " " + Arrays.toString(arrs));
		return i;
	}

	/*
	 * 交换指定数组的left和right索引的值
	 */
	private void swap(int[] arrs, int left, int right){
		int c = arrs[left];
		arrs[left] = arrs[right];
		arrs[right] = c;
	}
	
	public static void main(String args[]) {
		RandomQuickSort rqs = new RandomQuickSort();
		int arrs[] = { 49, 38, 65, 97, 76, 13, 27, 49, 5, 83 };
		rqs.randomQuickSort(arrs);
		for (int i = 0; i < arrs.length; i++) {
			System.out.println(arrs[i]);
		}
	}
}

 

执行结果：

基准数: 76 [49, 38, 65, 5, 49, 13, 27, 76, 97, 83]
基准数: 5 [5, 38, 65, 49, 49, 13, 27, 76, 97, 83]
基准数: 13 [5, 13, 65, 49, 49, 38, 27, 76, 97, 83]
基准数: 49 [5, 13, 38, 27, 49, 49, 65, 76, 97, 83]
基准数: 38 [5, 13, 27, 38, 49, 49, 65, 76, 97, 83]
基准数: 97 [5, 13, 27, 38, 49, 49, 65, 76, 83, 97]
5
13
27
38
49
49
65
76
83
97