读【数据结构与算法】之排序算法
本文介绍数据排序的基本算法和高级算法。这些算法都只依赖于数组来存储数据。
基本排序算法
基本排序算法的核心思想是指对一组数据按照一定的顺序重新排列。重新排列时用到的就是嵌套的for循环。其中外循环会遍历数组的每一项，内循环则用于比较元素。
冒泡排序
冒泡排序是最慢的排序算法之一，但也是一种最容易实现的排序算法。
之所以叫冒泡排序， 是因为使用这种算法排序时，数据值会像旗袍一样从数组的一端到另一端。这种算法会循环数组，然后多次循环，比较相邻的数据，当左侧值大于右侧值时将他们进行互换。
具体实现：
/**
* 对数组进行冒泡排序
* @param {Array} ary 目标数组
* @return {Undefined} undefined
*/
function bubbleSort(ary) {
for (var outer = ary.length, inner = 0, tmp; outer >= 2; outer--) {
for (inner = 0; inner <= outer - 1; inner++) {
if (ary[inner] > ary[inner + 1]) {
tmp = ary[inner];
ary[inner] = ary[inner + 1];
ary[inner + 1] = tmp;
}
}
}
}
选择排序
在 (这里)[http://blog.jobbole.com/79288/] 也有详细介绍。
选择排序是从数组的开头开始，将第一个元素和其他元素进行比较，检查完所有元素后，最小元素会被放到第一个位置上，然后算法会从第二个位置继续。
基本思路，假定数组[5, 6, 3]：
- 先选择认为第一个位置minIndex的元素5是最小元素
- 遍历剩余的，然后遇到了6，发现比5大，直接pass，进行下一个判断,遇到了3发现比5要小，那么此时认为最小的元素的位置就是3所在的位置。
- 遍历一圈发现，minIndex的值变成了2，也就是3所在位置
- 然后交换下3和5，此时数组变为了[3, 6, 5]
- 然后再次循环，此时认为第二个位置minIndex = 1的元素6是最小元素
- 同样遍历，发现5比其小，所以minIndex应该是2
- 然后这一轮也完成了，交换，数组变为了[3, 5, 6]
- 到此结束，并不需要对最后一个遍历了，因为他是最后一个元素，之后没有能和他进行比较的元素了
具体实现：
/**
* 对数组进行选择排序
* @param {Array} ary 目标数组
* @return {Undefined} undefined
*/
function selectionSort(ary) {
var outer = 0,
len = ary.length,
tmp, inner, minIndex;
for ( ; outer <= len - 2; outer++) {
minIndex = outer;
for (inner = outer + 1; inner <= len - 1; inner++) {
if (ary[inner] < ary[minIndex]) {
minIndex = inner;
}
}
if (minIndex !== outer) {
tmp = ary[outer];
ary[outer] = ary[minIndex];
ary[minIndex] = tmp;
}
}
}
交换次数比较多的实现：
/**
* 对数组进行选择排序
* @param {Array} ary 目标数组
* @return {Undefined} undefined
*/
function selectionSort2(ary) {
var outer = 0,
len = ary.length,
tmp, inner;
for ( ; outer <= len - 2; outer++) {
for (inner = outer + 1; inner <= len - 1; inner++) {
if (ary[inner] < ary[outer]) {
tmp = ary[inner];
ary[inner] = ary[outer];
ary[outer] = tmp;
}
}
}
}
插入排序
在 (这里)[http://blog.jobbole.com/79288/] 也有详细介绍。
插入排序中外循环将数组挨个移动，内循环对外循环中选中的元素及他后边的那个元素进行比较，如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中元素腾出位置。
基本思路（想想玩牌的时候），假定数组[5, 6, 3]，命中注定你拿到的牌顺序是这样的：
- 首先假定第一个元素是已经排过序的（你拿到的第一张牌）
- 然后从第二个元素6开始（再拿一张牌），和之前已经排序过的倒序比较（因为之前的已经排好了，肯定是后边的比较大），如果比排好序的5要大，直接pass，不动即可
- 然后第三个元素（你拿起的第三张牌）3，和之前的[5,6]倒着比较，发现比6小，那么交换他们，此时数组[5,3,6]，继续往前，发现比5小，再次交换，这样数组就是[3, 5, 6]了
- 完毕了，只能拿三张牌
基本实现：
/**
* 对数组进行插入排序
* @param {Array} ary 目标数组
* @return {Undefined} undefined
*/
function insertionSort(ary) {
var outer = 1,
len = ary.length,
inner, tmp;
for ( ; outer < len; outer++) {
inner = outer;
while (inner > 0 && ary[inner - 1] > ary[inner]) {
tmp = ary[inner];
ary[inner] = ary[inner - 1];
ary[inner - 1] = tmp;
inner--;
}
}
}
那他的改进版呢，发现每次循环都要交换
基本思路（还是玩牌），假定数组[6, 3, 5]：
- 首先假定第一个元素是已经排过序的（你拿到的第一张牌）
- 然后从第二个元素3开始（再拿一张牌），和之前已经排序过的倒序比较，发现比之前的6要小，所以把6向后移一位（原本位置可以理解为空出来了），数组为[6,6,5]，然后之前排过序的到头了，此时把空出来的位置放置3，此时数组[3,6,5]
- 下次拿到了牌5，此时和之前的倒序比较，发现比6小，依旧把6后移，空出来他的位置，数组为[3,6,6]，继续往前，发现比3大，OK，找到了牌5应该在的位置了，把牌放在哪个空出来的位置即可。此时数组[3,5,6]
- 结束，只能拿三张牌
/**
* 对数组进行插入排序
* @param {Array} ary 目标数组
* @return {Undefined} undefined
*/
function insertionSort2(ary) {
var outer = 1,
len = ary.length,
inner, tmp;
for ( ; outer < len; outer++) {
tmp = ary[outer];
inner = outer;
while (inner > 0 && ary[inner - 1] >= tmp) {
ary[inner] = ary[inner - 1];
inner--;
}
ary[inner] = tmp;
}
}
高级排序算法
高级排序算法通常认为是处理大型数据集的最高效排序算法。
希尔排序
在 (这里)[http://blog.jobbole.com/79288/] 也有详细介绍。
希尔排序（也称为递减增量排序）的思想就是使得数组中的任意间隔的h的元素都是有序的，当间隔为1的时候就是一个排好序的了；其工作原理是，通过定义一个间隔序列来表示排序过程中进行比较元素之间有多远的间隔。我们可以动态定义间隔序列，不过一般都是事先定义好的。
实现希尔排序的一种方法是对于每个h，用插入排序将h个子数组独立的排序。但是因为子数组是相互独立的，一个更简单的办法就是将h子数组中的每个元素都交换到比他大的元素前面去（也就是将比他大的元素向右移动一个位置）。其实也就是只需要将插入排序中的移动元素的距离由1变为h即可了。结果就是希尔排序实现转换为了一个类似于插入排序但却是使用不同增量的过程了。
那他为什么会比较高效呢？排序之初，各个子数组都比较短，排序之后呢子数组都是部分有序的，这两种情况很适合插入排序。
基本实现：
/**
* 对数组进行希尔排序（动态计算gap间隔）
* @param {Array} ary 目标数组
* @return {Undefined} undefined
*/
function shellSort(ary) {
var h = 1,
len = ary.length,
i, j, tmp;
// 《算法》中的计算间隔的公式
// 定义最大步长
while (h < len / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (i = h; i < len; i++) {
for (j = i; j >= h && ary[j] < ary[j - h]; j -= h) {
tmp = ary[j];
ary[j] = ary[j - h];
ary[j - h] = tmp;
}
}
h = (h - 1) / 3;
}
}
归并排序
在 (这里)[http://blog.jobbole.com/79293/] 也有详细介绍。
归并排序实现原理：把一系列排好序的子序列合并成一个大的完整的有序序列。归并排序的优点是保证任意长度为N的数组排序所需要的事件和NlogN成正比；缺点就是需要额外空间且和N成正比。典型的拿空间换时间。
一般情况下，归并排序会使用递归的算法来实现（参见下边的自顶向下的归并排序），然而，在JS中这种方式不太可行，因为这个算法的递归深度对JS而言太深了。所以我们需要使用一种非递归方式实现这个算法，这种策略称为自底向上的归并排序。
自底向上的归并排序
首先需要实现一个将一个数组（每一边左右都是排好序的）归并为一个有序的数组的方法：
/**
* 对数组按照位置合并
* @param {Array} ary 数组
* @param {Number} startLeft 开始左子数组位置
* @param {Number} stopLeft 结束左子数组位置
* @param {Number} startRight 开始右子数组位置
* @param {Number} stopRight 结束右子数组位置
* @return {Undefined} undefined
*/
function mergeArrays(ary, startLeft, stopLeft, startRight, stopRight) {
// 创建的左右子数组 用来复制在ary中元素
// 注意啊 这里长度是 +1 的
// 就是要把数组中最后位置的元素设置为无穷大
// 而对于每个数组 要排的只是从startLeft的位置开始的
// 但是不包含stopRight的位置的
// 从最下边循环中也能看出 是用的 小于 stopRight
var rightArr = new Array(stopRight - startRight + 1),
leftArr = new Array(stopLeft - startLeft + 1),
ral = rightArr.length - 1,
lal = leftArr.length - 1,
i = 0, m = 0, n = 0,
k = startRight;
// 对右子数组进行赋值
for ( ; i < ral; i++) {
rightArr[i] = ary[k];
k++;
}
// 对左子数组进行赋值
k = startLeft;
for (i = 0 ; i < lal; i++) {
leftArr[i] = ary[k];
k++;
}
// 标记结尾 也叫 哨兵值
// 这里为了方便直接设置最后一个元素为无穷大
rightArr[ral] = Infinity;
leftArr[lal] = Infinity;
// 截止到现在ary数组中的值以及分别在左右子数组中了
// 下边就简单了 循环下 谁比较小就把值赋给谁
// 对ary从指定开始到结束位置排序
// 可以使得当前这段范围内的ary是排好序的
for (k = startLeft; k < stopRight; k++) {
if (leftArr[m] <= rightArr[n]) {
ary[k] = leftArr[m];
m++;
} else {
ary[k] = rightArr[n];
n++;
}
}
}
采用非递归或者迭代版本的归并排序是一个自底向上的过程。这个算法首先将数据集分解为一组只有一个元素的数组，然后通过创建一组左右子数组将他们慢慢合并起来，每次合并都保存一部分排好序的数据，知道最后剩下的这个数组所有数据都已排好序。
基本实现：
var mergeSort = (function() {
/**
* 对数组进行归并排序
* @param {Array} ary 目标数组
* @return {Undefined} undefined
*/
function mergeSort(ary) {
var len = ary.length;
if (len < 2) return;
// 初始step是1 下次是2 再下次是4
var step = 1, left, right;
while (step < len) {
left = 0;
right = step;
while (right + step <= len) {
mergeArrays(ary, left, left + step, right, right + step);
// 下次就是把left位置移至right加上step的位置
left = right + step;
// 同理 右边
right = left + step;
}
if (right < len) {
mergeArrays(ary, left, left + step, right, len);
}
step *= 2;
}
}
/**
* 对数组按照位置合并
* @param {Array} ary 数组
* @param {Number} startLeft 开始左子数组位置
* @param {Number} stopLeft 结束左子数组位置
* @param {Number} startRight 开始右子数组位置
* @param {Number} stopRight 结束右子数组位置
* @return {Undefined} undefined
*/
function mergeArrays(ary, startLeft, stopLeft, startRight, stopRight) {
// 创建的左右子数组
var rightArr = new Array(stopRight - startRight + 1),
leftArr = new Array(stopLeft - startLeft + 1),
ral = rightArr.length - 1,
lal = leftArr.length - 1,
i = 0, m = 0, n = 0,
k = startRight;
// 对右子数组进行赋值
for ( ; i < ral; i++) {
rightArr[i] = ary[k];
k++;
}
// 对左子数组进行赋值
k = startLeft;
for (i = 0 ; i < lal; i++) {
leftArr[i] = ary[k];
k++;
}
// 标记结尾 也叫 哨兵值
rightArr[ral] = Infinity;
leftArr[lal] = Infinity;
// 对ary从指定开始到结束位置排序
// 可以使得当前这段范围内的ary是排好序的
for (k = startLeft; k < stopRight; k++) {
if (leftArr[m] <= rightArr[n]) {
ary[k] = leftArr[m];
m++;
} else {
ary[k] = rightArr[n];
n++;
}
}
}
return mergeSort;
}());
自顶向下的归并排序
虽然不推荐，但是还是简单实现下。参照《算法》。
这里先加上所需的merge方法：
/**
* 归并
* @param {Array} ary 已经按照了lo到mid排好序 mid到hi排好序的数组
* @param {Number} lo 起始位置
* @param {Number} mid 中间位置
* @param {Number} hi 结束位置
* @return {Undefined} undefined
*/
function merge(ary, lo, mid, hi) {
var i = lo, j = mid + 1, aux = [];
for (var k = lo; k <= hi; k++) {
aux[k] = ary[k];//复制一份先
}
for (k = lo; k <= hi; k++) {
if (i > mid) {// 左半边已经用尽了
ary[k] = aux[j++];
} else if (j > hi) { // 右半边已经用尽了
ary[k] = aux[i++];
} else if (aux[j] < aux[i]) { // 如果右半边的数比左半边的小 取右半边元素
ary[k] = aux[j++];
} else { // 最后 反之 取得左边元素
ary[k] = aux[i++];
}
}
}
注意和上边mergeArrays方法的区别，多了两个判断，就是左右变用尽的判断，而在上边的mergeArrays方法中没有判断，那是因为直接给左右两个数组中加入了无穷大数，当一边达到结束时，就意味着他的最后一项事无穷大，永远都会进行另一边的赋值。
所以自顶向下的归并排序：
var mergeSort2 = (function() {
var aux;
/**
* 对数组进行归并排序
* @param {Array} ary 目标数组
* @return {Undefined} undefined
*/
function mergeSort(ary) {
aux = new Array(ary.length);
sort(ary, 0, ary.length - 1);
}
// 进行 自顶向下的 递归拆分 然后merge
function sort(ary, lo, hi) {
if (hi <= lo) return;
var mid = parseInt(lo + (hi - lo) / 2);
sort(ary, lo, mid);// 对左半边排序 其实就是先拆分拆分 然后到最后的merge（从一个到多个）去排
sort(ary, mid + 1, hi); // 对对右半边
merge(ary, lo, mid, hi);// 此时归并 出结果
}
/**
* 归并
* @param {Array} ary 已经按照了lo到mid排好序 mid到hi排好序的数组
* @param {Number} lo 起始位置
* @param {Number} mid 中间位置
* @param {Number} hi 结束位置
* @return {Undefined} undefined
*/
function merge(ary, lo, mid, hi) {
var i = lo, j = mid + 1, aux = [];
for (var k = lo; k <= hi; k++) {
aux[k] = ary[k];//复制一份先
}
for (k = lo; k <= hi; k++) {
if (i > mid) {// 左半边已经用尽了
ary[k] = aux[j++];
} else if (j > hi) { // 右半边已经用尽了
ary[k] = aux[i++];
} else if (aux[j] < aux[i]) { // 如果右半边的数比左半边的小 取右半边元素
ary[k] = aux[j++];
} else { // 最后 反之 取得左边元素
ary[k] = aux[i++];
}
}
}
return mergeSort;
}());
两种算法呢，当数组长度为2的幂时，他们对数组访问次数是一样的，只是顺序不同。而其他时候呢，对于自底向上的排序mergeSort比较适合用链表组织的数据。
快速排序
在 (这里)[http://blog.jobbole.com/79298/] 也有详细介绍。
快速排序时处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。
这个算法首先要在列表中选择一个元素作为基准值，数据排序围绕基准值进行，将列表中小于基准值的元素移到数组底部，将大于基准值的元素移到数组顶部。
快速排序和归并排序时互补的：归并排序时将数组拆分成两个子数组再分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序方式则是当两个子数组都是有序的时候我们就认为整个数组就是有序的。
基本实现：
/**
* 对数组进行快速排序
* @param {Array} ary 目标数组
* @return {Array} 排序后的数组
*/
function quickSort(ary) {
var left = [],
right = [],
base = ary[0],
i = 1,
len = ary.length;
if (len < 2) return ary;
for ( ; i < len; i++) {
if (ary[i] < base) {
left.push(ary[i]);
} else {
right.push(ary[i]);
}
}
return quickSort(left).concat(base, quickSort(right));
}
/**
* 对数组进行快速排序（更快）
* @param {Array} ary 目标数组
* @param {Number} start 开始位置
* @param {Number} end 结束位置
* @return {Undefined} undefined
*/
function quickSort2(arr, start, end) {
var base = arr[start];
var i = start;
var j = end;
// 这样一轮循环过后也就是一次划分
// 按照 base 的值去划分
while (i < j) {
// 从右边开始找，如果大于base的话，就让j减一
// 直到遇到一个比base小的停止
while (j > start && arr[j] >= base) {
j--;
}
// 然后从左侧往右找，如果小于base的值，就让i加一
// 直到遇到一个比base大的停止
while (i < j && arr[i] <= base) {
i++;
}
// 交换 i j位置上的数
if (i < j) {
arr[i] = [arr[j], arr[j] = arr[i]][0];
}
}
// 指针相遇
// 此时还需要交换下 start和i的值
// 这一轮的最后的一次交换
arr[start] = [arr[i], arr[i] = arr[start]][0];
// 左半部分
if (i - 1 > start) {
quickSort2(arr, start, i - 1);
}
// 右半部分
if (i + 1 < end) {
quickSort2(arr, i + 1, end);
}
}
具体运行例子请看demo排序算法