快速排序 quicksort

快速排序是一种采用分治法的比较排序算法。
一般分为三个步骤完成:
一、分解:将数组 A[p..r] 分解为两个(可能为空)子数组 A[p..q – 1] 和
A[q + 1..r],使得 A[p..q – 1] 中的每个元素都小于等于 A[q],而且,
A[q + 1..r] 中的每个元素都大于等于 A[q]。q 是划分过程中计算出来的,
我们把 A[q] 称作主元。
二、解决:通过递归调用快速排序算法,对子数组 A[p..q – 1] 和
A[q + 1, r] 进行排序。
三、合并:因为采用的是就地排序,无需要合并操作。
那么我们就能得出排序算法如下:

quickSort(A, p, r){
	if(p < r){
		q = partition(A, p, r);
		quickSort(A, p, q - 1);
		quickSort(A, q + 1, r);
	}
}

那么对数组 A 排序是就调用 quickSort(A, 0, A.length – 1);

那么我们如何划分数组呢!
我们一般选取最后一个元素即 A[r] 作为主元,并对数组进行就地重排:
过程是这样的,设置划分的位置 q = 0,从第一个元素开始到第
r – 1 个元素,与主元比较,假如它比主元小就和下标为 q 的元素交换,
同时 q 后移。

partition(A, p, r){
	pivot = A[r];
	i = p;
	j = p;
	for(; j < r; j++){
		while(A[j] <= pivot){
			swap(A[i], A[j]);
			i++;
		}
	}
	swap(A[i], A[r]);
	return i;
}

下面我们以 A = [2, 6, 4, 1, 8, 7, 9, 3, 5] 为例图解一下过程:



最后我们来整理一下完整的代码:

function swap(aArr, i, j){
	var k = aArr[i];
	aArr[i] = aArr[j];
	aArr[j] = k;
}

function quickSort(aArr, iLeft, iRight){
	if(iLeft < iRight){
		var iPartition = partition(aArr, iLeft, iRight);
		quickSort(aArr, iLeft, iPartition - 1);
		quickSort(aArr, iPartition + 1, iRight);
	}
	return aArr;
}

function partition(aArr, iLeft, iRight){
	var iPartition = iLeft,
		j = iLeft,
		iPivot = aArr[iRight];

	for(; j < iRight; j++){
		if(aArr[j] < iPivot){
			if(iPartition !== j){
				swap(aArr, iPartition, j);
			}
			iPartition++;
		}
	}
	swap(aArr, iPartition, iRight);
	return iPartition;
}
var a = [2, 6, 4, 1, 8, 7, 9, 3, 5];
console.log(quickSort(a, 0, a.length - 1));

Post a Comment

Your email is never shared. Required fields are marked *

*
*