排序，搜索，算法模式，算法复杂度 | 数据结构与算法综合笔记

淩亂°似流年 2021-07-24 17:39 334阅读 0赞

*  图
 *  树
 *  字典,散列表
 *  集合
 *  链表
 *  队列
 *  栈

> 冒泡排序，选择排序，插入排序，归并排序，快速排序，堆排序，顺序搜索，二分搜索算法

### 排序算法 ###

*  先创建一个数组来表示待排序和搜索的数据结构

function ArrayList(){ 
     var array = []; //将项存储在数组中
     
     this.insert = function(item){ //插入方法来向数据结构中添加元素
         array.push(item); 
     }; 
     
     this.toString = function(){ //来拼接数组中的所有元素至一个单一的字符串
         return array.join(); 
     }; 
    }
    // join方法拼接数组元素至一个字符串，并返回该字符串

### 冒泡排序 ###

*  冒泡排序在运行时间的角度来看，是最差的。

原理：

> 冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动到正确的顺序，就像气泡升至表面一样，冒泡排序因此得名。

实现冒泡排序：

this.bubbleSort = function(){ 
     var length = array.length; // 用来存储数组的长度
     
     for (var i=0; i<length; i++){ 
     // 会从数组的第一位迭代至最后一位，它控制了在数组中经过多少轮排序 
     // 应该是数组中每项都经过一轮，轮数和数组长度一致
         for (var j=0; j<length-1; j++ ){ 
         //内循环将从第一位迭代至倒数第二位
         //内循环实际上进行当前项和下一项的比较
             if (array[j] > array[j+1]){ 
                 swap(array, j, j+1); //{5} 
             } 
         } 
     } 
    };
    
    // 声明swap函数
    // 一个私有函数
    var swap = function(array, index1, index2){ 
     var aux = array[index1];
     array[index1] = array[index2]; 
     array[index2] = aux; 
    };
    // 我们用一个中间值来存储某一交换项的值

ES6写法：

[array[index1], array[index2]] = [array[index2], array[index1]];

> 从内循环减去外循环中已跑过的轮数

进阶冒泡排序：

this.modifiedBubbleSort = function(){ 
         var length = array.length; 
         
         for (var i=0; i<length; i++){ 
             for (var j=0; j<length-1-i; j++ ){ //避免内循环中所有不必要的比较
                 if (array[j] > array[j+1]){ 
                     swap(j, j+1); 
                 } 
             } 
         } 
    };

### 选择排序(一种原址比较排序算法) ###

> 原理：找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推

示例：

this.selectionSort = function(){ 
     var length = array.length, indexMin; 
     
     for (var i=0; i<length-1; i++){ 
         indexMin = i; 
         for (var j=i; j<length; j++){ 
             if(array[indexMin]>array[j]){ 
                 indexMin = j; 
             } 
         } 
         if (i !== indexMin){ 
             swap(i, indexMin); 
         } 
     } 
    };

![25d573a59faaac464849ac520bdae80e.png][] image.png

### 插入排序 ###

> 插入排序每次排一个数组项，以此方式构建最后的排序数组

示例：

this.insertionSort = function(){ 
     var length = array.length, j, temp; 
     
     for (var i=1; i<length; i++){ 
         j = i; 
         temp = array[i];  
         while (j>0 && array[j-1] > temp){ 
             array[j] = array[j-1];  
             j--; 
         } 
         array[j] = temp; 
     } 
    };

![0d6bdf475f12cbc494d49d18694f2783.png][] image.png

### 归并排序 ###

> 归并排序是第一个可以被实际使用的排序算法

原理：

> 将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

*  归并排序是一种分治算法
 *  归并排序也是递归的

this.mergeSort = function(){ 
     array = mergeSortRec(array); 
    };

递归函数

// 归并排序将一个大数组转化为多个小数组直到只有一个项
    var mergeSortRec = function(array){ 
     var length = array.length; 
     
     if(length === 1) { //判断数组的长度是否为1 
     return array; //返回这个长度为1的数组 
     } 
     
     var mid = Math.floor(length / 2), //如果数组长度比1大，那么我们得将其分成小数组
     
     left = array.slice(0, mid), 
     //left数组由索引0至中间索引的元素组成
     
     right = array.slice(mid, length); 
     //right数组由中间索引至原始数组最后一个位置的元素组成
     
     return merge(mergeSortRec(left), mergeSortRec(right)); //将数组分成两个小数组
     
    };

示例：

// merge函数接受两个数组作为参数
    // 并将它们归并至一个大数组
    var merge = function(left, right){ 
     var result = [], // 声明归并过程要创建的新数组 
     il = 0, 
     ir = 0;
     
     while(il < left.length && ir < right.length) { // 迭代两个数组
     // 比较来自left数组的项是否比来自right数组的项小
         if(left[il] < right[ir]) { 
             result.push(left[il++]); 
             // 将该项从left数组添加至归并结果数组，并递增迭代数组的控制变量
         } else{ 
             result.push(right[ir++]); 
             // 从right数组添加项并递增相应的迭代数组的控制变量
         } 
     } 
     
     while (il < left.length){ // {11} 
         result.push(left[il++]); 
     } 
     
     
     while (ir < right.length){ // {12} 
         result.push(right[ir++]); 
     } 
     
     return result; // {13} 
    };

![a92467ab4efce7c2fc4f87cb1d0b337f.png][] image.png

### 快速排序 ###

*  从数组中选择中间一项作为主元
 *  创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项
 *  移动左指针直到我们找到一个比主元大的元素
 *  移动右指针直到找到一个比主元小的元素

示例：

this.quickSort = function(){ 
     quick(array, 0, array.length - 1); 
    };

示例：

var quick = function(array, left, right){ 
    
     var index; //该变量能帮助我们将子数组分离为较小值数组和较大值数组
     if (array.length > 1) { //因为只有一个元素的数组必然是已排序了的
         index = partition(array, left, right); //。partition函数返回值将赋值给index 
         
         if (left < index - 1) { //如果子数组存在较小值的元素 
             quick(array, left, index - 1); //对该数组重复这个过程
         } 
         if (index < right) { //对存在较大值的子数组 如果存在子数组存在较大值
             quick(array, index, right); //对该数组重复这个过程
         } 
     } 
     
    };

*  划分过程

1.选择主元

划分过程：

var partition = function(array, left, right) { 
    
     var pivot = array[Math.floor((right + left) / 2)], //选择中间项作为主元
     i = left, //初始化两个指针 初始化为数组第一个元素
     j = right; //初始化两个指针 初始化为数组最后一个元素
     
     while (i <= j) { //只要left和right指针没有相互交错就执行划分操作
         while (array[i] < pivot) { //移动left指针直到找到一个元素比主元大
             i++; 
         } 
         while (array[j] > pivot) { //移动right指针直到我们找到一个元素比主元小
             j--; 
         } 
         if (i <= j) { //当左指针指向的元素比主元大且右指针指向的元素比主元小
         // 左指针索引没有右指针索引大 左项比右项大
             swap(array, i, j); //交换它们，然后移动两个指针
             i++; 
             j--; 
         } 
     } 
     return i;  
    };

展示图：

![730333e30c728e24e4e5a3bded32ccf4.png][] image.png

*  下面的示意图展示了对有较小值的子数组执行的划分操作

![65853f644ee80f8bd0a082cd7c41a199.png][] image.png

*  继续创建子数组，请看下图

![0b85e2ff6bd1b8b8232904a937d7e5ef.png][] image.png

*  继续进行划分

![57fadb85649d3c6e6a4910ff2f8310f2.png][] image.png

*  继续进行划分

![d2f83ae855f4bd6dbdee30f886a7afe4.png][] image.png

### 堆排序 ###

*  **一种很高效的算法**
 *  **把数组当作二叉树来排序而得名**

1.索引0是树的根节点；

2.除根节点外，任意节点N的父节点是N/2；

3.节点L的左子节点是2\*L；

4.节点R的右子节点是2\*R+1

数组`[3, 5, 1, 6, 4, 7, 2]`想象成下面的树

![d2ca68fcb6afb0f97fd1a7161eb3ebb3.png][] image.png

示例：

this.heapSort = function() { 
    
     var heapSize = array.length; 
     
     buildHeap(array); //构造一个满足array[parent(i)] ≥ array[i]的堆结构
     
     while (heapSize > 1) { 
         heapSize--; 
         
         swap(array, 0, heapSize); //交换堆里第一个元素和最后一个元素的位置
         
         heapify(array, heapSize, 0); 
         //找到当前堆的根节点（较小的值），重新放到树的底部
     } 
     
    };

`buildHeap`函数实现如下

var buildHeap = function(array){ 
    
     var heapSize = array.length; 
     
     for (var i = Math.floor(array.length / 2); i >= 0; i--) { 
         heapify(array, heapSize, i); 
     } 
     
    };

堆的构建过程如下：(调用`buildHeap`函数)

数组`[3, 5, 1, 6, 4, 7, 2]`

![7fef8f9fa631b4b4151e089fdc979565.png][] image.png

var heapify = function(array, heapSize, i){ 
    
     var left = i * 2 + 1, 
     right = i * 2 + 2, 
     largest = i; 
     
     if (left < heapSize && array[left] > array[largest]) { 
         largest = left; 
     } 
     
     if (right < heapSize && array[right] > array[largest]) { 
         largest = right; 
     } 
     
     if (largest !== i) { 
         swap(array, i, largest); 
         heapify(array, heapSize, largest); 
     } 
     
    };

![3ee7df2e7d72203fb0f03d71cb2b886a.png][] image.png

### 排序(分布式排序) ###

1.计数排序

2.桶排序

3.基数排序

> 最著名的分布式算法有计数排序、桶排序和基数排序

### 搜索算法-顺序搜索 ###

*  顺序或线性搜索是最基本的搜索算法
 *  将每一个数据结构中的元素和我们要找的元素做比较

示例：

this.sequentialSearch = function(item){ 
     for (var i=0; i<array.length; i++){ //顺序搜索迭代整个数组
         if (item === array[i]) //将每个数组元素和搜索项作比较
             return i; //搜索成功 
             // 返回值可以是该搜索项本身，或是true，又或是搜索项的索引
         } 
     } 
     return -1; //没有找到该项，则返回-1 表示该索引不存在
    };

### 搜索算法-二分搜索 ###

游戏示例：一个1到100的数字游戏。我们每回应一个数字，那个人就会说这个数字是高了、低了还是对了。

示例：

this.binarySearch = function(item){ 
     this.quickSort(); //需要先将数组排序 
     var low = 0, //  在数组排序之后，我们设置low和high指针
     high = array.length - 1, 
     mid, element; 
     
     while (low <= high){ //当low比high小时
     
         mid = Math.floor((low + high) / 2); 
         element = array[mid]; 
         
         if (element < item) { 
         //比较选中项的值和搜索值
             low = mid + 1; 
         } else if (element > item) { 
             high = mid - 1; 
         } else { 
             return mid; 
         } 
     } 
     
     return -1; //我们计算得到中间项索引并取得中间项的值
     //此处如果low比high大，则意思是该待搜索值不存在并返回-1
    };

执行的步骤：

![234d34c1e34a538d9e47ebe8c0d09294.png][] image.png

> 冒泡、选择、插入、归并、快速以及堆排序算法，顺序搜索和二分搜索

### 算法模式 ###

*  递归
 *  动态规划
 *  贪心算法

示例:

function recursiveFunction(someParam){ 
     recursiveFunction(someParam); 
    };

function recursiveFunction1(someParam){ 
     recursiveFunction2(someParam); 
    }; 
    function recursiveFunction2(someParam){ 
     recursiveFunction1(someParam); 
    };

*  它会一直执行下去(栈溢出错误)。(需要一个不再递归调用的条件)

> JavaScript 调用栈大小的限制

示例：

var i = 0; 
    
    function recursiveFn () { 
     i++; 
     recursiveFn(); 
    } 
    
    try { 
     recursiveFn(); 
    } catch (ex) { 
     alert('i = ' + i + ' error: ' + ex); 
     // 超限错误：超过最大调用栈大小
     // 内部错误：递归次数过多
    }

*  es6尾调用优化

### 斐波那契数列 ###

*  1和2的斐波那契数是 1
 *  n（n>2）的斐波那契数是(n1)的斐波那契数加上(n2)的斐波那契数

示例：

// 边界条件是已知的，1和2的斐波那契数是1
    function fibonacci(num){ 
     if (num === 1 || num === 2){ //{1} 
     return 1; 
     } 
    }

function fibonacci(num){ 
     if (num === 1 || num === 2){ 
     return 1; 
     } 
     return fibonacci(num - 1) + fibonacci(num - 2); 
    }
    // 当n大于2时，Fibonacci(n)等于Fibonacci(n-1)+Fibonacci(n-2)

用非递归的方式实现斐波那契函数：

function fib(num){ 
     var n1 = 1, 
     n2 = 1, 
     n = 1; 
     
     for (var i = 3; i<=num; i++){ 
         n = n1 + n2; 
         n1 = n2; 
         n2 = n; 
     } 
     
     return n; 
    }

### 动态规划 ###

一些著名的问题如下:

*  背包问题
 *  最长公共子序列
 *  矩阵链相乘
 *  硬币找零
 *  图的全源最短路径

### 函数式编程简介 ###

函数式编程是借助ES6的能力，JavaScript也能够进行函数式编程

用命令式编程，声明的函数如下：

var printArray = function(array) { 
     for (var i = 0; i < array.length; i++) { 
         console.log(array[i]); 
     } 
    }; 
    
    printArray([1, 2, 3, 4, 5]);

函数式编程:(重点是需要描述什么，而不是如何描述)

var forEach = function(array, action) { 
     for (var i = 0; i < array.length; i++) { 
         action(array[i]); 
     } 
    };
    
    var logItem = function (item) { 
     console.log(item); 
    };
    
    forEach([1, 2, 3, 4, 5], logItem);

1.目标是描述数据，以及要对数据应用的转换

2.程序执行顺序的重要性很低，而在命令式编程中，步骤和顺序是非常重要的

3.函数和数据集合是函数式编程的核心

4.在函数式编程中，我们可以使用和滥用函数和递归，而在命令式编程中，则使用循环、 赋值、条件和函数

### map ###

把一个数据集合转换或映射成另一个数据集合

### filter ###

使用`filter`函数过滤一个集合的值

### reduce ###

把一个集合归约成一个特定的值

### 算法复杂度 ###

*  著名的大O表示法
 *  和NP完全理论

### 大 O 表示法 ###

![1b26f34688cd507d3fcc5a0da7fa71a8.png][] image.png

*  当讨论大O表示法时，一般考虑的是CPU（时间）占用

> O(1)

// 函数的复杂度是O(1)
    // 和参数无关，increment函数的性能都一样
    function increment(num){ 
     return ++num; 
    }

> O(n)

// 时间复杂度是O(n)
    // n是（输入）数组的大小
    function sequentialSearch(array, item){ 
     for (var i=0; i<array.length; i++){ 
     if (item === array[i]){ //{1} 
     return i; 
     } 
     } 
     return -1; 
    }

### 时间复杂度比较 ###

![a3ea4fd9a7c6065c4ed3f2ae0c3538b9.png][] image.png

常用数据结构的时间复杂度:

![3d686e2bf545cff43087f3c3bca3005a.png][] image.png

图的时间复杂度:

![224a1cbdb286e0ed4c5301854127ab9f.png][] image.png

排序算法的时间复杂度:

![c913e86378f45966c7ff5e3a7d0d26ef.png][] image.png

搜索算法的时间复杂度：

![3b113e2020a47db5aa315125445772ea.png][] image.png

### NP 完全理论 ###

*  `NP（nondeterministic polynomial，非确定性多项式）`算法
 *  对于给定的问题，如果存在多项式算法，则计为`P（polynomial，多项式）`
 *  如果一个问题可以在多项式时间内验证解是否正确，则计为`NP`
 *  `NP`问题中最难的是`NP`完全问题

1.是`NP`问题，也就是说，可以在多项式时间内验证解，但还没有找到多项式算法

2.所有的`NP`问题都能在多项式时间内归约为它

> `P`、`NP`、`NP`完全和`NP`困难 问题 图：

![5453fc932e767bb1fe2d8c6e3e9706ec.png][] image.png