- 算法入门
- 排序算法升级-选择排序的循环
- 排序算法升级-快速排序
- 排序算法升级-归并排序
- 排序算法升级-计数排序
-曾老湿, 江湖人称曾老大。
-多年互联网运维工作经验，曾负责过大规模集群架构自动化运维管理工作。 -擅长Web集群架构与自动化运维，曾负责国内某大型金融公司运维工作。 -devops项目经理兼DBA。 -开发过一套自动化运维平台（功能如下）： 1)整合了各个公有云API，自主创建云主机。 2)ELK自动化收集日志功能。 3)Saltstack自动化运维统一配置管理工具。 4)Git、Jenkins自动化代码上线及自动化测试平台。 5)堡垒机，连接Linux、Windows平台及日志审计。 6)SQL执行及审批流程。 7)慢查询日志分析web界面。
算法入门
如何找到两个数中较小的那个数 |
|---|
首先，我们的想法应该是如何表示两个数字？
如果你能想到，使用[a,b]数组，来表示，就说明你在使用数据结构
使用判断，或者问号，冒号表达式
代码如下
代码语言：javascript复制let minOf2 = (numbers) => {
if(numbers[0] < numbers[1]){
return numbers[0]
}else{
return numbers[1]
}
}优化代码
代码语言：javascript复制let minOf2 = numbers => numbers[0] < numbers[1] ? numbers[0] : numbers[1]再优化代码
代码语言：javascript复制let minOf2 = ([a,b]) => a<b ? a : b调用
代码语言：javascript复制//小白调用
minOf2([1,2])
//高手调用
minOf2(null,[1,2])

当然了，JS已经提供了现成的方法Math.min
Math.min(1,2)
Math.min.call(null,1,2)
Math.min.apply(null,[1,2])

举一反三，三个数字呢 |
|---|
求三个数字中间最小的。
代码语言：javascript复制let minOf3 = ([a,b,c]) => {
return minOf2(minOf2[(a,b)],c)
}
let minOf3 = ([a,b,c]) => {
return minOf2(a,minOf2([b,c]))
}推理，如果是4个数字呢？
代码语言：javascript复制let minOf4 = ([a,b,c,d]) => {
return minOf2([a,minOf3(b,c,d)])
}任意长度数组求最小值，都可以通过minOf2实现。
推广：任意长度的数组 |
|---|
代码如下
代码语言：javascript复制let min = (numbers) => {
return min(
[numbers[0],min(numbers.slice(1))]
)
}
//这个代码会死循环，不停的调用自己，需要添加一个终止条件其他方法
代码语言：javascript复制let min = (numbers) => {
if(numbers.length > 2){
return min(
[numbers[0],min(numbers.slice(1))]
)
}else{
return Math.min.apply(null,numbers)
}
}
//这就是递归递归的特点： 1.函数不停的调用自己，每次调用的参数略有不同 2.当满足某个简单条件时，则实现一个简单的调用 3.最终算出结果
将正整数数组从小到大排序 |
|---|
排序算法： 1.递归 2.循环
递归思路，选择排序：
长度为2的数组排序
代码语言：javascript复制let sort2 = ([a,b]) => {
if(a<b){
return [a,b]
}else{
return [b,a]
}
}优化代码
代码语言：javascript复制let sort2 = ([a,b]) => a<b ? [a,b] : [b,a]长度为3的数组排序
代码语言：javascript复制let sort3 ([a,b,c]) => {
return [min([a,b,c]),sort2([???])]
}
//我们发现无法将最小值，从数组里面删掉改进代码
代码语言：javascript复制let sort3 = (numbers) => {
let index = minIndex(numbers)
let min = numbers[index]
numbers.splice(index,1)
return [min].concat(sort2(numbers))
}
//定义minIndex
let minIndex = (numbers) =>
numbers.indexOf(min(numbers))长度为4
代码语言：javascript复制let sort4 = (numbers) =>{
let index = minIndex(numbers)
let min = numbers[index]
numbers.splice(index,1)
return [min].concat(sort3(numbers))
}任意长度排序 |
|---|
let sort = (numbers) => {
let index = minIndex(numbers)
let min = numbers[index]
numbers.splice(index,1)
return [min].concat(sort(numbers))
}
//和之前一样，这个代码会死循环优化代码：
代码语言：javascript复制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()
}
}

排序算法升级-选择排序的循环
使用循环重写minIndex |
|---|
let minIndex = (numbers) => {
let index = 0
for(let i=1;i<numbers.length;i ){
if(numbers[i] < numbers[index]){
index = i
}
}
return index
}由此可见，所有的递归，都可以改成循环
使用循环重写sort |
|---|
let sort = (numbers) =>{
for(let i=0;i<???;i ){
let index = minIndex(numbers)
//index是当前最小数的下标
//index对应的数，应该放到i处
swap(numbers,index,i) //swap还没实现
}
}怎么知道 i<??? 应该写什么？
分析代码：
假设numbers的长度为n = 4
n | i | |
|---|---|---|
4 | 0 | swap(numbers,index,0),index可能为0/1/2/3 |
4 | 1 | swap(numbers,index,1),index可能为0/1/2/3 |
4 | 2 | swap(numbers,index,2),index可能为0/1/2/3 |
4 | 3 | swap(numbers,index,3),index可能为0/1/2/3 |
我们会发现，minIndex 的查找范围是有问题的，每次都会找 0 1 2 3，我们已经找完了最小的，所以我们应该忽略上一次找到的最小的。
代码语言：javascript复制let sort = (numbers) =>{
for(let i=0;i<???;i ){
let index = minIndex(numbers.slice(i)) i
swap(numbers,index,i) //swap还没实现
}
}分析代码：
假设numbers的长度为n = 4
n | i | |
|---|---|---|
4 | 0 | swap(numbers,index,0),index可能为1/2/3 |
4 | 1 | swap(numbers,index,1),index可能为2/3 |
4 | 2 | swap(numbers,index,2),index可能为3 |
4 | 3 | numbers.slice(3),是[i],所以i=3不行,i<n-1 |
最终代码：
代码语言：javascript复制let sort = (numbers) =>{
for(let i=0;i<numbers.length -1;i ){
console.log('----')
console.log(`i:${i}`)
let index = minIndex(numbers.slice(i)) i
console.log(`index:${index}`)
console.log(`min:${numbers[index]}`)
if(index !== i){
swap(numbers,index,i)
console.log(`swap ${index}:${i}`)
}
}
return numbers
}实现swap |
|---|
let swap = (array,i,j) =>{
let temp = array[i]
array[i] = array[j]
array[j] = temp
}
swap(numbers,1,2)


实现swap |
|---|
//删除log最终写法
let sort = (numbers) =>{
for(let i=0;i<numbers.length -1;i ){
let index = minIndex(numbers.slice(i)) i
if(index !== i){swap(numbers,index,i)}
}
return numbers
}
let swap = (array,i,j) =>{
let temp = array[i]
array[i] = array[j]
array[j] = temp
}
let minIndex = (numbers) => {
let index = 0
for(let i=1;i<numbers.length;i ){
if(numbers[i] < numbers[index]){
index = i
}
}
return index
}排序算法升级-快速排序
递归思路 |
|---|
军训的时候，教官都会说，以 xxx 为基准，小的在前，大的在后，你会发现，很快...就排完序了。
[12,3,7,21,5,9,4,6]
阮一峰版代码如下：
代码语言：javascript复制let quitSort = arr =>{
if(arr.length <= 1){return arr}
let pivotIndex = Math.floor(arr.length/2);
let pivot = arr.splice(pivotIndex,1)[0];
let left = [];
let right = [];
for(let i=0;i<arr.length;i ){
if(arr[i] < pivot){
left.push(arr[i])
}else{
right.push(arr[i])
}
}
return quickSort(left).concat([pivot])
}排序算法升级-归并排序
归并排序思路，你还是一个体育委员。
你面对的同学是 [12,3,7,21,5,9,4,6]
左边一半让他们自动排好序，右边一半让他们自动排好序，然后把两个合并起来
代码如下：
代码语言：javascript复制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 meger(mergeSort(left),mergeSort(right))
}
let merge = (a,b) => {
if(a.length === 0) return b
if(b.length === 0) return a
return a[0] > b[0] ?
[b.[0]].concat(merge(a,b.slice(1))) :
[a.[0]].concat(merge(a.slice(1),b))
}排序算法升级-计数排序
计数排序思路： 用一个哈希表做记录 发现数字N 就记 N:1，如果再次发现N就加一 最后把哈希表的key全部打出来，架设N:m，那么N需要打印m次
代码如下：
代码语言：javascript复制let countSort = arr => {
let hashTable = {}, max = 0, result = []
for(let i=0;i<arr.length;i ){
//遍历数组
if(!(i in hashTable)){
hashTable[arr[i]] = 1
}else{
hashTable[arr[i]] = 1
}
if(arr[i] > max){max = arr[i]}
}
for(let j=0;j<=max;j ){
//遍历hash表
if(j in hashTable){
result.push(j)
}
}
return result
} //目前代码有bug计数排序代码2
代码语言：javascript复制let countSort = arr => {
let hashTable = {}, max = 0, result = []
for(let i=0;i<arr.length;i ){
//遍历数组
if(!(i in hashTable)){
hashTable[arr[i]] = 1
}else{
hashTable[arr[i]] = 1
}
if(arr[i] > max){max = arr[i]}
}
for(let j=0;j<=max;j ){
//遍历hash表
if(j in hashTable){
for(let i = 0; i<hashTable[j];i ){
result.push(j)
}
}
}
return result
}计数排序的特点 |
|---|
数据结构不同：
1、使用了额外的hashTable 2、只遍历数组一遍（不过还要遍历一次hashTable） 3、这叫做用空间换时间
时间复杂度对比：
选择排序 O(n2 ) 快速排序 O(n log2 n) 归并排序 O(n log2 n) 计数排序 O(n max)
还有哪些排序？
冒泡排序:TP 插入排序:TP点INS 希尔排序:TP 基数排序:TP点RAD
堆排序

排序算法:TP
