几种排序算法的JavaScript实现
本文由 小茗同学 发表于 2018-06-13 浏览(137)
最后修改 2018-06-27 标签:javascript sort

概述

常见排序算法:

傻瓜排序

这个傻瓜排序是我自己给起的名字,就是按照人的常规思维进行排序,不考虑任何时间复杂度和空间复杂度。话说如果给你一个数组让你手工排序,你的思路会是什么样的呢?我想你肯定是这样的:

整体用肉眼扫描一遍,找到最小的,插入结果里面,然后再扫描剩下的数字,找到最小的,再次插入结果里面,直至原始数组变空,是的,没错,这里说的傻瓜排序就是这个思路。

/**
 * 傻瓜排序
 */
function foolSort(arr) {
	var result = [];
	while(arr.length) {
		var min = arr[0], minIdx = 0; // 先假设第一个数是最小的
		// 遍历找到最小的数字
		for(var i = 1; i< arr.length; i++) {
			if(arr[i] < min) {
				min = arr[i];
				minIdx = idx;
			}
		}
		result.push(min); // 将当前最小数放入结果数组中
		arr.splice(idx, 1); // 从原始数组删除这个数
	}
	return result;
}

冒泡排序

这是最笨也是最容易想到的排序方法:

/**
 * 冒泡排序
 * @param arr 要排序的数组
 */
function bubbleSort(arr) {
	for(let i=0, len=arr.length; i<len-1; i++) {
		for(let j=0; j<len-1-i; j++) {
			if(arr[j] > arr[j+1]) {
				arr[j] = [arr[j+1], arr[j+1] = arr[j]][0];
			}
		}
	}
	return arr;
}

很多时候面试经常需要当面写排序,是个人憋一会儿都能写出来,但是如果能从头到尾一气呵成写完那定是最好的,如何记忆呢?这样记忆,n个数,需要n-1次循环,每次循环从0到n-1-i处为止,最大或最小的数永远在最后面。

快速排序

快速排序使用了一种叫分而治之的思想,它在冒泡排序基础上实现的递归分治法。优点就是快,大多数情况下表现较好,但缺点是不稳定,最坏运行情况是O(n²)

标准版实现(只是说是标准的快速排序,并不是说代码是标准版,代码没有标准):

function quickSort(arr, left, right) {
	left = left === undefined ? 0 : left;
	right = right === undefined ? arr.length : right;
	if (left < right - 1) {
		var splitIndex = split(arr, left, right);
		quickSort(arr, left, splitIndex);
		quickSort(arr, splitIndex+1, right);
	}
	function split(arr, left, right) {
		var i = left, j = right, c = left;
		while(true) {
			while(arr[++i] < arr[c]) {if(i >= right -1) break;}
			while(arr[--j] > arr[c]) {if(j <= left) break;}
			if(i>=j) break;
			swap(arr, i, j);
		}
		swap(arr, c, j);
		return j;
	}
	function swap(arr, a, b) {var temp = arr[a]; arr[a] = arr[b]; arr[b] = temp;}
	return arr;
}
console.log(quickSort([1,5,3,4,8,0,9,4,2,12,6,8,3,2,6,7,8,9,4,32,7,9]));

分割原理

首先,设定一个参考数,我们这里用第一个参数做参考数,然后用两个变量 i 和 j 从数组两边开始向中间扫描,i 向右走,j 往左走:

i往右走,直到遇见比中轴元素大的(或等于)元素停止移动,j 向左走,直到遇到比中轴元素小的(或等于)的元素停止移动:

此时,如果 i < j 则交换 i、j 所指向的元素:

然后继续向右向左走,直到 i >= j 整个扫描停止:

此时 i 对应元素的左边(不包含arr[i])必定小于或等于5,j 对应元素的右边(不包含arr[j])必定大于或等于5

至此,分隔完成。

本段主要参考这里(图片也是来自这里):https://www.itcodemonkey.com/article/3287.html

阮一峰版

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 = [], 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));
};

从代码长度以及理解难易程度上阮一峰版是最佳的,因为即便是从未了解过快速排序的人基本上一看就能懂,但是有2个大问题:

  • 每次都创建新数组,无形中大大增加了空间复杂度;
  • 使用splice不合理。

本文有待完善