首页 > 前端 > 快速排序之javascript实现

快速排序之javascript实现

算法原理

快速排序是目前各种排序算法中较为高效的一种算法,它的基本思想是分治法

分治法(Divide and Conquer Algorithm):把原问题分为若干个与原问题结构类似的子问题,然后对子问题进行递归求解,最后把这些子问题的解集全部合并起来就是原问题的解。

 

算法具体实现有三个步骤:

1. 从数组中选出一个元素,我们称之为 “基准”(pivot);

2. 先进行一次循环比较,把所有比基准小的数放左边,把所有比基准大的数放右边(相等的值随便哪边放都行),这个操作称为分区 (partition) 操作。当分区完成后,我们就得到了两个子分区,   其中一个分区的所有元素的值都比另外一个分区大。

3. 分别对步骤二分出来的两个子集进行递归排序,直到最后子集只剩一个元素为止。

2016050511445291

图片来自维基百科

 

JavaScript 实现

一开始参照了阮一峰的博客:快速排序(Quicksort)的Javascript实现

再根据分治法的原理,快速排序的JavaScript实现可以这样做:

function quickSort(arr) {
    //如果分区只剩一个元素,结束遍历并返回子集数组
    if (arr.length <= 1) { 
        return arr;
    }
    //基准的位置在哪里无所谓,但是为了便于理解,我们直接选择中间位置的元素作为基准
    var pivotIndex = Math.floor(arr.length / 2); 
    //获取基准的值pivotValue
    var pivotValue = arr.splice(pivotIndex, 1)[0]; 
    //先创建两个数组来存放左右分区 
    var left = []; 
    var right = []; 
    for (var i = 0; i < arr.length; i++) { 
        if (arr[i] < pivotValue) { 
            //元素值小于基准值,放进左分区
            left.push(arr[i]);
        } else { 
            //元素值大于基准值,放进右分区 
            right.push(arr[i]);
        }
    }
    //递归遍历子分区,重复上面步骤,最后将左数组\基准\右数组三个数组连接起来
    return quickSort(left).concat([pivotValue], quickSort(right)); 
}

这样就实现了快速排序算法,但是后来发现这种做法有一个问题,就是需要分配额外的存储空间(left[]和right[]分区占用的空间),每排一次都要新建两个一左一右的数组,所以当要排序的数组非常大时,占用的内存空间就会随着递归的次数迅速增加。

 

改进优化

参照Nicholas C.Zakas的文章 Computer science in JavaScript: Quicksort

核心的要点是使用 原地排序(In-Place) 的方法来进行优化,从而避免不必要的空间开销,实现代码如下:

// 交换
function swap(arr, a, b) {
	var temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

// 分区
function partition(arr, left, right) {

	//初始化基准位置设在中间
	var pivot   = arr[Math.floor((right + left) / 2)];

	//注意while,以及相等的情况(index相等时/indexValue相等时)
	//一定要有'=',等于时会直接进入if代码里++和--进行错开
	while (left <= right) {

    	//从左到右找到不小于基准值的元素为止
    	//注意遇到相等的情况也要停下
    	while (arr[left] < pivot) {
    		left++;
    	}

    	//从右到左找到不大于基准值的元素为止
    	//注意遇到相等的情况也要停下
    	while (arr[right] > pivot) {
    		right--;
    	}

    	if (left <= right) {
    		swap(arr, left, right);
            //交换之后要接着走完while循环
            left++;
            right--;
        }
    }

    //这里返回的是分区位置
    return left;
}
// 快排
function quickSort(arr, left, right) {

	var index;

    //确保原数组长度大于1
    if (arr.length > 1) {

    	//默认值从左到右为整个数组
    	left = typeof left != "number" ? 0 : left;
    	right = typeof right != "number" ? arr.length - 1 : right;

		//获取分区位置
		index = partition(arr, left, right);

        //确保左分区数组长度大于1,进入递归
        if (left < index - 1) {
        	quickSort(arr, left, index - 1);
        }

		//确保右分区数组长度大于1,进入递归
		if (index < right) {
			quickSort(arr, index, right);
		}

	}

	return arr;
}

其中left为低位序号,right为高位序号,可以这样调用:

var result = quickSort(arr, 0, arr.length - 1);
//or
var result = quickSort(arr);

 

以数组[4,9,6,5,7,9]为例,下面这张图片展示了该分区算法(partition)的操作流程:

quick-sort-demo

 

附:ES6实现

/**
* 快速排序
*
* @param {array}  arr   待排序的数组
* @param {number} left  开始排序的位置,默认为0
* @param {number} right 结束排序的位置,默认为数组最后一位
*/
function quickSort(arr, left, right) {

	//交换
	function swap(arr,i,j) {
		[arr[i],arr[j]] = [arr[j],arr[i]];
	}

	//分区
	function partition(arr, left, right) {
		//初始化基准位置设在中间
		let pivot = arr[Math.floor((right + left) / 2)];

		//注意有没有'='的判断的区别:有=是为了继续走,没有=则不走
		while(left <= right) {

			//从左到右找到不小于基准值的元素为止
    		//注意遇到相等的情况也要停下
			while(arr[left] < pivot) {
				left++;
			}

			//从右到左找到不大于基准值的元素为止
    		//注意遇到相等的情况也要停下
			while(arr[right] > pivot) {
				right--;
			}

			//为了接着走下去以获取准确的新分区位置,这里要考虑等于的情况
			if(left <= right) {
				//交换位置
				swap(arr,left,right);

				//交换之后要接着走外层while循环
				left++;
				right--;
			}
		}

		//这里返回的是新的分区位置
		return left;
	}


	function sort(arr, left, right) {
		let len = arr.length,
			partitionIndex = null;

		//确保原数组长度大于1
		if (len > 1) {

			//默认值从左到右整个数组
			left = typeof left != 'number' ? 0 : left;
			right = typeof right != 'number' ? len - 1 : right;

			//获取分区位置
			partitionIndex = partition(arr, left, right);

			//确保左分区数组长度大于1,进入递归
			if(left < partitionIndex - 1) {
				sort(arr, left, partitionIndex - 1);
			}

			//确保右分区数组长度大于1,进入递归
			if(right > partitionIndex) {
				sort(arr, partitionIndex, right);
			}
		}

		return arr;
	}

	return sort(arr, left, right);
}

 

总结:

快速排序在实践中被认为是比较高效率的排序方法,它的特点在于使用了分治法(Divide and Conquer Algorithm)和原地排序(In Place),这两个优点结合起来使得它适用于各种不同的输入数据,并且在一般应用中会比其排序算法快得多。

顺带一提,在V8引擎里调用Array.prototype.sort()时,当数组长度大于10个的情况下,采用的是快速排序,而当长度小于等于10个时则切换为插入排序,以提高运算效率(相关引擎源码见:V8 Array Source Code)。

而对于Mozilla 和 Safari 的JS引擎,采用的则是更为稳定的归并排序。

算法分析

  • 最佳情况:T(n) = O(nlogn)
  • 最差情况:T(n) = O(n2)
  • 平均情况:T(n) = O(nlogn)
  • 稳定性:不稳定

 


本文标题:快速排序之javascript实现
转载请注明出处,欢迎分享