算法入门-排序算法

之前学习了js的相关语法，函数，数组，原型等，现在来学习程序员都要修炼的内功，算法与数据结构

什么是算法？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

算法就是解决问题的一些策略

什么是数据结构？

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

其实数据结构就是数据与数据之间的关系

先从最简单的例子入手

表示两个数据

如果顺序有意义

[x,y]表示第一个是x,第二个是y 那么我们就要提供first和last操作
如果顺序没有意义

(x,y)和(y,x)一样就不需要提供first和last操作

如何表示N个数据

[a1,a2,a3...]
要提供索引操作get(i)
要提供add/indexOf/delete操作

如何表示N对N的数据呢

用哈希表表示
hash={1001=>'小芳'，1002='小红'}

数据结构的作用

提前记住一些结构

这些结构能让你快速理清思路

2.锻炼抽象能力

一种数据结构往往能解决很多类似的问题

如果选错了数据结构，根本就想不出思路

如何快速了解数据结构和算法呢，我打算从排序算法入手

打算了解的几种排序算法

冒泡排序
选择排序
快速排序
归并排序
插入排序
计数排序

排序算法

原理：

比较所有的相邻元素，如果第一个比第二个大，就交换它们

一轮下来，可以保证最后一个数是最大的

执行n-1轮，就可以完成排序

代码实现：

Array.prototype.bubbleSort=function(){
    for(let i=0;i<this.length-1;i++){
        for(let j=0;j<this.length-1-i;j++){
            if(this[j]>this[j+1]){
                const temp=this[j]
                this[j]=this[j+1]
                this[j+1]=temp
            }
        }
    }
}
const arr=[3,12,3,2,3,51,35,1,5,2]
arr.bubbleSort()

让冒泡的算法挂到数组的原型上，这样我们可以直接像调用js原生的sort方法一样去调用

时间复杂度O（n^2）

使用的数据结构：数组

选择排序思路：

找到数组中的最小值，选中它并将其放置到第一位

接着找到第二小的值，选中它放在第二位

递归实现方法：

首先我们实现用递归找出数组中的最小值

let min = (numbers) => {    if (numbers.length > 2) {        // 如果numbers的长度大于2 我们将第一个数字摘出来，其余的数字进行比较        return min([numbers[0], min(numbers.slice(1))])    } else {        // 如果numbers中只有两个数字了  递归的结束条件        return numbers[0] < numbers[1] ? numbers[0] : numbers[1]    }}

然后实现一个通过数组最小值找到数组最小值下标的方法

let minIndex = (numbers) => {    let index = 0    for (let i = 0; i < numbers.length; i++) {        index = numbers[i] < numbers[index] ? i : index    }    return index}

实现选择排序

let chooseSort = (numbers) => {    if (numbers.length > 2) {        // 找出最小值的下标        let index = minIndex(numbers)        let min = numbers[index]        // 从numbers中排除最小值        numbers.splice(index, 1)        return [min].concat(chooseSort(numbers))    } else {        // 如果只有两个数字        return numbers[0] < numbers[1] ? numbers : numbers.reverse()    }}

循环实现方法：

Array.prototype.chooseSort = function () {
    for (let i = 0; i < this.length - 1; i++) {
        let indexMin = i
        for (let j = 0; j < this.length; j++) {
            if (this[j] < this[indexMin]) {
                indexMin = j
            }
        }
        if (indexMin !== i) {
            const temp = this[i]
            this[i] = this[indexMin]
            this[indexMin] = temp
        }
    }
}

时间复杂度O（n^2）

思路：以某某为基准

想象你是一个体育委员，你面对的同学为【12,3,4,6,1,35，55】

以某某为基准，小的去前面，大的去后面

只要重复这句话，就能排序了

实现方法：

Array.prototype.quickSort=()=>{
 const rec=(arr)=>{
   // 先将数组进行分区
   // 我们以第一个同学为基准好了
   const left=[]
   const right=[]
   const mid=arr[0]
   // 从第二个同学开始遍历
   for(let i=1;i<arr.length;i++){
      arr[i]<mid?left.push(arr[i]):right.push(arr[i])
   }
   // 最后将左右区进行递归，按照左中右的顺序输出
   return [...rec(left),mid,...rec[right]]
 }
 const res=rec[this]
 res,forEach((n,i)=>{this[i]=n})
}
const arr = [2, 4, 5, 3, 1];
arr.quickSort(); 
console.log(arr)

这个方法一看就一目了然很简单

递归的时间复杂度为O（logN）

分区的时间复杂度为O（n）

所以时间复杂度为O(N*logN)

用到的数据结构：还是数组

思路：

不以某某为基准了

你现在面对的同学跟刚才一样是【12,3,4,6,1,35，55】

现在你让他们左边一半排好序右边一般排好序

然后左右合并起来

具体思路用图可以这样说明

算法入门-排序算法

具体实现：

let mergeSort=arr=>{    let k=arr.length;    if(k===1){return arr}    let left=arr.slice(0,Math.floor(k/2))    let right=arr.slice(Math.floor(k/2))    return merge(mergeSort(left),mergeSort(right))}let merge=(a,b)=>{    if(a.length===0) return b    if(b.length===0) return a    let res=a[0]>b[0]?[b[0],...merge(a,b.slice(1))]:[a[0],...merge(a.slice(1),b)]    return res}let arr=[3,1,2,5,2]console.log(mergeSort(arr));

mergeSort中其实就是用递归不断的吧数组分成两个部分

merge中对两个部分中的第一个进行比较，小的放到前面去，然后再递归

算法时间复杂度O（n*logn）

思路：

从第二个数开始往前比

比它大就往后排

以此类推到最后一个数

Array.prototype.chooseSort = function () {
    for (var i = 1; i < this.length; i++) {
    首先将要插入的数放在一个临时变量中
        const temp = this[i];
        let j = i;
        j从i往前遍历 如果前面的数比要插入的数大，就把前面的数往后移
        while (j > 0) {
            if (this[j - 1] > temp) {
                this[j] = this[j - 1]
            } else {
                break
            }
            j--
        }
        循环结束后，就将j退出位置下标的数值赋值为要插入的值 即将插入的数放在最小的位置上
        this[j] = temp
    }
}

插入排序的时间复杂度O（n^2）

思路：

用一个哈希表来做记录

发现数组N就记 N：1 如果再次发现N就加1

最后把哈希表的key全部打出来，假设N：m 那么N需要打印m次

在js中有一个数据结构可以很好的实现哈希表，字典 Map

实现方法：

let hashSort=arr=>{    let max=0,res=[]    let hashTable=new Map()    for(let i=0;i<arr.length;i++){        console.log('----');        if(!hashTable.has(arr[i])){            hashTable.set(arr[i],1)        }else{            hashTable.set(arr[i],hashTable.get(arr[i])+1)        }        console.log(hashTable);        console.log(max);        if(arr[i]>max){max=arr[i]}    }    for(let j=0;j<=max;j++){        if(hashTable.has(j)){            for(let i=0;i<hashTable.get(j);i++){                res.push(j)            }        }    }    return res}let arr=[3,2,6,1,7,8,32,12]console.log(hashSort(arr));

算法入门-排序算法