数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。

本章内容衔接上一章　数据结构与算法：二分查找

两种基本数据结构：

数组

常见操作: 数组降维、数组去重

链表

递归：递归是很多算法都使用的一种编程方法

　　- 如何将问题分成基线条件和递归条件
　　- 分而治之策略解决棘手问题

栈

　- 调用栈(call stack)
　- 递归调用栈

常见排序算法：很多算法仅在数据经过排序后才管用。如二分查找,它只能用于有序元素列表。

　- 冒泡排序
　- 选择排序
　- 插入排序
　- 希尔排序
　- 归并排序
　- 快速排序
　- 堆排序
　- 计数排序
　- 桶排序
　- 基数排序

需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。需要存
储多项数据时,有两种基本方式——数组和链表。但它们并非都适用于所有的情形,因此知道它
们的差别很重要

给出：let arr = [[1, 2, 3], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10, 0];
需求：降维、去重、排序
做法：Array.from(new Set(arr.flat(Infinity).sort((a, b) => a - b)))


解析如下：
0. arr.flat(Infinity)  //直接降维值一维数组。
1. sort     //排序就不说了。
2. new Set()  //达到去重效果
3. Array.from(上一步输出的结果)  //将上一步结果转换为数组

递归（recursion）：程序调用自身的编程技巧。

递归满足2个条件：

有反复执行的过程（调用自身）

有跳出反复执行过程的条件（递归出口）

递归就是指在定义一个概念和过程时，又用到了本身。
哲学的将, 递归的妙用就在，如果一个过程中又包含自身，那么这个过程就可以无穷地展开，不会在有穷的步骤后停止。但是描述这个过程只需要有穷的指令。以有穷表现无穷。

在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。
另外多提一句，递归和lambda 演算是两个与图灵机等价的计算机理论模型，感兴趣的读者可以去进一步研究，这里不赘述。

由于递归函数调用自己,编写这样的函数时很容易出错,导致无限循环。

例:编写这样倒计时的函数。

5...4...3...2...1

为此,你可以用递归的方式编写:

 const countdown = (i) => {
    console.log(i)
    // base case 基准条件
    if (i <= 0){
      return null
    } 
    // 隐藏的else是　递归条件
    countdown(i-1)
    return null
  }

  countdown(5)

编写递归函数时,必须告诉它何时停止递归。正因为如此,每个递归函数都有两部分:基线
条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则
指的是函数不再调用自己,从而避免形成无限循环。

可以去掉基准条件执行下代码：

  const countdown = (i) => {
    console.log(i)
    // base case 基准条件
    // if (i <= 0){
    //   return null
    // } 
    // 隐藏的else是　递归条件
    countdown(i-1)
    return null
  }

  countdown(5)

因为无限循环导致Maximum call stack size exceeded error

n! = n (n-1) (n-2) ... 1(n>0)

// 阶乘
const fact = (x) => {
  if(x === 1) {
    return 1
  }
  return x * fact(x - 1) 
}

console.log(fact(5))

斐波那契数列可以定义为以下序列：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

可以看到，该序列是由前两项数值相加而成的。这个数列的历史非常悠久，至少可以追溯 到公元700年。它以意大利数学家列奥纳多·斐波那契（Leornardo Fibonacci）的名字命 名，斐波那契在1202年使用这个数列描述理想状态下兔子的增长。

这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值

这个函数的问题在于它的执行效率非常低

有太多值在递归调用中被重新计算。如果编译器可以将已经计算的值记录下来，函

数的执行效率就不会如此差。我们可以使用动态规划的技巧来设计一个效率更高的算法。

动态规划的本质其实就是两点：

自底向上分解子问题

通过变量存储已经计算过的解

根据上面两点，我们的斐波那契数列的动态规划思路:

斐波那契数列从 0 和 1 开始，那么这就是这个子问题的最底层

通过数组来存储每一位所对应的斐波那契数列的值

树的最大深度：该题目来自 Leetcode，题目需要求出一颗二叉树的最大深度

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
   if(!root) return 0
   return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 
};

对于该递归函数可以这样理解：一旦没有找到节点就会返回 0，每弹出一次递归函数就会加一，树有三层就会得到 3。
但是递归真的很慢

我们可以写一个函数 用以递归的快速计算

// memoize 全局函数：用以阶乘，斐波那契数组等递归调用的快速计算
// useage: const memoizeFibonacci = memoize(fibonacci); memoizeFibonacci(45)

export function memoize(fn) {
  const cache = {};
  return function () {
    const key = JSON.stringify(arguments);
    var value = cache[key];
    if (!value) {
      value = [fn.apply(this, arguments)]; // 放在一个数组中，方便应对undefined，null等异常情况
      cache[key] = value;
    }
    return value[0];
  }
}

Stack Overflow上说的一句话:“如果使用循环,程序的性能可能更高;如果使用递归,程序可能
更容易理解。如何选择要看什么对你来说更重要。” Recursion or Iteration?

栈是一个线性结构，在计算机中是一个相当常见的数据结构。

栈的特点是只能在某一端添加或删除数据，遵循先进后出的原则

每种数据结构都可以用很多种方式来实现，其实可以把栈看成是数组的一个子集，所以这里使用数组来实现

arr = [2,3,6,5,33,7,23]

def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+i]:
                arr[j],arr[j + i] = arr[j + i], arr[j]
    return arr

print(bubbleSort(arr))

arr = [2,3,6,5,33,7,23]

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时， 将i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

print(selectionSort(arr))

arr = [2,3,6,5,33,7,23]

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

print(insertionSort(arr))

arr = [2,3,6,5,33,7,23]

def shellSort(arr):
    import math
    gap = 1
    while(gap < len(arr)/3):
        gap = gap*3 + 1
    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i - gap
            while j >= 0 and arr[j] >temp:
                arr[j+gap] = arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr

print(shellSort(arr))

下一篇文章 数据结构与算法:二叉树算法

JS-Sorting-Algorithm
javascript描述数据结构与算法（改自imooc）
算法图解
常见算法ｊｓ实现
javascript-algorithms
排序算法总结