JavaScript 实现 -- 快速排序

快速排序

快速排序算法是在分治算法基础上设计出来的一种排序算法，和其它排序算法相比，快速排序算法具有效率高、耗费资源少、容易实现等优点。

快排原理

选择一个基准数，通过一次排序将待排序数组分割成两个分区；其中分区的所有数据都比另外一分区的所有数据都要小。然后对分区的数据进行递归，重复上述操作以此达到整个数据变成有序序列。

代码实现

	Array.prototype.quickSort = function(){
	    const rec = (arr) => {
	        if(arr.length === 1 || arr.length === 0){ return arr;}
	        const left = [];
	        const right = [];
	        const mid = arr[0];
	        for(let i = 1; i < arr.length; i++){
	            if(arr[i] > mid){
	                right.push(arr[i]);
	            }else{
	                left.push(arr[i]);
	            }
	        }
	        return [...rec(left), mid, ...rec(right)];
	    };
	    const res = rec(this);
	    //将res拷贝到this
	    res.forEach( (n, i) => { this[i] = n; });
	} 
	
	// 测试用例
	const arr = [1,0,9,4,5];
	arr.quickSort();

快排过程

第一次代码执行完，未递归时，left数组为空，递归时直接返回；

right数组长度大于1，进行递归调用；

right数组递归后，left数组长度大于1，进行递归调用；

right数组为空，递归时直接返回；

left数组递归后，left数组为空，递归时直接返回；

right数组长度为1，排序完成；

时间复杂度

快速排序递归的时间复杂度为O(logN)，分区的时间复杂度为O(N)，所以其时间复杂度为O(n*logN);

算法稳定性

快速排序是不稳定的算法；