学习《JavaScript 数据结构与算法》读书笔记-第10章-排序和搜索算法

学习《JavaScript 数据结构与算法》读书笔记

10 排序和搜索算法

10.1 排序算法

先创建一个数组（列表）来表示待排序和搜索的数据结构

function ArrayList() {
  var array = [];

  this.insert = function(item) {
    array.push(item);
  };

  this.toString = function() {
    return array.join();
  };
}

10.1.1 冒泡算法

冒泡算法在所有排序算法中最简单。然而从运行时间的角度来看，冒泡排序是最差的一个。
冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序，就好像气泡升至表面一样。

this.bubbleSort = function() {
  var length = array.length;
  // 外循环，控制了在数组中经历了多少轮排序
  for (var i = 0; i < length; i++) {
    // 内循环，从第一个迭代至倒数第二位
    for (var j = 0; j < length - 1; j++) {
      // 判断顺序（当前项是否比下一项大）
      if (array[j] > array[j + 1]) {
        // 如果顺序不对，交换
        swap(array, j, j + 1);
      }
    }
  }
}

再声明swap函数（一个私有函数，只能用在ArrayList类的内部代码中）

var swap = function(array, index1, index2) {
  var aux = array[index1];
  array[index1] = array[index2];
  array[index2] = aux;
};

如果使用 ES6（ECMAScript2015） 增强的对象属性，这个函数可以写成下面这样

[array[index1], array[index2]] = [array[index2], array[index1]];

测试

function createNonSortedArray(size) {
  var array = new ArrayList();
  for (var i = size; i > 0; i--) {
    array.insert(i);
  }
  return array;
}

var array = createNonSortedArray(5);
console.log(array.toString());
array.bubbleSort();
console.log(array.toString());

改进后的冒泡排序

this.modifiedBubbleSort = function() {
  var length = array.length;
  for (var i = 0; i < length; i++) {
    for (var j = 0; j < length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        swap(j, j + 1);
      }
    }
  }
};

10.1.2 选择排序

找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

this.selectionSort = function() {
  var length = array.length,
    indexMin;
  /* 迭代数组，并控制迭代轮次 */
  for(var i = 0; i < length - 1; i++) {
    /* 假设本本迭代轮次第一个值为数组最小值 */
    indexMin = i;
    /* 从当前i的值开始至数组结束 */
    for (var j = i; j < length; j++) {
      /* 比较位置j的值和当前最小值 */
      if (array[indexMin] > array[j]) {
        /* 更新最小值 */
        indexMin = j;
      }
    }
    /* 内循环结束，如果该最小值和原最小值不同，则交换 */
    if (i !== indexMin) {
     swap(i, indexMin);
   }
  }
};

测试

array = createNonSortedArray(5);
console.log(array.toString());
array.selectionSort();
console.log(array.toString());

10.1.3插入排序

插入排序每次排一个数组项，以此方式构建最后的排序数组。
排序小型数组时，此算法比选择排序和冒泡排序性能要好。

this.insertionSort = function() {
  var length = array.length;
    j,
    temp;
  /* 迭代数组给第i项找到正确的位置 */
  /* 从第二个位置开始，我们认为第一项已经排序了 */
  for (var i = 1; i < length; i++) {
    j = i;
    temp = array[i];
    /* 只要j比0大，且数组中前面的值比待比较值大 */
    while (j > 0 && array[j - 1] > temp) {
      /* 我们就把这个值移到当前位置上 */
      array[j] = array[j - 1];
      /* 并减小j */
      j--;
    }
    array[j] = temp;
  }
};

10.1.4 归并排序

归并排序是第一个可以被实际使用的排序算法

归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，知道最后只有个一个排序完毕的大数组

this.mergeSort = function() {
  array.mergeSortRec(array);
};

var mergeSortRec = function(array) {
  var length = array.length;
  if (length === 1) {
    return array;
  }
  var mid = Math.floor(length / 2),
    left = array.slice(0, mid),
    right = array.slice(mid,length);

  return merge(mergeSortRec(left), mergeSortRec(right));
};

var merge = function(left, right) {
  var result = [],
    il = 0,
    ir = 0;

  while (il < left.length && ir < right.length) {
    if (left[il] < right[rl]) {
      result.push(left[il++]);
    } else {
      result.push(right[ir++]);
    }
  }

  while (il < left.length) {
    result.push(left[il++]);
  }

  while (ir < right.length) {
    result.push(right[ir++]);
  }

  return result;
};

10.1.5 快速排序

this.quickSort = function() {
  quice(array, 0, array.length - 1);
};

var quick = function(array, left, right) {
  var index;
  if (array.length > 1) {
    index = partition(array, left, right);

    if (left < index - 1) {
      quice(array, left, index - 1);
    }

    if (index < right) {
      quice(array, index, right);
    }
  }
};

var partition = function(array, left, right) {
  var pivot = array[Math.floor((right + left) / 2)],
    i = left,
    j = right;

  while (i <= j) {
    while (array[i] < pivot) {
      i++;
    }
    while (array[j] > pivot) {
      j--;
    }
    if (i <= j) {
      swap(array, i, j);
      i++;
      j--;
    }
  }
  return i;
};

10.1.6 堆排序

堆排序也是一种很高效的算法，因其把数组当做二叉树来排序而得名。这个算法会根据以下信息，把数组当做二叉树来管理

索引0是树的根节点

除根节点外，任意节点N的父节点是 N / 2

节点L的左子节点是 2 * L

节点R的右子节点是 2 * R + 1

堆排序算法实现如下

this.heapSort = function() {
  var heapSize = array.length;
  /* 构造一个满足 array[parent(i)] >= array[i] 的堆结构 */
  buildHeap(array);

  while (heapSize > 1) {
    heapSize--;
    /* 交换堆里第一个元素（数组中较大的值）和最后一个元素的位置 */
    swap(array, 0, heapSize);
    /* 再次将数组转换成堆 */
    heapify(array, heapSize, 0);
  }
};

var buildHeap = function(array) {
  var headSize = array.length;
  for (var i = Math.floor(array.length / 2); i >= 0; i--) {
    heapify(array, headSize, i);
  }
};

var heapify = function(array, heapSize, i) {
  var left = i * 2 + 1,
    right = i * 2 + 2,
    largest = i;

  if (left < headSize && array[left] > array[largest]) {
    largest = left;
  }

  if (right < heapSize && array[right] > array[largest]) {
    largest = right;
  }

  if (largest !== i) {
    swap(array, i, largest);
    heapify(array, heapSize, largest);
  }
};

10.1.7 计数排序、桶排序和基数排序（分布式排序）

还有一类被称为分布式排序的算法，原始数组中的数据会分发到多个中间结构（桶），再合起来放回原始数组。
最著名的分布式算法有计数排序、桶排序和基数排序
例子

10.2 搜索算法

10.2.1 顺序搜索

顺序或线性搜索是最基本的搜索算法。它的机制是，将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法

this.sequentialSearch = function(item) {
  for (var i = 0; i < array.length; i++) {
    if (item === array[i]) {
      return i;
    }
  }
  return -1;
}

10.2.2 二分搜索

这个算法要求被搜索的数据结构已排序。以下是该算法遵循的步骤：

1. 选择数组的中间值
2. 如果选中的值是待搜索值，那么算法执行完毕（值找到了）
3. 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找
4. 如果待搜索值比选中值要大，则返回不走1并在选中值右边的子数组中寻找

this.binarySearch = function(item) {
  this.quickSort();

  var low = 0,
    high = array.length - 1,
    mid,
    element;

  while (low <= high) {
    mid = Math.floor((low + high) / 2);
    element = array(mid);
    if (element < item) {
      low = mid + 1;
    } else if (element > item) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
};