javascript常用算法-快速排序（宝，我输液了，输的想你的夜）

这是我参与更文挑战的第16天，活动详情查看： 更文挑战

javascript常用算法-快速排序

• 快排像二分法一样都基于“分治”的算法思想，通过对数据进行分类处理，不断降低数量级，实现O(logN)（对数级别，比O(n)这种线性复杂度更低的一种，快排核心是二分法的O(logN)，实际复杂度为O(N*logN) ）的复杂度。

• 快速排序大概的流程是：

  1、随机选择数组中的一个数A，以这个数为基准；

  2、其他数字跟这个数进行比较，比这个数小的放在其左边，大的放在其右边；

  3、经过一次循环之后，A左边为小于A的，右边为大于A的；

  4、这时候将左边和右边的数再递归上面的过程。

实现的几种方法

方案一：

思路：

1、通过下标取中间数为基数；

2、从起点往后寻找比基数大的，记录为下标 i；再从终点往前寻找比基数小的，记录为下标 j，当 i <= j时，原地交换数值；

3、重复步骤2，直到遍历所有元素，并记录遍历的最后一个下标 i，以此下标为分界线，分为左右两边，分别重复步骤1~3实现递归排序；

// 
    var devide_Xin = function (array, start, end) {
        if(start >= end) return array;
        var baseIndex = Math.floor((start + end) / 2), // 基数索引
             i = start,
             j = end;

        while (i <= j) {
            while (array[i] < array[baseIndex]) {
                i++;
            }
            while (array[j] > array[baseIndex])  {
                j--;
            }

            if(i <= j) {
                var temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
        }
        return i;
    }

    var quickSort_Xin = function (array, start, end) {
        if(array.length < 1) {
            return array;
        }
        var index = devide_Xin(array, start, end);
        if(start < index -1) {
            quickSort_Xin(array, start, index - 1);
        }
        if(end > index) {
            quickSort_Xin(array, index, end);
        }

        return array;
    }
复制代码

总结：

1、用下标取基数，只有一个赋值操作，跟快；

2、原地交换，不需要新建多余的数组容器存储被划分的数据，节省存储；

阮一峰老师的快排js实现

思路：

1、选择数组中间数作为基数，并从数组中取出此基数；

2、准备两个数组容器，遍历数组，逐个与基数比对，较小的放左边容器，较大的放右边容器；

3、递归处理两个容器的元素，并将处理后的数据与基数按大小合并成一个数组，返回。

var quickSort = function(arr) {
 
　　if (arr.length <= 1) { return arr; }
 
　　var pivotIndex = Math.floor(arr.length / 2);
 
　　var pivot = arr.splice(pivotIndex, 1)[0];
 
　　var left = [];
 
　　var right = [];
 
　　for (var i = 0; i < arr.length; i++){
 
　　　　if (arr[i] < pivot) {
 
　　　　　　left.push(arr[i]);
 
　　　　} else {
 
　　　　　　right.push(arr[i]);
 
　　　　}
 
　　}
 
　　return quickSort(left).concat([pivot], quickSort(right));
 
};
复制代码

总结：

阮老师的思路非常清晰，选择基数为参照，划分数组，分而治之，对于新手来理解快排的核心思想“参照-划分-递归”，很容易理解 。

既实现了排序，又符合快速排序的思想，为什么还会为人所诟病呢？原来是因为：

1、阮老师取基数用的是splice()函数取，而不是算法中常用的取下标。基数只是一个参照对象，在比对的时候，只要能从数组中取到即可，所以只需要知道它的索引即可，调用函数删除基数只会更耗时；

2、根据基数来划分时，阮老师专门生成两个数组来存储，从而占用了更多的存储空间（增加了空间复杂度）。

严格上讲，阮老师的代码仅仅是用快速排序的思想实现了排序，也算是快速排序，但是还有很多改进之处。

方案三 网上其他的快排js实现

思路：

1、通过下表取排序区间的第0个数为基数

2、排序区间基数以后，从右往左，寻找比基数小的，从左往右，寻找比基数大的，原地交换；

3、重复步骤2直到 i >= j；

4、将基数与下标为 i 的元素原地交换，从而实现划分；

5、递归排序基数左边的数，递归排序基数右边的数，返回数组。

var quickSort_New = function(ary, left, right) {
        if(left >= right) {
            return ary;
        }

        var i = left,
             j = right;
             base = ary[left];

        while (i < j) {
            // 从右边起，寻找比基数小的数
            while (i<j && ary[j] >= base) {
                j--;
            }

            // 从左边起，寻找比基数大的数
            while (i<j && ary[i] <= base) {
                i++
            } 

            if (i<j) {
                var temp = ary[i];
                ary[i] = ary[j];
                ary[j] = temp;
            }
        }

        ary[left] = ary[i];
        ary[i] = base;

        quickSort_New(ary, left, i-1);
        quickSort_New(ary, i+1, right);

        return ary;
    }
复制代码

总结：

除选基数不同以外，其他与实现一类似。

快速排序的实际应用

• 求一个数组里面最小的k个数
• 通过调用快速排序的 partition() 方法，会返回一个整数 j ，要让得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 K 个元素，这种找第 K 个元素的算法称为快速选择算法。这种算法时间复杂度为O(N) + O(1)。使用最小堆求解的话时间复杂度不变。

	//快排的分割算法
	function partition($arr , $start , $end)
	{
		$temp = $arr[$start];
		while($start < $end){
			while($arr[$end] > $temp && $end>$start) $end--;
			$arr[$start] = $arr[$end];
			
			while($arr[$start] < $temp && $end>$start) $start++;
			$arr[$end] = $arr[$start];			
		}
		$arr[$start] = $temp;
		return $start;
	}
	//获取数组$arr前K个最小值
	function getLeastNumbers($arr,$k){
		$start = 0;
		$end = count($arr) - 1 ;
		$index = Partition($arr,$start,$end);
		while($index != $k-1){
			//在index右侧
			if($index < $k-1)
				$start = $index;				
			else//在index左侧
				$end = $index;
			$index = partition($arr,$start,$end);
		}
		//输出最小的k个数
		for($i = 0 ; $i < $k ; $i++)
			echo  $arr[$i] . " ";
 
 
	}
	$arr = array(4,5,1,6,2,7,3,8);
	getLeastNumbers($arr,4);
复制代码

• 求数组中出现次数超过一半的数

  • 容易理解次数超过一半的那个数必然是这个数组的中位数，依次可以使用快排来寻找数组的中位数，时间复杂度为O（n

function moreThanHalfNum(numberAry)
{
  var obj = {};
  var length = numberAry.length;
  numberAry.forEach(function(d) {
    if (obj[d]) {
      obj[d]++;
    } else {
      obj[d] = 1;
    }
  })
  for (var i in obj) {
    if (obj[i] > Math.floor(length / 2)) {
      return i;
    }
  }
  return 0;
}
复制代码