search

FrankKai / FrankKai.github.io

FE blog
https://frankkai.github.io/
362 stars 39 forks source link

发现算法之美-排序 #226

Open FrankKai opened 4 years ago

FrankKai commented 4 years ago

image

FrankKai commented 4 years ago

什么是排序？

初识

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

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

算法图

无序

image

降序

image

升序

image

FrankKai commented 4 years ago

JavaScript中的排序

在js中，Array.prototype上的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([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()

FrankKai commented 4 years ago

必会经典排序算法

image

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

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

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

题目：https://leetcode-cn.com/problems/sort-an-array/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/912.Sort_an_Array.js

冒泡排序（最大值置尾排序）

  /**
   * 解法：冒泡排序
   * 思路：外层每次循环都是不断将最大值置于尾部,最小值像气泡一样向前冒出
   * 性能：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;
  }
};

算法过程图（来自程序员小灰的文章：漫画：什么是快速排序？（完整版））

image

image

image image

image

image

image image image

FrankKai commented 4 years ago

leetcode 排序 解法题目

35. 搜索插入位置

题目：https://leetcode-cn.com/problems/search-insert-position/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/35.Search_Insert_Position.js

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/problems/merge-sorted-array/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/88.Merge_Sorted_Array.js

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/problems/number-of-1-bits/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/191.Number_of_1_Bits.js

/**
 * @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/problems/shortest-unsorted-continuous-subarray/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/581.Shortest_Unsorted_Continuous_Subarray.js

/**
 * @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/problems/rank-transform-of-an-array/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/1331.Rank_Transform_of_an_Array.js

/**
 * @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/problems/merge-intervals/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/56.Merge_Intervals.js

/**
 * @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/problems/kth-largest-element-in-an-array/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/215.Kth_Largest_Element_in_an_Array.js

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

参考资料