排序算法

排序算法没有优劣之分，在不同的场景中，不同的排序算法执行效率不同。 原地排序：在排序过程中，不产生额外的数组

image.png

选择排序 Selection Sort

一次选择排序，可以将某个区间的最小值排列到该区域的第一位，具体的方式是：

  1. 找出该区域的最小值
  2. 将该值与该区域第一个值交换
  3. 对下一个区域重复上述过程，直到排序完成

排序和查找 - 图2

冒泡排序 Bubble Sort

一次冒泡排序，可以将某个区域序列的最大值排序到该区域的最后一位，具体的方式是：

  1. 将第1位和第2位比较，如果前者比后者大则交换
  2. 将第2位和第3位比较，如果前者比后者大则交换
  3. 依次类推，直到比较到该区域的最后两位
  4. 重复上述过程，直到序列排序完成

排序和查找 - 图3

插入排序 Insertion Sort

将序列分为两个部分，一部分是有序的，一部分是无序的，现在要做的是，就是不断的从无序的部分取出数据，加入到有序的部分，直到整个排序完成

例如：序列[5, 7, 2, 3, 6]

  1. 分为有序的序列和无序的序列 (5) (7 2 3 6)
  2. 不断的扩充有序序列 (5 7) (2 3 6)
  3. 不断的扩充有序序列 (2 5 7) (3 6)
  4. 不断的扩充有序序列 (2 3 5 7) (6)
  5. 不断的扩充有序序列 (2 3 5 6 7)
  6. 排序完成

快速排序 Quick Sort

选择一个数（比如序列的最后一位）作为基准数，将整个序列排序成两部分，一部分比该数小，另一部分比该数大，基准数在中间，然后对剩余的序列做同样的事情，直到排序完成

例如：序列[5, 7, 2, 3, 6, 4]

  1. 选择4作为基准数，排序成为：(3, 2) 4 (7, 6, 5)
  2. 对于3,2， 继续使用该方式排序，得到： (2, 3) 4 (7,6,5)
  3. 对于7,6,5，继续使用该方式排序，得到： (2, 3) 4 (5,6,7)
  4. 排序完成

排序和查找 - 图4

  1. var nums = [3, 8, 7, 9, 6, 5];
  3. // 交换数组两个下标的值，很多排序算法都需要用
  4. function swap(nums, i, j) {
  5.   var temp = nums[i];
  6.   nums[i] = nums[j];
  7.   nums[j] = temp;
  8. }
  10. // 选择排序
  11. function selectionSort(nums) {
  12.   for (var i = 0; i < nums.length - 1; i++) {
  13.     // 在 i ~ nums.length - 1 范围内找到最小值所在的下标
  14.     var min = Infinity;
  15.     var index;
  16.     for (var j = i; j < nums.length; j++) {
  17.       if (nums[j] < min) {
  18.         min = nums[j];
  19.         index = j;
  20.       }
  21.     }
  22.     // 现在，找到了最小值的位置，保存到了变量index中
  23.     // 将index 和 i 交换
  24.     swap(nums, i, index);
  25.   }
  26. }
  28. // 冒泡排序
  29. function bubbleSort(nums) {
  30.   for (var i = 0; i < nums.length - 1; i++) {
  31.     // 依次看 0 ~ nums.length - 2 - i 范围内的数据，只要它比后面的大，就交换
  32.     for (var j = 0; j <= nums.length - 2 - i; j++) {
  33.       if (nums[j] > nums[j + 1]) {
  34.         swap(nums, j, j + 1);
  35.       }
  36.     }
  37.   }
  38. }
  40. // 插入排序
  41. function insertionSort(arr) {
  42.   for (var i = 1; i < arr.length; i++) {
  43.     if (arr[i] < arr[i - 1]) {
  44.       //将第i位的值加入到前面有序队列的正确位置
  45.       var temp = arr[i];
  46.       for (var j = i; j >= 0; j--) {
  47.         if (j > 0 && arr[j - 1] > temp) {
  48.           arr[j] = arr[j - 1];
  49.         }
  50.         else {
  51.           arr[j] = temp;
  52.           break;
  53.         }
  54.       }
  55.     }
  56.   }
  57. }
  59. // 快速排序
  60. function quickSort(nums) {
  61.   // 在指定的下标范围内，做这种骚操作（以一个数为基础，小的靠左，大的靠右）
  62.   function _quickSort(start, end) {
  63.     if (start >= end || start < 0 || end > nums.length - 1) {
  64.       // 范围有问题
  65.       return;
  66.     }
  67.     var low = start, // 低位游标
  68.         high = end, // 高位游标
  69.         key = nums[end]; // 基准值
  70.     while (low < high) {
  71.       //1. 低位向高位移动
  72.       while (low < high && nums[low] <= key) {
  73.         low++;
  74.       }
  75.       nums[high] = nums[low]; //把当前不合理的数字扔到高位去
  76.       //2. 高位向低位移动
  77.       while (low < high && nums[high] >= key) {
  78.         high--;
  79.       }
  80.       nums[low] = nums[high];
  81.     }
  82.     // 高位低位重叠
  83.     nums[low] = key;
  84.     // 对左边的范围重来一次
  85.     _quickSort(start, low - 1);
  86.     // 对右边的范围重来一次
  87.     _quickSort(low + 1, end);
  88.   }
  90.   _quickSort(0, nums.length - 1);
  91. }

查询算法

顺序查找 Inorder Search

即普通的遍历，属于算法的穷举法，没啥好解释的

二分查找 Binary Search

如果一个序列是一个排序好的序列，则使用二分查找可以极大的缩短查找时间

具体的做法是：

查找该序列中间未知的数据

  1. 相等，找到
  2. 要找的数据较大，则对后续部分的数据做同样的步骤
  3. 要找的数据较小，则对前面部分的数据做同样的步骤

插值查找 Interpolation Search

插值查找是对二分查找的进一步改进

如果序列不仅是一个排序好的序列，而且序列的步长大致相同，使用插值查找会更快的找到目标。

插值查找基于如下假设：下标之间的距离比和数据之间的距离比大致相同，即：
排序和查找 - 图5
(目标下标-最小下标) / (最大下标 - 最小下标) ≈ (目标值 - 最小值) / (最大值 - 最小值)

(target - a) / (g - a) ≈ (mid - minIndex) / (maxIndex - minIndex)

因此可以算出大致的下标落点：
目标下标 ≈ (目标值 - 最小值) / (最大值 - 最小值) * (最大下标 - 最小下标) + 最小下标

mid ≈ (target - a) / (g - a) * (maxIndex - minIndex) + minIndex

这样就可以计算出大致的下标落点，后续的比较和二分查找一样。

var nums = [5, 6, 7, 9, 9];

// 顺序查找
function inorderSearch(nums, target) {
  for (var i = 0; i < nums.length; i++) {
    if (nums[i] === target) {
      // 找到了
      return true;
    }
  }
  return false;
}

// 针对排序好的数组，二分查找
function binarySearch(nums, target) {
  var minIndex = 0, // 小的下标
      maxIndex = nums.length - 1; // 大的下标
  while (minIndex <= maxIndex) {
    var mid = Math.floor((minIndex + maxIndex) / 2); // 中间下标

    if (nums[mid] === target) {
      return true; // 找到了
    } else if (nums[mid] > target) {
      maxIndex = mid - 1;
    } else {
      minIndex = mid + 1;
    }
  }
  return false;
}

// 针对排序好的数组，插值查找
function interpolationSearch(nums, target) {
  var minIndex = 0, // 小的下标
      maxIndex = nums.length - 1; // 大的下标
  while (minIndex < maxIndex) {
    var mid = Math.floor(
      ((target - nums[minIndex]) / (nums[maxIndex] - nums[minIndex])) *
      (maxIndex - minIndex) +
      minIndex
    );
    if (mid < minIndex || mid > maxIndex) {
      return false;
    }
    if (nums[mid] === target) {
      return true; // 找到了
    } else if (nums[mid] > target) {
      maxIndex = mid - 1;
    } else {
      minIndex = mid + 1;
    }
  }
  return false;
}