阅读 276

排序算法总结

上个星期没有更,因为没想好写啥。计划每周两更,其中一篇包括TypeScript学习笔记(对,这是一个flag,如果更不了,那我就把这段话重新编辑一下),另外一篇想写啥就写啥。大概就是这样安排的。
写这篇来试个水,一是想自己整理一份排序算法的笔记;二是如果有时间了,也打算整理整理其他数据结构(我要是学会了的话)。如果要问为什么学习算法这些东西,我说不出来什么“职业天花板”类似高水平的话,我只知道:面试要问,所以要学(前端菜鸡,在线卑微)。

认识排序算法

常见排序算法

冒泡排序、选择排序、插入排序、归并排序、计数排序、基数排序、希尔排序、堆排序、桶排序等

简单排序

冒泡排序、选择排序、插入排序

高级排序

希尔排序、快速排序

笔试过程中,首选写自己熟悉的排序,其次优先选择高级排序。最好是写快速排序,快速排序可以说是所有排序算法中最快的(大部分情况下)

时间复杂度

1.时间复杂度指执行当前算法所消耗的时间,用来衡量算法好坏的一个标准。大O表示

符号 名称
O(1) 常数的
O(log(n)) 对数的
O(n) 线性的
O(nlog(n)) 线性和对数乘积的
O(n^2) 平方
O(2^n) 指数的

2.按照表格顺序从上往下,时间复杂度依次递增 (图片来自百度)

推导大O表示法的方式

1.用常量1取代运行时间中所有的加法常数

2.在修改后的运行次数函数中,只保留最高阶项

3.如果最高项存在且不为1,则去除最高阶项的常数

ArrayList类的封装

1.首先在ArrayList类中定义一个数组,因为后面的所有排序方法都是添加到数组上的,调试也都是基于数组的元素的。

2.定义insert方法和toString测试方法,方便插入元素、调试等。

3.定义swap方法,用于两个元素的交换。后续可以在各个排序中直接调用

// ArrayList的封装
class ArrayList{
    //属性
    constructor(){
        this.array = [];
    }

    //插入方法
    insert(ele){
        this.array.push(ele);
    }

    //toString() 调试方法
    toString(){
        return this.array.join();
    }
    
    //交换函数
    swap(i,j){
        let temp = this.array[i];
        this.array[i] = this.array[j];
        this.array[j] = temp;
    }
    
}

// 测试部分
let list = new ArrayList();
list.insert(10);
list.insert(8);
list.insert(3);
list.insert(2);
list.insert(2);
list.insert(4);
list.insert(9);
list.insert(5);
list.insert(4);
list.insert(3);
console.log(list.toString()); //10,8,3,2,2,4,9,5,4,3
复制代码

冒泡排序

是最慢的排序算法之一,但也是一种最容易实现的排序算法。

冒泡排序思想

1.假设正在将一组数字按照升序排列,较大的值会浮动到数组的右侧,而较小的值则会浮动到数组的左侧。比较相邻的数据,当左侧值大于右侧值时将它们进行互换。

  • 对未排序的各元素从头到尾依次比较相邻的两个元素大小关系
  • 如果左侧元素大于右侧元素时,将它们进行互换
  • 向右移动一个位置, 比较下面两个元素
  • 当比较到最右端时, 最大的元素一定被放在了最右边
  • 再从最第一个元素重新开始, 比较到倒数第二个元素

2.特点
第一轮比较后,最大值在最后一个位置(升序情况下)
第二轮比较后,第二大的值在倒数第二个位置;
... ...
... ...

3.代码

//冒泡排序
bubbleSort(){
    //1.获取数组的长度
    let length = this.array.length;
    //2.外层循环控制循环次数
    for(let i=0;i<length;i++){
        //3.内层循环控制循环位置
        for(let j=0;j<length-i;j++){
            //4.如果前一个比后一个位置大, 那么就交换
            if(this.array[j] > this.array[j+1]){
                this.swap(j,j+1);
            }
        }
    }
}

    //写法二(倒着写)
    for(let i=arr.length-1;i>=0;i--){
        for(let j=0;j<i;j++){
            if(arr[j]>arr[j+1]){
                this.swap(j,j+1);
            }
        }
    }
复制代码

冒泡排序效率

1.冒泡排序比较次数

  • 以上面代码为例,10个数据,共9次循环。第一次循环比较了9次,第二次循环比较了8次,...,一共比较了9+8+7+6+5+4+3+2+1 = 45次。

  • 如果是N个数据,则比较了(N-1)+(N-2)+(N-3)···+1 = N*(N-1) / 2 次

2.冒泡排序的大O表示法

  • 比较次数为N*(N-1)/2 = N² / 2 - N / 2
  • 根据上面的规则2:在修改后的运行次数函数中,只保留最高阶项,则为 N² / 2
  • 根据规则3:如果最高项存在且不为1,则去除最高阶项的常数,则为N²
  • 因此冒泡排序的比较次数的大O表示法为O(N²)

3.冒泡排序的交换次数

假设有两次比较才需要交换一次,那么交换次数为N² / 4。交换次数的大O表示也是O(N²)

选择排序

选择排序的效率比冒泡排序稍好一点

选择排序思想

1.选择排序从数组的开头开始,将第一个元素和其他元素进行比较。检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续。这个过程一直进行,当进行到数组的倒数第二个位置时,所有的数据便完成了排序。

2.特点

  • 第一轮比较后,最小值在第一个位置
  • 第二轮比较后,第二小的值在第二个位置

3.代码

//选择排序
selectionSort(){
    //1.获取数组长度
    let length = this.array.length;
    //2.外层循环,从0位置开始取数字
    for(let i=0;i<length;i++){
        //3.内层循环,从i+1位置开始,和后面比较
        for(let j=i+1;j<length;j++){
            //4.如果i位置的数据大于j位置的数据, 就交换
            if(this.array[i] > this.array[j]){
                this.swap(i,j);
            }
        }
    }
}

    // 写法二,利用一个变量来保存最小的位置
    for(let i=0;i<length;i++){
        let min = i;
        for(let j=min+1;j<length;j++){
            if(this.array[min] > this.array[j]){
                min = j;
            }
        }
        this.swap(min,i);
    }
复制代码

选择排序效率

1.选择排序比较次数
10个数时比较9次,9个数时比较8次,... ,N个数时,选择排序的比较次数N*(N-1)/2 次

2.选择排序的大O表示法
比较次数为N*(N-1)/2,比较次数大O表示法为O(N²)

3.选择排序的交换次数
假设每次选择,最多需要交换1次,一共遍历了N-1次;则交换次数为N-1次。
交换次数的大O表示法为O(N)

插入排序

插入排序思想

1.插入排序有两个循环。外循环将数组元素挨个移动,而内循环则对外循环中选中的元素及 它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小,那么数组元素会向右移动,为内循环中的这个元素腾出位置。

  • 假设一个数组,此时需要向里放入一个元素。从第一个元素开始,把这个元素当做是有序的(或者该数组可能有一部分已经排好序)
  • 取出第二个(排好序部分的下一个)元素,在已经排好序的序列中,由该位置从后先前扫描比较
  • 如果被扫描的元素(已经排好序的)大于该元素,则替换位置
  • 重复上一步,找到已排序的元素小于或者等于该元素的位置
  • 将该元素插入到该位置,继续循环重复,直至排序完成

2.注意点

内层循环判断时不仅要保证前一个元素大于当前元素,还要保证前一个元素的索引不超过边界

3.代码

//插入排序
insertionSort(){
    //1.获取数组长度
    let length = this.array.length;
    //2.外层循环,从第一个位置开始往后获取数据
    for(let i=1;i<length;i++){
        //3.记录当前位置,和后面的数据依次比较
        let temp = this.array[i];
        let j = i;
        while (j>0 && this.array[j-1] > temp){
            this.array[j] = this.array[j-1];
            j--;
        }
        //4.比较结束之后,将temp数据放入j位置
        this.array[j] = temp;
    }
}
复制代码

插入排序效率

1.插入排序比较次数

  • 第一趟排序时最多比较1次,第二趟时最多比较2次,... ,第后一趟最多比较N-1次,比较次数一共是N*(N-1) / 2 次
  • 每一趟平均只有一半数据需要比较,所以比较次数是N * (N - 1) / 4
  • 插入排序比较次数的比较次数是前两个排序方法的一半

2.插入排序和其他两种排序的比较

  • 插入排序的效率是高于选择排序和冒泡排序的。对于已经部分有序的数据来说,选择插入排序要好的多。
  • 选择排序和插入排序要比冒泡排序快,插入排序是这三种算法中最快的,冒泡排序是最慢的。

希尔排序

希尔排序是插入排序的升级版

希尔排序算法在插入排序的基础上做了很大的改善。希尔排序的核心理念与插入排序不同,它会首先比较距离较远的元素,而非相邻的元素。和简单地比较相邻元素相比,使用这种方案可以使离正确位置很远的元素更快地回到合适的位置。当开始用这个算法遍历数据集时,所有元素之间的距离会不断减小,直到处理到数据集的末尾,这时算法比较的就是相邻元素了。

希尔排序思想

1.通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列,不过对于大部分的实际应用场景,算法要用到的间隔序列可以提前定义好。
(图片来自百度)

2.以下面图片为例
(图片来自51CTO博客作者NicoChen的原创作品)

  • 已知无序数组为[8,12,6,33,12,5,4,94,63,23,75,22,43,27,46],首先取间隔为7,将数字分组 (8,46,94), (12,63), (6,23), (33,75), (12,22), (5,43), (4,27)
  • 在分好的组中进行比较,如果前一个数字大于后面数字,则二者交换位置(注意:交换的是未分组时的位置)
  • 再取间隔为3,分组为(8,33,4,23,43),(12,12,46,75,27),(6,5,63,22,94),重复上一步操作
  • 最后取间隔为1,完成最终排序

3.希尔排序的增量

增量就是指,排序时所采取的间隔,

  • 希尔建议的初始间距是 N/2 ,简单的把每趟排序分成两半即可。
  • 采用hibbard增量时,增量算法为 h(i)=2^i−1,即1,3,5,7,...

4.代码

//希尔排序
shellSort(){
    //1.获取数组长度
    let length = this.array.length;
    //2.初始化增量
    let gap = Math.floor(length / 2);
    //3.while循环
    while (gap >= 1){
        //4.循环取出分组中的数,进行插入排序
        for(let i=gap;i<length;i++){
            let temp = this.array[i];
            let j = i;
            while(this.array[j-gap]>temp && j>gap-1){
                this.array[j] = this.array[j-gap];
                j -= gap;
            }
            //5.j位置放入temp
            this.array[j] = temp;
        }
        //6.增量的变化
        gap = Math.floor(gap / 2);
    }
}
复制代码

希尔排序效率

  • 希尔排序的效率和增量的选取有关系
  • 经过统计,希尔排序使用原始增量,最坏的情况下时间复杂度为O(N²),通常情况下都要好于O(N²)
  • 希尔排序的效率高于简单排序

快速排序

快速排序是冒泡排序的升级版

快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法,通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直 到所有数据都是有序的。

快速排序思想

首先要在列表中选择一个元素作为基准值(pivot)。数据排序围绕基准值进行,将列表中小于基准值的元素移到数组的左边,将大于基准值的元素移到数组的右边。再将左右两边的数组看成是一个整体,选择基准值进行递归操作。重复递归直到排序完成。

快速排序的基准值

基准值决定了快速排序的效率,尽可能选择某个中间值的元素作为基准值,能够把数组等分,此时效率是最高的。

1.选取基准值的方法

  • 取一个较小的位置赋给left,取另外一个较大的位置赋给right,利用center = (left + right)/2,得到center的位置。
  • 取出这三个位置的值,对这三个数进行比较排序,选出中位数当做基准值。

2.代码

//基准值的确定
pivot(left,right){
    //1.取出中间的位置
    let center = Math.floor((left + right) / 2);

    //2.判断大小,进行交换
    if (this.array[left] > this.array[center]) {
        this.swap(left, center);
    }
    if (this.array[center] > this.array[right]) {
        this.swap(center, right);
    }
    if (this.array[left] > this.array[right]) {
        this.swap(left, right);
    }

    //3.将center移动到right前面一个位置
    this.swap(center,right-1);

    //4.返回基准值
    return this.array[right-1];
}
复制代码

3.测试

原数组为[10, 8, 3, 2, 2, 4, 9, 5, 4, 3]

console.log(list.pivot(1, 8)); //pivot值为4
console.log(list); //[10, 8, 3, 2, 2, 5, 9, 4, 4, 3]
复制代码

4.快速排序完整代码

//快速排序
quickSort() {
    this.quickSortRec(0, this.array.length - 1)
}

quickSortRec(left, right) {
    // 1.递归结束条件
    if (left >= right) return;

    // 2.获取基准值
    let pivot = this.pivot(left, right);

    // 3.开始进行交换
    //3.1 记录左边开始位置和右边开始位置
    let i = left;
    let j = right - 1;
    //3.2 循环查找位置
    while (true) {
        while (this.array[++i] < pivot) { }
        while (this.array[--j] > pivot) { }
        if (i < j) {
            //2.3 交换位置
            this.swap(i, j)
        } else {
            break
        }
    }

    // 4.将枢纽放在正确的位置
    this.swap(i, right - 1);

    // 5.递归调用
    this.quickSortRec(left, i - 1);
    this.quickSortRec(i + 1, right)
}
复制代码

快速排序效率

  • 快速排序的平均效率是O(N * logN).
  • 其他某些算法的效率也可以达到O(N * logN), 但是快速排序是最好的。

完整代码

<script>
  // ArrayList的封装
  class ArrayList{
    //属性
    constructor(i,j){
      this.array = [];
    }

    //插入方法
    insert(ele){
      this.array.push(ele);
    }

    //toString() 方便调试
    toString(){
      return this.array.join();
    }

    //交换函数
    swap(i,j){
      let temp = this.array[i];
      this.array[i] = this.array[j];
      this.array[j] = temp;
    }

    //冒泡排序
    bubbleSort(){
      //1.获取数组的长度
      let length = this.array.length;
      //2.外层循环控制循环次数
      for(let i=0;i<length;i++){
        //3.内层循环控制循环位置
        for(let j=0;j<length-i;j++){
            //4.如果前一个比后一个位置大, 就交换
            if(this.array[j]>this.array[j+1]){
            this.swap(j,j+1);
          }
        }
      }
    }

    //选择排序
    selectionSort(){
      //1.获取数组长度
      let length = this.array.length;
      //2.外层循环,从0位置开始取数字
      for(let i=0;i<length;i++){
        //3.内层循环,从i+1位置开始,和后面比较
        for(let j=i+1;j<length;j++){
          //4.如果i位置的数据大于j位置的数据, 就交换
          if(this.array[i] > this.array[j]){
            this.swap(i,j);
          }
        }
      }
    }

    //插入排序
    insertionSort(){
      //1.获取数组长度
      let length = this.array.length;
      //2.外层循环,从第一个位置开始往后获取数据
      for(let i=1;i<length;i++){
        //3.记录当前位置,和后面的数据依次比较
        let temp = this.array[i];
        let j = i;
        while (j>0 && this.array[j-1] > temp){
          this.array[j] = this.array[j-1];
          j--;
        }
        //4.比较结束之后,将temp数据放入j位置
        this.array[j] = temp;
      }
    }

    //希尔排序
    shellSort(){
      //1.获取数组长度
      let length = this.array.length;
      //2.初始化增量
      let gap = Math.floor(length / 2);
      //3.while循环
      while (gap >= 1){
        //4.循环取出分组中的数,进行插入排序
        for(let i=gap;i<length;i++){
          let temp = this.array[i];
          let j = i;
          while(this.array[j-gap]>temp && j>gap-1){
            this.array[j] = this.array[j-gap];
            j -= gap;
          }
          //5.j位置放入temp
          this.array[j] = temp;
        }
        //6.增量的变化
        gap = Math.floor(gap / 2);
      }
    }

    //基准值的确定
    pivot(left,right){
      //1.取出中间的位置
      let center = Math.floor((left + right) / 2);

      //2.判断大小,进行交换
      if (this.array[left] > this.array[center]) {
        this.swap(left, center);
      }
      if (this.array[center] > this.array[right]) {
        this.swap(center, right);
      }
      if (this.array[left] > this.array[right]) {
        this.swap(left, right);
      }

      //3.将center移动到right前面一个位置
      this.swap(center,right-1);

      //4.返回基准值
      return this.array[right-1];
    }


    //快速排序
    quickSort() {
      this.quickSortRec(0, this.array.length - 1)
    }
    
    quickSortRec(left, right) {
      // 1.递归结束条件
      if (left >= right) return; //如果left位置大于或者等于right位置,说明左右两边和基准值得比较结束了

      // 2.获取基准值
      let pivot = this.pivot(left, right);

      // 3.开始进行交换
      //3.1 记录左边开始位置和右边开始位置
      let i = left;
      let j = right - 1;
      //3.2 循环查找位置
      while (true) {
        while (this.array[++i]<pivot && i<j) { } //如果左边的值小于基准值,则不用排序
        while (this.array[--j]>pivot && i<j) { } //如果右边的值大于基准值,则不用排序
        if (i < j) {
          //2.3 交换位置
          this.swap(i, j)
        } else {
          break
        }
      }

      // 4.将枢纽放在正确的位置
      this.swap(i, right - 1);

      // 5.递归调用
      this.quickSortRec(left, i - 1);
      this.quickSortRec(i + 1, right)
    }
  }

  // 测试部分
  let list = new ArrayList();
  list.insert(10);
  list.insert(8);
  list.insert(3);
  list.insert(2);
  list.insert(2);
  list.insert(4);
  list.insert(9);
  list.insert(5);
  list.insert(4);
  list.insert(3);
  // console.log(list.toString()); //10,8,3,2,2,4,9,5,4,3

  // list.bubbleSort();
  // console.log(list);

  // list.selectionSort();
  // console.log(list);

  // list.insertionSort();
  // console.log(list);

  // list.shellSort();
  // console.log(list);

  // console.log(list.pivot(2, 8));
  // console.log(list);

  list.quickSort();
  console.log(list);
  
</script>
复制代码

总结:虽说这个排序算法是JavaScript版本,但是在某些可以直接用数组的API的地方并没有直接使用,比如快速排序还有更精简版本。可以自行搜索看看。

本文参考书籍:《数据结构与算法JavaScript描述》

本文图片均来自百度,有出处的已注明出处,如有不妥立马删除。