数据结构和算法基础之时间复杂度为O(n²)排序(偏向前端方向)

在实际项目开发中,不管是后端还是前端,最基本的操作就是数据的CRUD。换句话说,后端是根据某些条件 组装 数据,前端是拿着后端提供的数据,进行数据 展示 。但是不管在进行数据封装还是展示,其中在特定的场景下,需要根据某些条件,对数据进行排序。而在既定的现有框架下,都有现成的方法对数据进行排序处理。

但是,在开发中,有没有想过,这些排序底层是如何实现的,还有就是针对不同的数据,不同的排序是否在 性能 方面有不同的体现。

后端的数据排序不在本文的讨论中,本文只针对前端的排序的一些 思路实践 .(该文只在前端范围内讨论排序的实现)

前端案例分析

现在有一组数据如下:

0: {layoutId: 1028, priceCodeId: 1000408, activityId: 0, roomNum: 1}
1: {layoutId: 1028, priceCodeId: 1000408, activityId: 0, roomNum: 1}
2: {layoutId: 1028, priceCodeId: 1000408, activityId: 0, roomNum: 1}
3: {layoutId: 1029, priceCodeId: 1000409, activityId: 1, roomNum: 1}
4: {layoutId: 1029, priceCodeId: 1000409, activityId: 1, roomNum: 1}
5: {layoutId: 1269, priceCodeId: 1000410, activityId: 2, roomNum: 1}
复制代码

现在有一个需求就是,需要更加 layoutId,priceCodeId,activityId 这个三个 组合主键 来对 roomNum 进行求和。

处理结果如下:

0: {layoutId: 1028, priceCodeId: 1000408, activityId: 0, roomNum: 3}
1: {layoutId: 1029, priceCodeId: 1000409, activityId: 1, roomNum: 2}
2: {layoutId: 1069, priceCodeId: 1000410, activityId: 2, roomNum: 1}
复制代码

不要惊讶,这不是后台处理逻辑,这是一个 真真切切 的前端数据处理逻辑。有的前端可能会说,数据处理是后台的事。这个前端不好处理,我想说,如果是这个思维方式,感觉你被其他语言开发工程师 鄙视理所当然 的。

所以,我信奉一个道理:

菜并不可怕,不敢正视自己的弱点才是最可怕的。

其实类似上述的问题,可能用JS的一些现有的库,可能很好实现,但是这个文章没有选择这些现有库,而是以一种最原始的方式来实现。或许还能有更好的方式来实现,欢迎大家 批评指导

需要指出的是,这个案例和本文讲的排序没有很大的关系,但是在文末的实现的时候,用到了一些排序的 思路方法和方式

在开始之前,需要明确几个概念: 原地排序稳定性

  • 原地排序:特指 空间复杂度 是 O(1) 的排序算法
  • 稳定性:如果待排序的序列中存在 值相等 的元素,经过排序之后,相等元素之间原有的先后顺序不变。如果相同的值 前后顺序 没有发生变化,叫 稳定的排序算法 ;如果前后顺序发生变化,那对应的排序算法就叫作 不稳定的排序算法

冒泡排序(Bubble Sort)

冒泡排序只会 操作相邻 的两个数据。每次冒泡操作都会对相邻的两个元素进行 比较 ,看是否满足大小关系要求。如果不满足就让它俩互换。 一次冒泡会让至少一个元素移动到它应该在的位置 ,重复 n 次,就完成了 n 个数据的排序工作。

现在我们假设有 29,10,14,37,14 这些数据,需要按 升序 排序

Talk is cheap. Show you the code

arr 为待排序数组,n为数组个数

  • 版本1:
function BubbleSort1(arr,n){
    if(n<=1) return ;
    for(let i=0;i<n;i++){
        for(let j = i+1;j<n;j++){
            if(arr[i]>arr[j]){
                let tempValue = arr[i];
                arr[i] = arr[j];
                arr[j] = tempValue;
            }
        }
    }
    return arr;
}
复制代码
  • 版本2:
function bubbleSort2(arr, n) {
    if (n <= 1) return;
   
   for (let i = 0; i < n; ++i) {
      // 提前退出冒泡循环的标志位
      let flag = false;
      for (let j = 0; j < n - i - 1; ++j) {
        if (arr[j] > arr[j+1]) { // 交换
          let tmp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = tmp;
          flag = true;  // 表示有数据交换      
        }
      }
      if (!flag) break;  // 没有数据交换,提前退出
    }
  }
复制代码

note

  • 上面的两个实现方式都是 升序排列 ,但是如果你用断点追或者实际模拟一遍就会发现,这两个版本的数据移动方向是 相反 的。 版本1的是先把较小数据排列好,版本2是把较大数据排列好
  • 结合 原地排序稳定性 来分析,冒泡排序的空间复杂度为 O(1),是一个 原地排序算法 。只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性, 当有相邻的两个元素大小相等的时候,我们不做交换 ,相同大小的数据在排序前后 不会改变顺序 ,所以冒泡排序是 稳定的排序算法

插入排序(Insertion Sort)

插入排序具体的实现思路就是:找到已存数据列表中插入位置,将数据 插入对应位置 。是一个 找茬 算法。

思路分析

将数组中的数据分为 两个区间已排序区间未排序区间初始 已排序区间 只有 一个元素,就是数组的 第一个元素 。插入算法的 核心思想 是取未排序区间中的元素,在已排序区间中找到 合适的插入位置 将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

我们还是以 29,10,14,37,14 为例。

Talk is cheap. Show you the code

arr 为待排序数组,n为数组个数

function insertionSort(arr, n) {
    if (n <= 1) return;
   
    for (let i = 1; i < n; ++i) {
      let value = arr[i];
      //确定已排序区间,这里的j是一个"哨兵",守卫者"边界"
      let j = i - 1;
      // 查找插入的位置(这里的) --j也就是从已排中找对应合适的位置
      for (; j >= 0; --j) {
        if (arr[j] > value) {
          arr[j+1] = arr[j];  // 数据移动
        } else {
          break;
        }
      }
      arr[j+1] = value; // 插入数据
    }
  }
复制代码

note

  • 结合 原地排序稳定性 来分析:不需要额外的存储空间,所以 空间复杂度是 O(1) ,插入排序是 原地排序算法 。在插入排序中,对于值相同的元素,我们可以 选择将后面出现的元素,插入到前面出现元素的后面 ,这样就可以保持原有的前后顺序不变,所以插入排序是 稳定的排序算法

选择排序(Selection Sort)

选择排序算法的 实现思路 有点类似插入排序,也分 已排序区间和未排序区间 。但是选择排序每次会从未排序区间中 找到最小的元素 ,将其放到 已排序区间的末尾

我们还是以 29,10,14,37,14 为例。 屏幕录制 2019-09-27 下午2.30.52_52.gif

Talk is cheap. Show you the code

function selectionSort(arr) {
    let len = arr.length;
    let minIndex, temp;
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}
复制代码

note

  • 原地排序 :是原地排序
  • 稳定排序 : 不是稳定排序 ,比如 5,8,5,2,9 这样一组数据,使用选择排序算法来排序的话,第一次找到最小元素 2,与第一个 5 交换位置,那第一个 5 和中间的 5 顺序就变了,所以就不稳定了。

要点汇总

针对这三种时间复杂度都为O(n²)排序统一做一次对比:

排序方式 是否原地排序 是否稳定排序 最好 最坏 平均
冒泡排序 :white_check_mark: :white_check_mark: O(n) O(n²) O(n²)
插入排序 :white_check_mark: :white_check_mark: O(n) O(n²) O(n²)
选择排序 :white_check_mark: × O(n²) O(n²) O(n²)

文末彩蛋

在刚开始的时候,有一个 纯前端 的数据 聚合 问题。话不多说,来段代码尽尽兴。 嗨皮一下

来咯,来咯。

版本1:

function polymerizationData(sourceArr, flagKeyArr, targetKeyArr) {
  let tempSourceArr = [...sourceArr];
  let targetArr = tempSourceArr.splice(0, 1);
  while (tempSourceArr.length) {
    for (let i = 0; i < targetArr.length; i++) {
      let outerItem = targetArr[i];
      let j = 0;
      for (; j < tempSourceArr.length; j++) {
        let innerItem = tempSourceArr[j];
        let isAllEqual = true;
        for (let flagindex = 0; flagindex < flagKeyArr.length; flagindex++) {
          if (innerItem[flagKeyArr[flagindex]] != outerItem[flagKeyArr[flagindex]]) {
            isAllEqual = false;
            break;
          }
        }
        if (isAllEqual) {
          for (let targetKeyIndex = 0; targetKeyIndex < targetKeyArr.length; targetKeyIndex++) {
            outerItem[targetKeyArr[targetKeyIndex]] += innerItem[targetKeyArr[targetKeyIndex]]
          }
          tempSourceArr.splice(j, 1);
          j = -1;
        } else {
          targetArr.push(tempSourceArr.splice(j, 1)[0]);
          break;
        }
      }
    }
  }
  return targetArr;
}
复制代码

版本2(版本1的升级版)

function AdvancePolymerizationData(sourceArr, flagKeyArr, targetKeyArr) {
  let storeDesignationKey = {};
  let tempSourceArr = [...sourceArr];
  let finalArr = tempSourceArr.splice(0, 1);
  flagKeyArr.map(item => {
    storeDesignationKey[item] = finalArr[0][item];
  })
  let i = 0, j = 0;
  for (; i < tempSourceArr.length; i++) {
    let isEqual = flagKeyArr.every(item => {
      return tempSourceArr[i][item] == storeDesignationKey[item]
    })
    if (isEqual) {
      targetKeyArr.map(item => {
        finalArr[j][item] += tempSourceArr[i][item]
      })
      tempSourceArr.splice(i, 1);
      i = -1;
    } else {
      let requirePushItem = tempSourceArr.splice(i, 1)[0];
      flagKeyArr.map(item => {
        storeDesignationKey[item] = requirePushItem[item];
      })
      finalArr.push(requirePushItem);
      j++;
      i = -1;
    }
  }
  return finalArr;
}

复制代码

上面的代码调用方式

AdvancePolymerizationData(sourceArray, ["layoutId", "priceCodeId", "activityId"], ["roomNum"]);

复制代码
我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章