「算法之美系列」排序(JS版)

前言 最近一段时间重(入)拾(门)算法,算法渣渣的我只有做笔记换来一丝丝心里安慰,在这里也记录分享一下,后面将会归纳成一系列吧。比如「递归与回溯」、「深度与广度优先」、「动态规划」、「二分搜索」和「贪婪」等。
冒泡排序(Bubble Sort) 冒泡排序基本思想
给定一个数组,我们把数组里的元素通通倒入到水池中,这些元素将通过相互之间的比较,按照大小顺序一个一个地像气泡一样浮出水面。
冒泡排序实现
每一轮,从杂乱无章的数组头部开始,每两个元素比较大小并进行交换,直到这一轮当中最大或最小的元素被放置在数组的尾部,然后不断地重复这个过程,直到所有元素都排好位置。其中,核心操作就是元素相互比较。
冒泡排序例题分析
给定数组 [2, 1, 7, 9, 5, 8],要求按照从左到右、从小到大的顺序进行排序。
冒泡排序解题思路
从左到右依次冒泡,把较大的数往右边挪动即可。
「算法之美系列」排序(JS版)
文章图片

  • 首先指针指向第一个数,比较第一个数和第二个数的大小,由于 21 大,所以两两交换,[1, 2, 7, 9, 5, 8]
  • 接下来指针往前移动一步,比较 27,由于 27 小,两者保持不动,[1, 2, 7, 9, 5, 8]。到目前为止,7 是最大的那个数。
  • 指针继续往前移动,比较 79,由于 79 小,两者保持不动,[1, 2, 7, 9, 5, 8]。现在,9 变成了最大的那个数。
  • 再往后,比较 95,很明显,95 大,交换它们的位置,[1, 2, 7, 5, 9, 8]
  • 最后,比较 9898 大,交换它们的位置,[1, 2, 7, 5, 8, 9]。经过第一轮的两两比较,9 这个最大的数就像冒泡一样冒到了数组的最后面。
  • 接下来进行第二轮的比较,把指针重新指向第一个元素,重复上面的操作,最后,数组变成了:[1, 2, 5, 7, 8, 9]
  • 在进行新一轮的比较中,判断一下在上一轮比较的过程中有没有发生两两交换,如果一次交换都没有发生,就证明其实数组已经排好序了。
冒泡排序代码示例
// 冒泡排序算法 const bubbleSort = function (arr) { const len = arr.length // 标记每一轮是否发生来交换 let hasChange = true// 如果没有发生交换则已经是排好序的,直接跳出外层遍历 for (let i = 0; i < len && hasChange; i++) { hasChange = false for (let j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) { let temp = arr[j] arr[j] = arr[j + 1] arr[j + 1] = temp hasChange = true } } } }const arr = [2, 1, 7, 9, 5, 8] bubbleSort(arr) console.log('arr: ', arr)

冒泡排序算法分析
冒泡排序空间复杂度 假设数组的元素个数是 n,由于在整个排序的过程中,我们是直接在给定的数组里面进行元素的两两交换,所以空间复杂度是 O(1)
冒泡排序时间复杂度 给定的数组按照顺序已经排好
  • 在这种情况下,我们只需要进行 n?1 次的比较,两两交换次数为 0,时间复杂度是 O(n)。这是最好的情况。
  • 给定的数组按照逆序排列。在这种情况下,我们需要进行 n(n-1)/2 次比较,时间复杂度是 O(n2)。这是最坏的情况。
  • 给定的数组杂乱无章。在这种情况下,平均时间复杂度是 O(n2)
由此可见,冒泡排序的时间复杂度是 O(n2)。它是一种稳定的排序算法。(稳定是指如果数组里两个相等的数,那么排序前后这两个相等的数的相对位置保持不变。)
插入排序(Insertion Sort) 插入排序基本思想
不断地将尚未排好序的数插入到已经排好序的部分。
插入排序特点
在冒泡排序中,经过每一轮的排序处理后,数组后端的数是排好序的;而对于插入排序来说,经过每一轮的排序处理后,数组前端的数都是排好序的。
插入排序例题分析
对数组 [2, 1, 7, 9, 5, 8] 进行插入排序。
插入排序解题思路
  • 首先将数组分成左右两个部分,左边是已经排好序的部分,右边是还没有排好序的部分,刚开始,左边已排好序的部分只有第一个元素 2。接下来,我们对右边的元素一个一个进行处理,将它们放到左边。
「算法之美系列」排序(JS版)
文章图片

  • 先来看 1,由于 12 小,需要将 1 插入到 2 的前面,做法很简单,两两交换位置即可,[1, 2, 7, 9, 5, 8]
  • 然后,我们要把 7 插入到左边的部分,由于 7 已经比 2 大了,表明它是目前最大的元素,保持位置不变,[1, 2, 7, 9, 5, 8]
  • 同理,9 也不需要做位置变动,[1, 2, 7, 9, 5, 8]。
  • 接下来,如何把 5 插入到合适的位置。首先比较 59,由于 59 小,两两交换,[1, 2, 7, 5, 9, 8],继续,由于 57 小,两两交换,[1, 2, 5, 7, 9, 8],最后,由于 52 大,此轮结束。
  • 最后一个数是 8,由于 89 小,两两交换,[1, 2, 5, 7, 8, 9],再比较 78,发现 87 大,此轮结束。到此,插入排序完毕。
插入排序代码示例
// 插入排序 const insertionSort = function (arr) { const len = arr.length for (let i = 1; i < len; i++) { let current = arr[i] for (let j = i - 1; j >= 0; j--) { // current 小于 j 指向的左侧值,将 j 指向左侧值右移一位 if (current < arr[j]) { arr[j + 1] = arr[j] } else { // 否则将 current 插入到 j 位置,跳出内循环 arr[j] = current break } } } }const arr = [2, 1, 7, 9, 5, 8] insertionSort(arr) console.log('arr: ', arr)

插入排序算法分析
插入排序空间复杂度 【「算法之美系列」排序(JS版)】假设数组的元素个数是 n,由于在整个排序的过程中,是直接在给定的数组里面进行元素的两两交换,空间复杂度是 O(1)
插入排序时间复杂度
  • 给定的数组按照顺序已经排好。只需要进行 n-1 次的比较,两两交换次数为 0,时间复杂度是 O(n)。这是最好的情况。
  • 给定的数组按照逆序排列。在这种情况下,我们需要进行 n(n-1)/2 次比较,时间复杂度是 O(n2)。这是最坏的情况。
  • 给定的数组杂乱无章。在这种情况下,平均时间复杂度是 O(n2)
由此可见,和冒泡排序一样,插入排序的时间复杂度是 O(n2),并且它也是一种稳定的排序算法。
归并排序(Merge Sort) 归并排序基本思想
核心是分治,就是把一个复杂的问题分成两个或多个相同或相似的子问题,然后把子问题分成更小的子问题,直到子问题可以简单的直接求解,最原问题的解就是子问题解的合并。归并排序将分治的思想体现得淋漓尽致。
归并排序实现
一开始先把数组从中间划分成两个子数组,一直递归地把子数组划分成更小的子数组,直到子数组里面只有一个元素,才开始排序。
排序的方法就是按照大小顺序合并两个元素,接着依次按照递归的返回顺序,不断地合并排好序的子数组,直到最后把整个数组的顺序排好。
归并排序代码示例
// 归并排序 const mergeSort = function (arr, lo, hi) { if (lo === undefined) { lo = 0 } if (hi === undefined) { hi = arr.length - 1 }// 判断是否剩下最后一个元素 if (lo >= hi) return// 从中间将数组分成两部分 let mid = lo + Math.floor((hi - lo) / 2) console.log('mid', mid)// 分别递归将左右两边排好序 mergeSort(arr, lo, mid) mergeSort(arr, mid + 1, hi)// 将排好序的左右两半合并 merge(arr, lo, mid, hi) }const merge = function (arr, lo, mid, hi) { // 复制一份原来的数组 const copy = [...arr]// 定义一个 k 指针表示从什么位置开始修改原来的数组, // i 指针表示左边半的起始位置 // j 指针便是右半边的其实位置 let k = lo let i = lo let j = mid + 1while (k <= hi) { if (i > mid) { arr[k++] = copy[j++] } else if (j > hi) { arr[k++] = copy[i++] } else if (copy[j] < copy[i]) { arr[k++] = copy[j++] } else { arr[k++] = copy[i++] } } } const arr = [2, 1, 7, 9, 5, 8] mergeSort(arr) console.log('arr: ', arr)

其中,While 语句比较,一共可能会出现四种情况。
  • 左半边的数都处理完毕,只剩下右半边的数,只需要将右半边的数逐个拷贝过去。
  • 右半边的数都处理完毕,只剩下左半边的数,只需要将左半边的数逐个拷贝过去就好。
  • 右边的数小于左边的数,将右边的数拷贝到合适的位置,j 指针往前移动一位。
  • 左边的数小于右边的数,将左边的数拷贝到合适的位置,i 指针往前移动一位。
归并排序例题分析
利用归并排序算法对数组 [2, 1, 7, 9, 5, 8] 进行排序。
归并排序解题思路
「算法之美系列」排序(JS版)
文章图片

首先不断地对数组进行切分,直到各个子数组里只包含一个元素。
接下来递归地按照大小顺序合并切分开的子数组,递归的顺序和二叉树里的前向遍历类似。
  • 合并 [2][1][1, 2]
  • 子数组 [1, 2][7] 合并。
  • 右边,合并 [9][5]
  • 然后合并 [5, 9][8]
  • 最后合并 [1, 2, 7][5, 8, 9][1, 2, 5, 8, 9],就可以把整个数组排好序了。
合并数组 [1, 2, 7][5, 8, 9] 的操作步骤如下。
「算法之美系列」排序(JS版)
文章图片

  • 把数组 [1, 2, 7]L 表示,[5, 8, 9]R 表示。
  • 合并的时候,开辟分配一个新数组 T 保存结果,数组大小应该是两个子数组长度的总和
  • 然后下标 ijk 分别指向每个数组的起始点。
  • 接下来,比较下标 i 和 j 所指向的元素 L[i]R[j],按照大小顺序放入到下标 k 指向的地方,1 小于 5
  • 移动 ik,继续比较 L[i]R[j]25 小。
  • ik 继续往前移动,57 小。
  • 移动 jk,继续比较 L[i] 和 R[j],78 小。
  • 这时候,左边的数组已经处理完毕,直接将右边数组剩余的元素放到结果数组里就好。
合并之所以能成功,先决条件必须是两个子数组都已经分别排好序了。
归并排序算法分析
归并排序空间复杂度 由于合并 n 个元素需要分配一个大小为 n 的额外数组,合并完成之后,这个数组的空间就会被释放,所以算法的空间复杂度就是 O(n)。归并排序也是稳定的排序算法。
归并排序时间复杂度 归并算法是一个不断递归的过程。
举例:数组的元素个数是 n,时间复杂度是 T(n) 的函数。
解法:把这个规模为 n 的问题分成两个规模分别为 n/2 的子问题,每个子问题的时间复杂度就是 T(n/2),那么两个子问题的复杂度就是 2×T(n/2)。当两个子问题都得到了解决,即两个子数组都排好了序,需要将它们合并,一共有 n 个元素,每次都要进行最多 n-1 次的比较,所以合并的复杂度是 O(n)。由此我们得到了递归复杂度公式:T(n) = 2×T(n/2) + O(n)
对于公式求解,不断地把一个规模为 n 的问题分解成规模为 n/2 的问题,一直分解到规模大小为 1。如果 n 等于 2,只需要分一次;如果 n 等于 4,需要分 2 次。这里的次数是按照规模大小的变化分类的。
以此类推,对于规模为 n 的问题,一共要进行 log(n) 层的大小切分。在每一层里,我们都要进行合并,所涉及到的元素其实就是数组里的所有元素,因此,每一层的合并复杂度都是 O(n),所以整体的复杂度就是O(nlogn)
快速排序(Quick Sort) 快速排序基本思想
快速排序也采用了分治的思想。
快速排序实现
把原始的数组筛选成较小和较大的两个子数组,然后递归地排序两个子数组。
举例:把班级里的所有同学按照高矮顺序排成一排。
解法:老师先随机地挑选了同学 A,让所有其他同学和同学 A 比高矮,比 A 矮的都站在 A 的左边,比 A 高的都站在 A 的右边。接下来,老师分别从左边到右边的同学里选择了同学 B 和同学 C,然后不断的筛选和排列下去。
在分成较小和较大的两个子数组过程中,如何选定一个基准值(也就是同学 A、B、C 等)尤为关键。
快速排序实现例题分析
对数组[2,1,7,9,5,8]进行排序。
快速排序解题思路
「算法之美系列」排序(JS版)
文章图片

  • 按照快速排序的思想,首先把数组筛选成较小和较大的两个子数组。
  • 随机从数组里选取一个数作为基准值,比如 7,于是原始的数组就被分成里两个子数组。注意:快速排序是直接在原始数组里进行各种交换操作,所以当子数组被分割出去的时候,原始数组里的排列也被改变了。
  • 接下来,在较小的子数组里选 2 作为基准值,在较大的子数组里选 8 作为基准值,继续分割子数组。
  • 继续将元素个数大于 1 的子数组进行划分,当所有子数组里的元素个数都为 1 的时候,原始数组也被排好序了。
快速排序代码示例
// 快速排序 const quickSort = function (arr, lo, hi) { if (lo === undefined) { lo = 0 } if (hi === undefined) { hi = arr.length - 1 }// 判断是否只剩下一个元素,是,则直接返回 if (lo >= hi) return// 利用 partition 函数找到一个随机的基准点 const p = partition(arr, lo, hi)// 递归对基准点左半边和右半边的数进行排序 quickSort(arr, lo, p - 1) quickSort(arr, p + 1, hi) }// 交换数组位置 const swap = function (arr, i, j) { let temp = arr[i] arr[i] = arr[j] arr[j] = temp }// 随机获取位置索引 const randomPos = function (lo, hi) { return lo + Math.floor(Math.random() * (hi - lo)) }const partition = function (arr, lo, hi) { const pos = randomPos(lo, hi) console.log('pos: ', pos) swap(arr, pos, hi)let i = lo let j = lo// 从左到右用每个数和基准值比较,若比基准值小,则放在指针 i 指向的位置 // 循环完毕后,i 指针之前的数都比基准值小 while (j < hi) { if (arr[j] <= arr[hi]) { swap(arr, i++, j) } j++ } // 末尾的基准值放置到指针 i 的位置, i 指针之后的数都比基准值大 swap(arr, i, j)// 返回指针 i,作为基准点的位置 return i }const arr = [2, 1, 7, 9, 5, 8] quickSort(arr) console.log(arr)

快速排序算法分析
快速排序时间复杂度 1、最优情况:被选出来的基准值都是当前子数组的中间数。
这样的分割,能保证对于一个规模大小为 n 的问题,能被均匀分解成两个规模大小为 n/2 子问题(归并排序也采用了相同的划分方法),时间复杂度就是: T(n)=2xT(n/2) + O(n)
把规模大小为 n 的问题分解成 n/2 的两个子问题时,和基准值进行了 n-1 次比较,复杂度就是 O(n)。很显然,在最优情况下,快速排序的复杂度也是 O(nlogn)
2、最坏情况:基准值选择了子数组里的最大后者最小值。
每次都把子数组分成了两个更小的子数组,其中一个的长度为 1,另外一个的长度只比原子数组少 1
举例:对于数组来说,每次挑选的基准值分别是 9、8、7、5、2
解法:划分过程和冒泡排序的过程类似。
算法复杂度为 O(n^2)
提示:可以通过随机地选取基准值来避免出现最坏的情况。
快速排序空间复杂度 和归并排序不同,快速排序在每次递归的过程中,只需要开辟 O(1) 的存储空间来完成交换操作实现直接对数组的修改,又因为递归次数为 logn,所以它的整体空间复杂度完全取决于压堆栈的次数,因此,它的空间复杂度是 O(logn)

    推荐阅读