八大算法的整体和汇总

2020-06-20

算法的详细分模块学习

八大算法

排序

1. 时间复杂度

时间复杂度来表示执行的次数,,树容量N有关,下面详细讲解基本排序的时间复杂度

1.1 冒泡排序

思路

最外层遍历将最大的元素放在最后
内层遍历前面的最值

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
//1.冒泡排序
/*
每次都将最大值放在最优的位置
*/
function bubbleSort(arr) {
  if (arr == null || arr.length < 2) {
    return
  }
  for (var i = arr.length - 1; i > 0; i--) {
    //内部选出交换比较出最大值
    for (var j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        //交换位置
        swap(arr, j, j + 1)
      }
    }
  }
}

时间复杂度的分析O(n^2)
空间:O(1)
稳定

1.2 选择排序

思路

每次都从后面元素中选出最值存放在前面,依次类推,两层循环嵌套

时间复杂度==O(n^2)

//2.选择排序
/*
选择排序就是将后面元素的最值放在前面,最外面的循环从0开始,里面的循环找最值
*/
function selectSort(arr) {
  if (arr == null || arr.length < 2) {
    return
  }
  for (var i = 0; i < arr.length; i++) {
    //记录当前最小位置的索引
    var minIndex = i;
    for (var j = i + 1; j < arr.length; j++) {
      minIndex = arr[j] < arr[minIndex] ? j : minIndex;
    }
    //找到最小值之后和当前排序好的指定位置交换,每次找到后面最小值的值依次从0开始的位置放置
    swap(arr, i, minIndex)
  }
}

时间复杂度:O(N^2)
空间复杂度:O(1)
不稳定

1.3 插入排序

思路
插入排序 :从第一位开始排序,始终保证前面的元素是排好序的,每次从后面未排的元素中依次取出元素和拍好序的元素进行对比并插入到排好序的元素中
插入排序和数组是否有序有直接关系

时间复杂度

插入排序和是否有序有关
- 有序:O(n)
- 逆序:N*交换次数N=O(n^2)
时间复杂度以最坏情况下为基础
不稳定

// 3.插入排序
/*
插入排序 :从第一位开始排序,始终保证前面的元素是排好序的,每次从后面未排的元素中依次取出元素和拍好序的元素进行对比并插入到排好序的元素中
插入排序和数组是否有序有直接关系
*/
function InsertSort(arr) {
  if (arr == null || arr.length < 2) {
    return
  }
  //外层遍历依次递增,表示新插入到有序队列中的元素
  for (var i = 1; i < arr.length; i++) {
    //内层遍历主要是通过一次添加后面的元素和前面排好序的元素进行比较,满足条件的情况下进行交换,从后往前两两比较
    for (var j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
      //新插入的元素小于前面的元素交换,一次比较,直到有序
      swap(arr, j, j + 1)
    }
  }
}

1.4 排序的对数器

test函数
- testTime:测试次数
- size:数组的长度
- value:数值范围
- sortType:排序算法的类型

const { bubbleSort, InsertSort, selectSort } = require('./01_sort')

//4 对数器(解决case)来测试代码是否合适
function generateSort(size, value) {
  /*
  size:生成数组的长度
  value:生成数组的数值范围
  */
  //1.生成随机的数组长度(0-size)
  var arr = new Array(parseInt(Math.random() * (size + 1)));
  //为每个数值生成随机的数
  for (var i = 0; i < arr.length; i++) {
    // 为数组的每个数值生成随机的数值,相减有正负之分,
    arr[i] = parseInt(Math.random() * (value + 1)) - parseInt(Math.random() * (value + 1));
  }
  return arr
}

//通过数组对数器结合一个系统提供的绝对正确的方法
function sort(arr) {
  arr.sort((a, b) => a - b)
}

// 克隆数组
function cloneArr(arr) {
  var clone = [];
  for (var i = 0; i < arr.length; i++) {
    clone[i] = arr[i]
  }
  return clone
}

// 比较两个数组是否相等
function isEqual(arr1, arr2) {
  if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
    return false
  }
  if (arr1 == null && arr2 == null) return true
  if (arr1.length != arr2.length) {
    return false;
  }
  for (var i = 0; i < arr1.length; i++) {
    //数值不相等则返回false
    if (arr1[i] != arr2[i]) {
      return false
    }
  }
  //执行到最后结果都满足
  return true
}

//通过计数器来测试当前的三个排序算法
function test(testTime, size, value, sortType) {
  var testTime = testTime;
  var size = size;
  var value = value;
  success = true
  for (var i = 0; i < testTime; i++) {
    //生成随机样本发生器
    var arr = generateSort(size, value)
    var arr1 = cloneArr(arr)
    var arr3 = cloneArr(arr)
    //通过绝对正确的排序检测arr
    sort(arr);
    //测试自己写的排序算法
    sortType(arr1)
    //比较结果是否相同
    if (!isEqual(arr, arr1)) {
      //只要有一个不一样说明测试不通过直接返回
      console.log(arr3);//出错打印出错的样本
      success = false
      break
    }
  }
  console.log(success ? '测试通过' : '测试失败')
}

递归

1 时间复杂度

1.1 递归通用的时间复杂度分析(Master定理)

a:表示一共这个过程发生了多少次,就看代码中发生的次数(也就是递归调用的次数),不用看执行的次数
N/b:子样本量
T(N/b):子样本量的时间复杂度
O(N^d):除去子过程调用之外,剩下过程的时间复杂度是多少

master公式的使用范围:划分子过程的规模是一样的,也就是每次b的值是一样,只是发生的次数a不一样

计算时间复杂度的网址

2 复杂度练习

2.1 递归求解数组中的最大

思路

先求解左边的最大值,
在求解右边的最大值
在求左右两边的最大值
递归结束的条件是:start==end

代码

//通过递归实现求解最大值
/*
递归实现的过程就是不断压栈的过程,每次递归都会将所有的数据都压入栈中,还原现场
*/
function getMax(arr, start, end) {
  if (start == end) {
    //当只有一个数的时候,此时直接返回
    return arr[start]
  }
  // 求左右两边的最大值,然后进行不断划分
  var mid = parseInt((start + end) / 2)

  var left = getMax(arr, start, mid)
  var right = getMax(arr, mid + 1, end)
  //返回两边的最大值
  return Math.max(left, right)
}
var arr = [3, 4, 2, 5, 6, 7, 9]
console.log(getMax(arr, 0, arr.length - 1));

时间复杂度分析(满足master)

logb(a)=log2(2)=1>0,所以O(N^(logb(a)))=O(N)

2.2 归并排序(采用的是分治的思想)

分析

第一，归并排序是原地排序算法吗？这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。实际上，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。所以，归并排序不是原地排序算法。
第二，归并排序是稳定的排序算法吗？ merge 方法里面的 left[0] <= right[0] ，保证了值相同的元素，在合并前后的先后顺序不变。归并排序是一种稳定的排序方法。
第三，归并排序的时间复杂度是多少？从效率上看，归并排序可算是排序算法中的佼佼者。假设数组长度为 n，那么拆分数组共需 logn 步, 又每步都是一个普通的合并子数组的过程，时间复杂度为 O(n)，故其综合时间复杂度为 O(nlogn)。 最佳情况：T(n) = O(nlogn)。最差情况：T(n) = O(nlogn)。平均情况：T(n) = O(nlogn)。

思路

先数组划分为两部分
左右两侧排好序
通过外排,增加临时存储数组temp
添加指针分别指向有序的两部分数组,从头到尾依次比较,谁小谁将值存储在temp中并一定指针,直到有一个先到数组结尾,归并结束
判断两个数组是否同时到达数组结尾,没有直接将后面的元素直接添加到temp中,归并排序结束

分析时间复杂度

空间复杂度

占用了arr数组长度,O(N)

代码

function mergeSort(arr) {
  if (arr == null || arr.length < 2) {
    return
  }
  sortProcess(arr, 0, arr.length - 1)
}
//子数组排序
function sortProcess(arr, left, right) {
  if (left == right) {
    return
  }
  var mid = parseInt((left + right) / 2);
  sortProcess(arr, left, mid)//T(N/2)
  sortProcess(arr, mid + 1, right)//T(N/2)
  merge(arr, left, mid, right)//O(N)

}
//归并
function merge(arr, left, mid, right) {
  var temp = []
  leftIndex = left;
  rightIndex = mid + 1;
  while (leftIndex <= mid && rightIndex <= right) {
    temp.push(arr[leftIndex] < arr[rightIndex] ? arr[leftIndex++] : arr[rightIndex++])
  }
  //长出来的部分直接添加到最后
  while (leftIndex <= mid) {
    temp.push(arr[leftIndex++])
  }
  while (rightIndex <= right) {
    temp.push(arr[rightIndex++]);
  }
  //通过循环将temp保存在arr
  for (var i = 0; i < temp.length; i++) {
    // 注意从left的位置开始重新复值给arr
    arr[left++] = temp[i];
  }
}

2.3 小和问题(归并排序的思想来解决)

在一个数组中，每个数左边比当前数小的数累加起来，叫做这个数组的小和，求一个数组的小和

思路

(1)直接遍历，时间复杂度为O（N^2）

(2)通过归并排序

分析

[1,3,4,2,5]

1:左边比1小的数:没有

3：左边比3小的数：1

4…..:1,3,

2,…..: 1

5…..:1,3,4

小和=1+1+3++1+1+3+4=16

在归并的过程中,如果左边比右边的小,产生小和,(右边的当前指向到末尾有几个值就有左边所指位置的值*指的个数个小和)

问题的转换:求当前位置的值左边比他自身小的值====求当前值右边比他大的值

注意归并排序是没有返回值的,小和问题和逆序问题只是在归并的基础了多了求和问题和返回值问题

//这里借助归并排序来解决小和问题

// 2.小数和
function smallSum(arr) {
  if (arr == null || arr.length < 2) {
    return 0
  }
  return mergeSort(arr, 0, arr.length - 1)
}
//子数组排序
function mergeSort(arr, left, right) {
  if (left == right) {
    return 0
  }
  var mid = parseInt((left + right) / 2);
  return mergeSort(arr, left, mid) +
    mergeSort(arr, mid + 1, right) +
    merge(arr, left, mid, right)

}
//归并
function merge(arr, left, mid, right) {
  var temp = []
  leftIndex = left;
  rightIndex = mid + 1;
  // 保存小数和,和归并排序相比多的代码
  var result = 0;
  while (leftIndex <= mid && rightIndex <= right) {
  	//归并排序相比多的代码
    result += arr[leftIndex] < arr[rightIndex] ? (right - rightIndex + 1) * arr[leftIndex] : 0;
    temp.push(arr[leftIndex] < arr[rightIndex] ? arr[leftIndex++] : arr[rightIndex++])
  }
  //长出来的部分直接添加到最后
  while (leftIndex <= mid) {
    temp.push(arr[leftIndex++])
  }
  while (rightIndex <= right) {
    temp.push(arr[rightIndex++]);
  }
  //通过循环将temp保存在arr
  for (var i = 0; i < temp.length; i++) {
    // 注意从left的位置开始重新复值给arr
    arr[left++] = temp[i];
  }
  return result
}
var arr = [1, 3, 4, 2, 5]
console.log(smallSum(arr));

2.4 逆序问题(归并排序思想解决)

题目

求数组中存在的逆序对,这里和小数和正好相反(只需修改左边的数比右边的数大,改变指针的走向,将大数归并)

思路

(1) 遍历,事件复杂度:O(N^2)

(2)归并排序的时间复杂度:nlogn

归并排序快的原因是:去除了重复的操作,在归并的过程中

代码


// 2.归并排序来解决逆序对的问题
function reversePair(arr) {
  if (arr == null || arr.length < 2) {
    return 0
  }
  return mergeSort(arr, 0, arr.length - 1)
}
//子数组排序
function mergeSort(arr, left, right) {
  //递归终止的条件
  if (left == right) {
    return 0
  }
  var mid = (left + right) >> 1;
  return mergeSort(arr, left, mid) +
    mergeSort(arr, mid + 1, right) +
    merge(arr, left, mid, right)


}
//归并
function merge(arr, left, mid, right) {
  var temp = []
  leftIndex = mid;
  rightIndex = right;
  //暂存数组的长度
  tempIndex = right - left;
  //保存逆序数
  var count = 0
  while (leftIndex >= 0 && rightIndex > mid) {
    //较大的数归并,改变指针的走向,注意这里的条件和小和问题相反,取左边的大于右边的,才构成逆序,这里归并的是大的数,和归并排序的不同之处
    count += arr[leftIndex] > arr[rightIndex] ? (rightIndex - mid) : 0;

    temp[tempIndex--] = arr[leftIndex] > arr[rightIndex] ? arr[leftIndex--] : arr[rightIndex--]
  }
  //长出来的部分直接添加到最后
  while (leftIndex >= 0) {
    temp[tempIndex--] = arr[leftIndex--];
  }
  while (rightIndex > mid) {
    temp[tempIndex--] = arr[rightIndex--];
  }
  //通过循环将temp保存在arr
  for (var i = 0; i < temp.length; i++) {
    // 注意从left的位置开始重新复值给arr
    arr[left++] = temp[i];
  }
  //返回计算的逆序对数
  return count
}

快排

1 数组划分(partion)

1.1 大于num的放右边,小于放左边(划分为两部分)

思路

本题主要考察的是指针和交换问题
设置小于部分的区域为less,less初始值=-1
当当前值大于num,cur++
小于num和less的下一个值交换,less++,扩大less的范围

注意:这里不考虑是否有序的问题

复杂度

时间:O(N)
空间:O(1)

代码

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;

}
function partionTwo(arr, num) {
  var less = - 1;
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < num) {
      swap(arr, ++less, i)
    }
  }
  return arr
}

1.2 荷兰国旗问题(划分为3部分)

题目

将数组划分为3部分,大于,等于,和小于

思路

设置三个指针,分别指向左边区域less,右边区域more和当前区域cur
当cur>num arr[–more]和arr[cur]交换位置,当前位置不变继续比较
cur<num arr[++less]和arr[cur++]交换位置,当前位置++
cur = num cur++
结束条件是cur==more

注意:less和more始终指向的less区域和more区域的边界,++less到–more之间的值都是等于num的区间范围,依然不考虑是否有序的问题

复杂度

时间:O(N)
空间:O(1)

代码

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;

}
// 2.荷兰国旗问题(划分为三部分)
function partionThree(arr, L, R, num) {
  var less = L - 1;
  var more = R + 1;
  var cur = L;
  while (cur < more) {
    if (arr[cur] < num) {
      swap(arr, ++less, cur++)
    } else if (arr[cur] > num) {
      // 注意这里cur不能移动,还要和左边的比较当前值
      swap(arr, --more, cur)
    } else {
      cur++
    }
  }
   //返回的是等于num的子数组的下标志起始位置和终止位置
  return [less + 1, more - 1]
}
console.log(partionThree(arr, 0, arr.length - 1, 5))

2 随机快排

2.1 递归实现(增加了递归的partition问题)

思路

快排可以看做在和荷兰问题的基础上不断递归左右已经划分好的子数组,最终返回排序好的数组
这里可以进行优化,在递归的过程中不在重复计算已经等于num的数值
快排每次将数组的最后的一个数看成基础的base=num来进行荷兰问题递归

复杂度

时间:nlogn
空间:O(logn),只需执行过程中保存的断点的个数(划分的次数)需要额外的空间存储,断点组成是一个树,logN
注意:快速排序有序归并排序,好在快排的常数项小,空间复杂度小
这里的时间复杂度和空间复杂度都是一个长期期望

问题分析(数据状况不可控)

经典快排和数组是否有序是有关系的,当你每次选择的base不是正中间的数的时候此时划分的左右规模是不相等,当有序的情况下会演变成o(n^2)
代码:swap(arr, parseInt(Math.random() * (R - L + 1)) + L, R)

数据状况不可控的解决方案(绕过原始的数据状况):

通过随机的方式打乱数据状况:比如在快排中通过随机选择一个值作为base,就和原始的数据状况没有关系了
数据状况通过哈希函数打乱

快排相关知识

快排是原地排序算法(不需要额外的空间)
快排不稳定(相同的元素可能会调换位置)

代码

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
//数组划分排序
function partition(arr, L, R) {
  var less = L - 1;
  var more = R + 1;
  var cur = L;
  var num = arr[R]
  while (cur < more) {
    if (arr[cur] < num) {
      swap(arr, ++less, cur++)
    } else if (arr[cur] > num) {
      // 注意这里cur不能移动,还要和左边的比较当前值
      swap(arr, --more, cur)
    } else {
      cur++
    }
  }
  //返回的是等于num的子数组的下标志起始位置和终止位置
  return [less + 1, more - 1]
}
//快排递归
function quickSort(arr, L, R) {
  // L<R的时候才有有排序
  if (L < R) {
    //base的选择优化,随机的选择arr中的下标和最后一个位置交换
    swap(arr, parseInt(Math.random() * (R - L + 1)) + L, R)
    //注意这里快排通过最后一个元素作为base=num
    const curRange = partition(arr, L, R);
    //相等值的下届开始
    quickSort(arr, L, curRange[0] - 1);
    // 相等值的上届开始
    quickSort(arr, curRange[1] + 1, R)
  }
}

const arr = [4, 3, 5, 6, 2, 7, 3]
quickSort(arr, 0, arr.length - 1)
console.log(arr);

2.2 非递归实现

3.快排和归并的比较

相同点

快排和归并用的都是分治思想，递推公式和递归代码也非常相似

不同点

归并排序的处理过程是由下而上的，先处理子问题，然后再合并。

而快排正好相反，它的处理过程是由上而下的，先分区，然后再处理子问题。

归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。

归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。

快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

堆

1.1 堆知识点

堆:将数组看成是一个完全二叉树,堆分为大顶堆和小顶堆.

父子元素之间的关系

父元素:(i-1)/2

左孩子:2i+1<n

右还在:2i-1<n,

这里的i是数组的下标值,当他们小于最后数组的长度表示子节点存在没有越界
堆结构非常重要
- 堆结构的插入heapInsert和调整heapify
- 堆结构的增大和减小
- 建立堆的过程,时间复杂度为O(N)
- 优先级队列结构就是堆结构

1.2 堆排序

思路

通过遍历,边插入边调整堆
交换堆的最大值和最后一个元素,将调整范围-1,调整堆,
每次将最大值放在数组的末尾,直到调整范围变为0,此时数组中所有的元素都有序

复杂度

时间:O(nlogn)
空间:O(1)
不稳定

注意

堆在调整的过程中的时间复杂度就是logN,在不断的调整二叉树结构;插入N
通过堆就可以实现一个优先级队列,面试中都是这么实现的

示意图

代码

//数组交换
function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp
}
//大顶堆调整过程
function heapify(arr, index, heapsize) {
  //求其做孩子
  var left = 2 * index + 1;
  //循环的前提是不越界
  while (left < heapsize) {
    //判断孩子节点中最大值的索引(当左孩子存在并且做孩子大于有孩子时,最大索引是左孩子的索引,不存在或者小于右孩子,较大值的是右孩子)
    var largest = (left + 1) < heapsize && arr[left + 1] > arr[left] ? left + 1 : left;
    //比较孩子最大值和父节点的大小,将较大的值赋值largest
    largest = arr[index] > arr[largest] ? index : largest;
    //判断最大值是不是父节点,是则直接返回,不用调整
    if (largest == index) {
      break
    }
    //调整的前提是index和最大值不相等
    swap(arr, index, largest);
    //将当前最大值赋值给index,继续往下比较
    inde = largest;
    left = index * 2 + 1;
  }
}

//插入堆
function heapInsert(arr, index) {
  //判断和父节点的大小,大于父节点,交换,依次递归
  var parent = Math.floor((index - 1) / 2)
  while (arr[index] > arr[parent]) {
    swap(arr, index, parent);
    index = parent;
    parent = Math.floor((index - 1) / 2)
  }
}
// 堆排序
/*
思想:先将数组中的所有值依次插入调整成大顶堆,每次从大顶堆中的最后一个元素和根元素最大值交换位置,调整的范围--,重新调整交换之后的堆,每次调整的时间复杂度都是logN,n个元素依次调整时间复杂度NlogN
*/
function heapSort(arr) {
  if (arr == null || arr.length < 2) {
    return
  }
  //for循环依次调整arr为大顶堆
  for (var i = 0; i < arr.length; i++) {
    heapInsert(arr, i)
  }
  //插入之后依次交换堆顶和末尾元素,调整堆,调整范围heapsize-1,这样数组末尾的元素就是已经排序好的
  var heapsize = arr.length;
  swap(arr, 0, --heapsize);
  while (heapsize > 0) {
    heapify(arr, 0, heapsize);
    //继续交换
    swap(arr, 0, --heapsize)
  }
}

var arr = [
  89, -80, 47, -9,
  -10, -48, 27
]
heapSort(arr)
console.log(arr);

其他排序

1.1 其他排序

1.2 排序对比

本文作者： SparkParis
本文链接： https://sparkparis.github.io/2020/06/20/%E7%AE%97%E6%B3%952/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！