阅读 150

数据结构和算法基础之时间复杂度为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²)排序统一做一次对比:

排序方式 是否原地排序 是否稳定排序 最好 最坏 平均
冒泡排序 O(n) O(n²) O(n²)
插入排序 O(n) O(n²) O(n²)
选择排序 × 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++) {
        //这里的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"]);

复制代码

代码分析

其实,类似这种的数据处理,有一个共同的点,就是需要有一个类似插入排序选择排序已排序区,来作为一个targetArray/finalArr。在进行isAllEqual的判断处理就类似于在排序中的数据判断。在满足情况下,进行数据拼接或者数据移动

关注下面的标签,发现更多相似文章
评论