快速排序

快速排序：快排是一种不稳定的算法，其平均时间复杂度为O(nlgn)，最坏为O(n^2)。

设当前待排序的无序区为R[low..high]，那么在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1]和R[pivotpos+1..high]，并使左边子区间所有记录的值小于等于基准值，右边子区间所有记录的值大于等于基准值，这时基准值就会处于正确的位置上。

 

/**
 * 快速排序(不稳定)
 * 
 * @author alchimie
 */
public class QuickSort {
	public void sort(int[] arrs) {
		sort(arrs, 0, arrs.length - 1);
	}

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

	private int partition(int[] arrs, int left, int right) {
		int i, j, c, p;
		p = arrs[left]; // p中存的就是基准数
		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) {
				c = arrs[i];
				arrs[i] = arrs[j];
				arrs[j] = c;
			}
		}
		// 最终将基准数归位
		// System.out.println("===" + "arrs[left]="+ arrs[left] + ", arrs[i]="+
		// arrs[i]+"===");
		arrs[left] = arrs[i];
		arrs[i] = p;
		System.out.println("基准数: " + p + " " + Arrays.toString(arrs));
		return i;
	}

	public static void main(String args[]) {
		QuickSort qs = new QuickSort();
		int arrs[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
		qs.sort(arrs);
		for (int i = 0; i < arrs.length; i++) {
			System.out.println(arrs[i]);
		}
	}
}

 

 

执行结果：

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

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

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

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

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

13

27

38

49

49

65

76

97