乐趣区

发现算法之美排序

  • 什么是排序?

    • 初识
    • 算法图
  • JavaScript 中的排序

    • 普通排序
    • 复杂排序
    • 复杂排序函数封装
    • lodash(v4.17.15)排序函数
    • 从 V8 源码看 sort()
  • 必会经典排序算法

    • 冒泡排序(最大值置尾排序)
    • 选择排序(最小值置头排序)
    • 插入排序(寻找位置排序)
    • 归并排序(二分递归排序)
    • 快速排序(基分递归排序)
  • leetcode 排序 解法题目

    • 35. 搜索插入位置(easy)
    • 88. 合并两个有序数组(easy)
    • 191. 位 1 的个数(easy)
    • 581. 最短无序连续子数组(easy)
    • 1331. 数组序号转换(easy)
    • 56. 合并区间(medium)
    • 215. 数组中的第 K 个最大元素(medium)
  • 参考资料

什么是排序?

初识

生活中也有很多排序,比如考试以后按总分进行降序排列:
第一名 700 分、第二名 699 分、第三名 698 分等等等等
值得注意的是,虽然分数是倒序,但是名次却是正序 1,2,3···

排序在生活中的例子实在太多了,就不一一赘述了。

  • 排序的英文名为 sort
  • 排序是一个将无序 (乱) 的一组数据变为有序的过程
  • 有序通常分为两种:升序(asc)和降序(desc)
  • 排序在软件开发中非常常见:前端数据排序、后端数据库查表升序(asc)、降序(desc)
  • 很多算法依赖于排序算法:栈式算法、二分查找法等等

算法图

无序

降序

升序

JavaScript 中的排序

在 js 中,Array.prototype 上的 sort()函数可以很方便的达到我们对升序和降序的要求。

  • sort()可以升序也可以降序
  • sort()排序后,数组本身发生变化,不产生新数组

普通排序

假设要给 [2,4,3,1,5] 进行排序:

const arr = [2,4,3,1,5]
// 升序
arr.sort((a,b)=>a-b)
// 降序
arr.sort((a,b)=>b-a)

复杂排序

对于复杂情况的话,例如需要对对象数组根据对象中的某个 key 排序。

// items 按照 value 排序
const items = [{ name: 'Edward', value: 21},
  {name: 'Sharpe', value: 37},
  {name: 'And', value: 45},
  {name: 'The', value: -12},
  {name: 'Magnetic', value: 13},
  {name: 'Zeros', value: 37}
];
items.sort((a, b) => a.value - b.value);

复杂排序函数封装

// key 需要排序的 key
// 升序还是降序
function sortBy(arr, key, type = 'asc'){if(!arr || !key) return;
   let callback = (a, b) => a[key]- b[key] : 
   if(type === 'desc'){callback = (a, b) => b[key]- a[key] ;
   }
   arr.sort(callback);
}

lodash(v4.17.15)排序函数

  • _.sortedIndex(array, value)
  • _.sortedIndexBy(array, value, [iteratee=_.identity])
  • _.sortedIndexOf(array, value)
  • _.sortedUniq(array)
  • _.sortedUniqBy(array, [iteratee])

_.sortBy(collection, [iteratees=[_.identity]])

插入位置
_.sortedIndex([30, 50], 40); // => 1
复杂插入位置
var objects = [{'x': 4}, {'x': 5}];
 
_.sortedIndexBy(objects, { 'x': 4}, function(o) {return o.x;});
// => 0
 
// The `_.property` iteratee shorthand.
_.sortedIndexBy(objects, { 'x': 4}, 'x');
// => 0
查询第一个索引
_.sortedIndexOf([4, 5, 5, 5, 6], 5); // => 1
去重并排序
_.sortedUniq([1, 1, 2]); // => [1, 2]
复杂去重并排序
_.sortedUniqBy([1.1, 1.2, 2.3, 2.4], Math.floor);// => [1.1, 2.3]
根据某个 key 排序
var users = [{ 'user': 'fred',   'age': 48},
  {'user': 'barney', 'age': 36},
  {'user': 'fred',   'age': 40},
  {'user': 'barney', 'age': 34}
];
 
_.sortBy(users, [function(o) {return o.user;}]);
// => objects for [['barney', 36], ['barney', 34], ['fred', 48], ['fred', 40]]
 
_.sortBy(users, ['user', 'age']);
// => objects for [['barney', 34], ['barney', 36], ['fred', 40], ['fred', 48]]

从 V8 源码看 sort()

  • V8 源码内部的排序函数叫做 InnerArraySort
  • InnerArraySort 排序算法不仅仅是一种经过多种优化的排序算法
  • InnerArraySort 排序算法综合运用到了快速排序和插入排序

    • 对于数组长度小于 22 的数组,运用插入排序
    • 对于数组长度大于等于 22 的数组,运用快速排序
function InnerArraySort(array, length, comparefn) {
  // In-place QuickSort algorithm.
  // For short (length <= 22) arrays, insertion sort is used for efficiency.
  var InsertionSort = function InsertionSort(a, from, to) {for (var i = from + 1; i < to; i++) {var element = a[i];
      for (var j = i - 1; j >= from; j--) {var tmp = a[j];
        var order = comparefn(tmp, element);
        if (order > 0) {a[j + 1] = tmp;
        } else {break;}
      }
      a[j + 1] = element;
    }
  };

  var QuickSort = function QuickSort(a, from, to) {
    var third_index = 0;
    while (true) {
      // Insertion sort is faster for short arrays.
      if (to - from <= 10) {InsertionSort(a, from, to);
        return;
      }
      if (to - from > 1000) {third_index = GetThirdIndex(a, from, to);
      } else {third_index = from + ((to - from) >> 1);
      }
      // Find a pivot as the median of first, last and middle element.
      var v0 = a[from];
      var v1 = a[to - 1];
      var v2 = a[third_index];
      var c01 = comparefn(v0, v1);
      if (c01 > 0) {
        // v1 < v0, so swap them.
        var tmp = v0;
        v0 = v1;
        v1 = tmp;
      } // v0 <= v1.
      var c02 = comparefn(v0, v2);
      if (c02 >= 0) {
        // v2 <= v0 <= v1.
        var tmp = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
      } else {
        // v0 <= v1 && v0 < v2
        var c12 = comparefn(v1, v2);
        if (c12 > 0) {
          // v0 <= v2 < v1
          var tmp = v1;
          v1 = v2;
          v2 = tmp;
        }
      }
      // v0 <= v1 <= v2
      a[from] = v0;
      a[to - 1] = v2;
      var pivot = v1;
      var low_end = from + 1;   // Upper bound of elements lower than pivot.
      var high_start = to - 1;  // Lower bound of elements greater than pivot.
      a[third_index] = a[low_end];
      a[low_end] = pivot;

      // From low_end to i are elements equal to pivot.
      // From i to high_start are elements that haven't been compared yet.
      partition: for (var i = low_end + 1; i < high_start; i++) {var element = a[i];
        var order = comparefn(element, pivot);
        if (order < 0) {a[i] = a[low_end];
          a[low_end] = element;
          low_end++;
        } else if (order > 0) {
          do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
            order = comparefn(top_elem, pivot);
          } while (order > 0);
          a[i] = a[high_start];
          a[high_start] = element;
          if (order < 0) {element = a[i];
            a[i] = a[low_end];
            a[low_end] = element;
            low_end++;
          }
        }
      }
      if (to - high_start < low_end - from) {QuickSort(a, high_start, to);
        to = low_end;
      } else {QuickSort(a, from, low_end);
        from = high_start;
      }
    }
  };

  if (length < 2) return array;
  QuickSort(array, 0, num_non_undefined);
  return array;
}

必会经典排序算法

经典排序算法有十 (几) 种,由于当前的能力有限,我将先介绍 冒泡、选择、插入、归并和快排 这五种排序算法。

看了 sort()函数的 V8 源码以后,是不是一筹莫展觉得“哇 好难”,除了心存敬畏,其实明白算法是会经过不断的优化的,sort()函数处理了根据 JavaScript 语言特性做了很多性能上的优化。
通常来说我们去开心使用这样性能又好使用又便捷的 sort()函数即可,但其实有一些经典的排序算法,还是非常值得去探索一下的。
即使数据结构课上学过,但其实时间一久,砖搬得过多,还是容易忘记的,就算没有忘记,工作几年以后再回过头来看算法,可能会对过去的算法做一个优化。

LeetCode 的 912 题是一个很好的 oj 环境,适合对自己的排序算法做验证,推荐给大家。

题目:https://leetcode-cn.com/probl…
题解:https://github.com/FrankKai/l…

  • 冒泡排序(最大值置尾排序)
  • 选择排序(最小值置头排序)
  • 插入排序(寻找位置排序)
  • 归并排序(二分递归排序)
  • 快速排序(基分递归排序)

冒泡排序(最大值置尾排序)

  /**
   * 解法:冒泡排序
   * 思路:外层每次循环都是不断将最大值置于尾部, 最小值像气泡一样向前冒出
   * 性能:4704ms 39.4MB
   * 时间复杂度:O(n^2)
   */
var sortArray = function (nums) {for (let i = 0; i < nums.length; i++) {for (let j = 0; j < nums.length - 1 - i; j++) {if (nums[j] > nums[j + 1]) {const temp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = temp;
      }
    }
  }
  return nums;
}

选择排序(最小值置头排序)

  /**
   * 解法:选择排序
   * 思路:已排序区间和未排序区间。在未排序区间中找到最小数,与未排序区间的第一项(已排序区间的下一项)交换,将已排序区间从 [] 构造成[...],最终完成排序。若是降序的话,则找最大的数。* 性能:2104ms 41.5MB
   * 时间复杂度:O(n^2)
   */
var sortArray = function (nums) {for (let i = 0; i < nums.length; i++) {let min = nums[i];
    let idx = i;
    for (let j = i + 1; j < nums.length; j++) {if (nums[j] < min) {min = nums[j];
        idx = j;
      }
      if (j === nums.length - 1) {let temp = nums[i];
        nums[i] = nums[idx];
        nums[idx] = temp;
      }
    }
  }
  return nums;
}

插入排序(寻找位置排序)

  /**
   * 解法:插入排序
   * 思路:已排序区间和未排序区间。取出未排序区间的第一项,在已排序区间上找到自己的位置, 一般来说是找 foo<x<bar,将 x 插入 foo 和 bar 之间,或者是 x <bar 插入头部。* 关键点:插入到指定位置后立即停止在已排序数组中查找
   * 性能:2008ms 43.9MB
   * 时间复杂度:O(n^2)
   * */
var sortArray = function (nums) {const sorted = [nums[0]];
  for (let i = 1; i < nums.length; i++) {
    // j = i - 1; 也行
    for (let j = sorted.length - 1; j >= 0; j--) {if (nums[i] < sorted[j]) {if (j === 0) {sorted.splice(j, 0, nums[i]);
        }
      } else if (nums[i] >= sorted[j]) {sorted.splice(j + 1, 0, nums[i]);
        j = -1; // 这里很关键,插入到指定位置后立即停止在已排序数组中查找
      }
    }
  }
  return sorted;
}
  /**
   * 优化版:插入排序(不借助辅助数组)* 思路:插入 splice(j/j+1, 0), 删除 splice(i, 1)[0]
   * 需要注意的是: splice()返回的是一个数组,例如[1]
   * 性能:2372ms 42.5MB
   * 时间复杂度:O(n^2)
   */
var sortArray = function (nums) {for (let i = 1; i < nums.length; i++) {for (let j = i - 1; j >= 0; j--) {if (nums[i] < nums[j]) {if (j === 0) {nums.splice(j, 0, nums.splice(i, 1)[0]);
        }
      } else if (nums[i] >= nums[j]) {nums.splice(j + 1, 0, nums.splice(i, 1)[0]);
        j = -1;
      }
    }
  }
  return nums;
}

归并排序(二分递归排序)

  /**
   * 解法:归并排序
   * 思路:将长度为 n 的数组拆为 n / 2 长度的数组,分别对各自进行排序。再将 n / 2 长度的数组使用归并排序,直到最终的排序的数组长度为 2,最后将最终排序的数组依次向上合并
   * 核心:二分和递归。类似二分排序,自顶向下二分拆解排序,自底向上合并排序结果。* 注意:终止递归的条件为 if (length <= 1) {return nums;}
   * 性能:260ms 47.9MB
   * 时间复杂度: O(nlogn)
   */
var sortArray = function (nums) {const merge = (left, right) => {const result = [];
    while (left.length && right.length) {if (left[0] >= right[0]) {result.push(right.shift());
      } else {result.push(left.shift());
      }
    }
    while (left.length) {result.push(left.shift());
    }
    while (right.length) {result.push(right.shift());
    }
    return result;
  };
  let length = nums.length;
  if (length <= 1) {return nums;}
  let middle = Math.floor(length / 2);
  let left = nums.splice(0, middle);
  let right = nums;
  return merge(sortArray(left), sortArray(right));
}

快速排序(基分递归排序)

  /** 解法:快速排序
   * 思路:* 1. 选中一个分割点 split
   * 2. 定义左右双指针,一次遍历将分割值小的置于左侧,比分割值大的置于右侧
   * 2.1 左右指针不相遇时 swap(left, right)
   * 2.2 左右指针相遇时,swap(start, left)并且返回 left
   * 3. 分治递归式为左右两侧序列 ***
   * 性能:128ms 40.8MB
   * 时间复杂度:O(nlogn)
   */
var sortArray = function (nums) {quickSort(nums, 0, nums.length - 1);
  return nums;
  // 定义一个 *** 函数
  function quickSort(arr, left, right) {if (left < right) {let splitIndex = findSplitIndex(nums, left, right);
      quickSort(nums, left, splitIndex - 1);
      quickSort(nums, splitIndex + 1, right);
    }
  }
  // 查找分割值索引
  function findSplitIndex(arr, left, right) {
    const start = left;
    const splitValue = arr[start];
    while (left !== right) {while (left < right && arr[right] > splitValue) {right--;}
      while (left < right && arr[left] <= splitValue) {left++;}
      if (left < right) {swap(arr, left, right);
      }
    }
    swap(arr, start, left);
    return left;
  }
  // 交换位置:左右交换、分割点与 left 交换
  function swap(arr, i, j) {const temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
  }
};

算法过程图(来自程序员小灰的文章:漫画:什么是快速排序?(完整版))




leetcode 排序 解法题目

  • 35. 搜索插入位置(easy)
  • 88. 合并两个有序数组(easy)
  • 191. 位 1 的个数(easy)
  • 581. 最短无序连续子数组(easy)
  • 1331. 数组序号转换(easy)
  • 56. 合并区间(medium)
  • 215. 数组中的第 K 个最大元素(medium)

35. 搜索插入位置

题目:https://leetcode-cn.com/probl…
题解:https://github.com/FrankKai/l…

var searchInsert = function(nums, target) {
 /**
   * 解法 2:推入数组重排序法 96ms better than 6.35%
   */
  nums.push(target);
  var resortedNums = nums.sort((x,y)=>x-y);
  return resortedNums.indexOf(target);
};

88. 合并两个有序数组(easy)

题目:https://leetcode-cn.com/probl…
题解:https://github.com/FrankKai/l…

var merge = function(nums1, m, nums2, n) {
  /**
   * 特别需要注意的点:这道题会检查 nums1 数组内存空间最后的存储情况
   */
  // splice 截断数组
  nums1.splice(m);
  nums2.splice(n);
  // 未使用 concat 的原因:concat 返回一个新数组,而题目需要直接在 nums1 的空间进行存储
  nums2.forEach(num2 => {nums1.push(num2);
  });
  // sort 排序当前数组
  var ascArr = nums1.sort((a, b) => a - b);
  return ascArr;
};

191. 位 1 的个数(easy)

题目:https://leetcode-cn.com/probl…
题解:https://github.com/FrankKai/l…

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function (n) {
  /** 解法 4:排序优化 count
   * 性能:88ms 35.7MB
   */
  let strArr = n.toString(2).split("");
  strArr.sort((a, b) => parseInt(b) - parseInt(a));
  let count = 0;
  for (let i = 0; i < strArr.length; i++) {if (strArr[i] === "1") count++;
  }
  return count;
};

581. 最短无序连续子数组(easy)

题目:https://leetcode-cn.com/probl…
题解:https://github.com/FrankKai/l…

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function (nums) {
  /**
   * 解法
   * - 克隆数组并排序
   * - 找起始元素的索引值
   *     - startIdx 从头到尾 找到第一个发生变化的元素索引
   *     - endIdx 从尾到头 找到第一个发生变化的元素索引
   */
  // 使用 [...nums] 克隆一个新数组,是因为 sort 改变的是自身,不会返回一个新数组
  var sortedNums = [...nums].sort((a, b) => a - b);
  var startIdx = 0;
  for (var i = 0; i < nums.length; i++) {if (nums[i] !== sortedNums[i]) {
      startIdx = i;
      break;
    }
  }
  var endIdx = 0;

  for (var j = nums.length - 1; j >= 0; j--) {if (nums[j] !== sortedNums[j]) {
      endIdx = j;
      break;
    }
  }
  var length = endIdx - startIdx > 0 ? endIdx - startIdx + 1 : 0;
  return length;
};

1331. 数组序号转换(easy)

题目:https://leetcode-cn.com/probl…
题解:https://github.com/FrankKai/l…

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var arrayRankTransform = function(arr) {if (arr.length > Math.pow(10, 5)) return;
  /**
   * 生成唯一排序 Map
   */
  var uniqArr = Array.from(new Set(arr));
  var sortArr = uniqArr.sort((a, b) => a - b);
  // 构造出一个二维数组作为 Map 构造器入参
  var twoDimArr = sortArr.map((num, idx) => [num, idx + 1]);
  var idxMap = new Map(twoDimArr);
  /**
   * Map 中查找数字序号
   */
  var serialNums = [];
  for (var i = 0; i < arr.length; i++) {serialNums.push(idxMap.get(arr[i]));
  }
  return serialNums;
};

56. 合并区间(medium)

题目:https://leetcode-cn.com/probl…
题解:https://github.com/FrankKai/l…

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  /**
   * 解法 1:排序 + 栈
   * 性能:88ms 36.3MB
   * 思路:* 推入区间 空栈 或者 arr[0]大于栈最后一个区间闭
   * 覆盖重叠 arr[0]小于栈最后一个区间闭
   *  */
  intervals.sort((a, b) => a[0] - b[0]);
  let stack = [];
  for (let i = 0; i < intervals.length; i++) {let currrentInterval = intervals[i];
    let stackLastItem = stack[stack.length - 1];
    if (stack.length === 0 || currrentInterval[0] > stackLastItem[1]) {stack.push(currrentInterval);
    } else if (currrentInterval[0] <= stackLastItem[1]) {stackLastItem[1] = Math.max(stackLastItem[1], currrentInterval[1]);
    }
  }
  return stack;
};

215. 数组中的第 K 个最大元素(medium)

题目:https://leetcode-cn.com/probl…
题解:https://github.com/FrankKai/l…

var findKthLargest = function (nums, k) {
  /**
   * 解法 1:倒序排序输出
   */
  nums.sort((a, b) => b - a);
  return nums[k - 1];
};

参考资料

  • https://juejin.im/post/57dcd3…
  • https://www.zhihu.com/people/…
  • https://leetcode-cn.com/probl…
  • https://mp.weixin.qq.com/s?__…
  • https://github.com/v8/v8/blob…

期待和大家交流,共同进步,欢迎大家加入我创建的与前端开发密切相关的技术讨论小组:

  • 微信公众号:生活在浏览器里的我们 / excellent_developers
  • Github 博客: 趁你还年轻 233 的个人博客
  • SegmentFault 专栏:趁你还年轻,做个优秀的前端工程师
  • Leetcode 讨论微信群:Z2Fva2FpMjAxMDA4MDE=(加我微信拉你进群)

努力成为优秀前端工程师!

退出移动版