标签： 算法

获取两个字符串 a 和 b 的最长公共子串，时间复杂度 O(mn)，空间复杂度 O(n)，其中 a 的字符串长度为 m，b 的字符串长度为 n。

function lcs(a, b) {
    var ai, al = a.length,
        bi, bl = b.length - 1, maxBi,
        max = 0, val,
        row = [],
        ret = [];

    for (ai = 0; ai < al; ai++) {
        for (bi = bl; bi > -1; bi--) {
            val = a[ai] == b[bi] ? 1 : 0;
            if (val) {
                if (row[bi - 1]) {
                    val += row[bi - 1];
                }
                if (val > max) {
                    max = val;
                    maxBi = bi;
                }
            }
            row[bi] = val;
        }
    }

    for (; max > 0; max--, maxBi--) {
        ret.unshift(b[maxBi]);
    }

    return ret.join('');
}

常见排序算法比如：

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

下面通过 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]

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

希尔排序

希尔排序

简单选择排序

简单选择排序

堆排序

堆排序

归并排序

归并排序

基数排序

基数排序