sort-visualization

排序算法可视化展示，实现了元素比较展示，和交换动画。(算法基于算法 4 中的代码实现)

展示网址

目前实现了

• 简单选择排序
• 插入排序
• 希尔排序
• 快速排序
• 冒泡排序
• 二分法查找
• 堆排序展示网址

算法 4 学习笔记

• 对于算法稳定性的理解

  之前错误的以为，算法的稳定性是指算法在最坏和最优的情况下，时间复杂度和空间复杂度相差不大，或者在大多数情况下，时间复杂度变化不大。

  算法稳定性的定义是：如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是稳定的。 说白了就是键值相同的元素，在排序过程中的顺序是不会发生变化。

  例如大家最熟悉的通讯录假设有四条数据：

   { name: 'zhou', date: '2017-08-07' },
   { name: 'zhou', date: '2017-09-1' },
   { name: 'li', date: '2017-10-1' },
   { name: 'wu', date: '2017-11-1' }
  

  假设现在有这样一个需求： 通讯录按照姓名排序，并且姓名相同的，按照创建时间排序。

  那么此时就体现出了稳定性排序算法的优势：不会改变重复元素之前的顺序。

  此时可以先使用排序算法对上面的记录按照时间进行排序，这次排序可以是稳定的或者不稳定的。关键是第二次排序。

  排序后的记录为：

   { name: 'zhou', date: '2017-08-07' },
   { name: 'zhou', date: '2017-09-1' },
   { name: 'li', date: '2017-10-1' },
   { name: 'wu', date: '2017-11-1' }
  

  现在进行第二次排序，按照姓名首字母进行排序。注意此时稳定性排序算法和非稳定性排序算法就会表现出不一样的结果。

  稳定性排序算法的排序结果肯定是：

   { name: 'li', date: '2017-10-1' },
   { name: 'wu', date: '2017-11-1' }
   { name: 'zhou', date: '2017-08-07' },
   { name: 'zhou', date: '2017-09-1' },
  

  注意此时两条姓名为zhou的记录，依然是按照时间进行排序的

  不稳定的排序算法的会是：

   { name: 'li', date: '2017-10-1' },
   { name: 'wu', date: '2017-11-1' }
   { name: 'zhou', date: '2017-09-01' },
   { name: 'zhou', date: '2017-08-7' },
  

  注意此时两条姓名为zhou的记录，不再是按照时间进行排序的，因为不稳定性排序会改变相同记录的位置

  稳定算法： 插入排序 归并排序

  不稳定排序排序算法：选择排序 希尔排序 快速排序 三向快速排序

• 稳定性算法和不稳定性算法的使用场景：

  1. 对于原始类型来说，稳定性算法和不稳定性算法都可以。
  2. 对于引用类型来说，也就是有排序的键的，最好使用稳定排序算法。

  例如 java 中的 Arrays.sort 在对原始类型进行排序时用的是（三向切分的）快速排序，时间复杂度介于N和NlogN 空间复杂度lgN,在对引用类型排序时，使用的是归并排序,时间复杂度NlogN,空间复杂度N

• javascript 中的 sort 算法底层实现 v8 在元素小于 22 个时候，使用插入排序，其他使用快速排序(所以 v8 的 sort 是不稳定排序)

  Mozilla/Firefox : 归并排序（jsarray.c 源码）

  Webkit ：底层实现用了 C++ 库中的 qsort() 方法（JSArray.cpp 源码）

• 最快的排序算法 快速排序是最快的通用排序算法。(在面试中曾经被问到过，之前竟然回答的是堆排序)

• 对于用快速排序实现查找第 k 个最小元素的实现思路 首先快排的原理是每次排定一个元素，并且排定的元素大于等于左边的元素，小于等于右边的元素， 并且排定的元素位置不再发生变化这是很重要的一点。 那么排定元素的位置就代表了它在当前数组的第几小元素。这样就利用快排实现查找第 k 个最小元素的算法。

  例如：

   2 1 3 4 9 7 8 // 此时元素4已经排定，并且位置不会再发生改变
  

  排序完成之后的数组:

  1 2 3 4 7 9  // 元素4当前所处的位置，就代表了它是第几小元素
  

  所以只需要在返回每次排定位置的时候判断一下是否等于当前的第几最小元素的值

• 快速排序快的原因是它的内循环的指令很少，内循环只有--j和++i这样的指针移动指令

• 排序算法的应用场景(以及对为什么不管大学课本的算法课程还是很多算法书都是把排序最为最开始的章节呢) 要解决的问题， 为什么需要排序，不排序的会怎么样，排序之后有什么好处。

  • 排序算法的应用场景(待补充)

• 各种查找算法的时间复杂度和空间复杂度（查找算法的成本模型是比较次数）

数据结构	最坏情况下查找	最坏情况下插入	平均情况下查找	平均情况下插入
顺序查找	n	n	n2	n
二分查找	lgN	2N	lgN	N
二叉树查找	N	N	1.39lgN	1.39lgN
2-3查找树	2lgN	2lgN	1.001lgN	1.001lgN