JavaScript 排序

常见排序算法比如:

  • 冒泡排序(属于交换排序)
  • 快速排序(属于交换排序)
  • 直接插入排序(属于插入排序)
  • 希尔排序(属于插入排序)
  • 简单选择排序(属于选择排序)
  • 堆排序(属于选择排序)
  • 归并排序
  • 基数排序

下面通过 JavaScript 实现各个排序算法。

冒泡排序

冒泡排序应该是印象中接触最早的排序算法。冒泡算法核心是顺序比较相邻的两个元素,在升序排列下,如果元素 i 大于 元素 i + 1,则交换两者,第一轮比较到最后一个元素,第二轮比较到倒数第二个元素。直到只剩下第一个元素,比较完毕。

中间有一个优化是,如果某轮比较没有进行交换,则认为数组已经有序,不需要进行下一轮比较。

另一个“改进”版本——双向冒泡,为了减少来回的次数。但实际并没有减少比较次数,反而申请了更多的内存空间。

function sortBubble(array) {
	var i, j = array.length - 1, tmp, no_change;
	while (j > 0) {
		no_change = true;
		for (i = 0; i < j; i++) {
			if (array[i] > array[i + 1]) {
				tmp = array[i];
				array[i] = array[i + 1];
				array[i + 1] = tmp;
				no_change = false;
			}
		}
		if (no_change) {
			break;
		}
	}
}
var ar_score = [10, 9, 8, 7, 6];
sortBubble(ar_score);

快速排序

快速排序通过设置哨兵,把小于和大于哨兵的数组元素分别组织为数组,再通过递归对两个数组进行快速排序,直到每个数组不能分解(只有一个数组元素)。

<script type="text/javascript">
function sortQuick(array) {
	var i = 0, j = array.length - 1, index = 0, guard = array[index];
	var ar_left, ar_right;
	while (j > i) {
		while (j > index) {
			if (array[j] < guard) {
				array[index] = array[j];
				array[j] = guard;
				index = j;
				break;
			}
			j--;
		}
		while (i < index) {
			if (array[i] > guard) {
				array[index] = array[i];
				array[i] = guard;
				index = i;
				break;
			}
			i++;
		}
	}

	if (i > 0) {
		ar_left = array.slice(0, i);
		sortQuick(ar_left);
		array.splice.apply(array, [0, i].concat(ar_left));
	}

	if (j < array.length - 1) {
		j++;
		ar_right = array.slice(j);
		sortQuick(ar_right);
		array.splice.apply(array, [j, array.length - j].concat(ar_right));
	}
}

var ar_score = [10, 9, 8, 7, 6];
sortQuick(ar_score);
</script>

[10, 9, 8, 7, 6] 交换步骤

  • 第一次排序 [6, 9, 8, 7, 10]
  • 分拆为 [6, 9, 8, 7]、[10], 左侧数组在进行快速排序、右侧数组不需要进行排序
  • 第二次排序 [6, 9, 8, 7] 、[10], 分拆为 [6]、[9, 8, 7]、[10]
  • 第三次排序 [6]、[7, 8, 9]、[10]
  • 第四次排序 [6]、[7, 8], [9], [10]
  • 第五次排序 [6]、[7], [8], [9]、[10]
  • 拼装返回的数组列表得到 [6, 7, 8, 9, 10]

直接插入排序

插入排序是在实际生活中使用得比较早的排序,比如试卷评分,把试卷按照分数高低排序。

插入排序通过设置有序数组,从后续元素中依次比较元素与有序数组中元素的顺序,从而插入到指定位置,最终形成有序数组。

  1. 设置 a[0] 是一个有序数组,无序数组从 a[1…length-1]。length 为数组长度,假定 i = 1
  2. 将 a[i] 插入到有序数组 a[0…i-1]
  3. 将 i++,如果 i 小于 length 则重复第二步
  4. 排序结束
<script type="text/javascript">
function sortInsert(array) {
	var i = 1, j, k, length = array.length, tmp;

	if (!(length > 1)) {
		return;
	}

	do {
		for (j = i - 1; j > -1; j--) {
			if (array[j] < array[i]) {
				break;
			}
		}
		if (j != i - 1) {
			tmp = array[i];
			for (k = i - 1; k > j; k--) {
				array[k + 1] = array[k];
			}
			array[k + 1] = tmp;
		}
		i++;
	} while (i < length);
}
var ar_score = [10, 9, 8, 7, 6];
sortInsert(ar_score);
</script>

[10, 9, 8, 7, 6] 插入步骤

  • 第1次排序,设置有序数组 [10],插入数组元素 9,得到 [9, 10]、[8, 7, 6]
  • 第2次排序,有序数组 [9, 10],插入数组元素 8,得到 [8, 9, 10]、[7, 6]
  • 第3次排序,有序数组 [8, 9, 10],插入数组元素 7,得到 [7, 8, 9, 10]、[6]
  • 第4次排序,有序数组 [7, 8, 9, 10],插入数组元素 6,得到 [6, 7, 8, 9, 10]

直接插入排序在第二步插入时,需要用到查询,上述代码的一个改进点是使用二分查找,降低时间复杂度。

希尔排序

希尔排序

简单选择排序

简单选择排序

堆排序

堆排序

归并排序

归并排序

基数排序

基数排序

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注