排序算法

~ 排序算法(上)

算法里面最简单的就是排序算法，这节课主要讲选择排序。\算法入门:四种排序算法(选择、归并、快速、技术)和对应的结构。

实现minOf2:2个数找出较小的那个

再优化

析构赋值:把结构拆开，依次复制let?minOf2=([a,b])?=>?a?<?b???a?:?b?//调用minOf2([1,2])?//小白调用法minOf2.call(null,[1,2])?//高手调用法

现成API\JS内置了Math.min\Math.min(1,2)\Math.min.call(null,1,2)\Math.min.apply(null,[1,2])\关于Math\看起来Math像Object一样是构造函数\实际上Math只是普通对象，唯一一个首字母大写的对象，对象一般首字母小写

实现minOf3:3个数找出最小的那个

推广，任意长度数组求最小值

递归\特点\函数不停调用自己，每次调用的参数略有不同\当满足某个简单条件时，则实现一个简单的调用\最终算出结果\理解\可以用代入法快速理解递归\可以用调用栈快速理解递归

解析代入法，先递进后回归

知识点\1.numbers.slice(1)选中从下标1开始的所有数据\2.Math.min.apply(null,numbers)\apply就是把numbers一个个展开调用。call就是把numbers作为一项。

var?arr?=?[1,3,6,8,2,10];var?minNum?=?Math.min.apply(null,arr);console.log(minNum);??//1

Math.min可以实现得到数组中最小的一项\Math.min.apply(null,arr)其中第一个参数null，这个是因为没有对象去调用这个方法，所以直接传递null过去。同理,Math.max.apply可以获得数组里面最大的值。

实现sort排序(将正整数数组从小到大排序)

排序算法\思路:1'用递归实现、2'用循环实现

递归思路

选择排序\例1.将长度为2的数组排序

例2.将长度为3的数组排序\思路:先求最小值，把最小值放前面。\然后将后面2个数字进行"2个数的排序"。

let?minIndex?=?(numbers)?=>?numbers.indexOf(min(numbers))?//取巧:如果有2个最小数，只会返回第1个最小数的下标。let?sort3?=?(numbers)?=>?{//获取最小数字的下标??let?index?=?minIndex(numbers)?//minIndex函数??let?min?=?numbers[index]//获取最小数下标后再将其删掉,返回被保留的数字??numbers.splice(index,?1)???return?[min].concat(sort2(numders))}

知识点\1.JS中concat用于2个数组的相加，拼成一个数组\2.sort2(numders)得到的是排好序的2个数\3.numbers.indexOf求出某个数字的下标

例3.将长度为4的数组排序

推广，任意长度的数组排序\死循环，到2个数时不会断。

要理解递归，必须用代入法

选择排序:每次找到最小的数放前面，然后对后面的数做同样的事情。

例子:假设我没理解splice,于是我写了rest,实际上splice会返回被删除部分而不是被余下部分。

let?minIndex?=?(numbers)?=>?numbers.indexOf(min(numbers))?let?sort?=?(numbers)?=>?{??if(numbers.length>2){????let?index?=?minIndex(numbers)?????let?min?=?numbers[index]????let?rest=numbers.splice(index,1)????return?[min].concat(sort(rest))??}else{??????return?numbers[0]<numbers[1]?numbers:numbers.reverse()??}}

分析报错\当前代码属于匿名的函数,调用了sort,sort调用了minIndex，minIndex调用了min,并发现min不存在。\这个就叫做调用栈，函数调了函数，前面的函数就要压到栈里面。\它说没有定义那就一定没有定义，找原因。\1.<anonymous>，当前代码属于匿名的函数\2.atsort，调用了sort

结果不符合预期，把每一步的结果打出来

推断出rest有问题那怎么拿到剩余的数呢？

总结\1.求最小值:2个数、3个数、N个数\2.排序:2个数、3个数、N个数\用到的东西:数组(数据结构)、递归\1.请写一个min函数，要求min(numbers)能返回数组numbers中的最小数字。

let?min?=?(numbers)?=>?{??if(numbers.length?>?2){????return?min([numbers[0],?min(numbers.slice(1))])??}else{????return?Math.min.apply(null,?numbers)??}}

2.请写出一个sort函数，要求sort(numbers)能返回一个把numbers从小到大排列的数组

let?minIndex?=?(numbers)?=>?numbers.indexOf(min(numbers))let?sort?=?(numbers)?=>?{??if(numbers.length?>?2){????let?index?=?minIndex(numbers)????let?min?=?numbers[index]????numbers.splice(index,?1)????return?[min].concat(sort(numbers))??}else{????return?numbers[0]<numbers[1]???numbers?:?numbers.reverse()??}}sort([21,8,44,92])

排序算法(下)

算法入门:四种排序算法和对应的结构。

所有算法都有2种写法递归和循环。\目前的minIndex,看着就繁琐。

let?minIndex?=?(numbers)?=>?numbers.indexOf(min(numbers))let?min?=?(numbers)?=>?{??return?min(?[numbers[0],?min(numbers.slice(1))]?)}

minIndex重写

let?minIndex?=?(numbers)?=>??let?index=0?//默认下标为0开始??for(let?i=1;i<numbers.length;i++){//默认从第2个开始比????if(numbers[i]<numbers[index]){??????index=i????}??}??return?index}

默认返回下标为0(默认第1个数是最小的数)，然后用每个数跟它比。\哪个数字比它小就把下标置为那个小的数字。\所有递归都能改为循环

面试题\四种排序算法以及时间复杂度

改写sort:选择排序的循环写法

思路不变:\每次找到最小的数放前面，然后对后面的数做同样的的事情,然后i++。

let?sort?=?(numbers)?=>?{??if(numbers.length?>?2){????let?index?=?minIndex(numbers)????let?min?=?numbers[index]????numbers.splice(index,?1)????return?[min].concat(sort(numbers))??}else{????return?numbers[0]<numbers[1]???numbers?:?numbers.reverse()??}}

实现swap

let?swap?=?(array,?i,?j)?=>?{??let?temp?=?array[i]??array[i]?=?array[j]??array[j]?=?temp}swap(numbers,?1,?2)

思考1.错误地实现swap

思考2.怎么知道?处应该写什么\暴力分析

假设numbers的长度为n=4,推算出i最大为2。

重新分析代码

最终代码

var?arr?=?[1,3,6,8,2,10];var?minNum?=?Math.min.apply(null,arr);console.log(minNum);??//10

知识点\1.JSES6析构赋值实现交换ab值

var?arr?=?[1,3,6,8,2,10];var?minNum?=?Math.min.apply(null,arr);console.log(minNum);??//11

2.交换值lettemp=a;a=b;b=temp\3.JS删除数组中的某个元素默认返回的还是数组，要取数组的第[0]项

总结\所有递归都能改成循环。循环的时候有很多细节:\这些细节很难想清楚,要动手列出表格找规律,\尤其是边界条件很难确定,我们没有处理长度为0和1的数组。\学会debug

快速排序

递归思路\以某某为基准

8个人就要指定8次。\快速排序-阮一峰

归并排序

递归思路\不以某某为基准

merge的逻辑图

计数排序

整理扑克牌的过程就是计数排序\这就是哈希表:A有几个，2有几个，3有几个...

最终代码:当j出现两次时(当12出现了2次时，就push2次)

如果你的数据结构升级了，你的算法就会直接升级。\技术排序的特点\事件复杂度对比

其它排序算法\冒泡排序\插入排序\希尔排序\基数排序

原文：https://juejin.cn/post/7095686492164489229

---

排序算法视频