冒泡排序
冒泡排序比较任何两个相邻的项,如果第一个比第二个大,则交换它们。元素项向上移动至确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。
1 | var bubbleSort = function (array) { |
它在所有排序算法中最简单。然而,
从运行时间的角度来看,冒泡排序是最差的一个,
1 | var bubbleSort = function (array) { |
如果用大小为 10 的数组执行 bubbleSort,开销是 100,所以复杂度是 O(n^2)
注意当算法执行外循环的第二轮的时候,数字 4 和 5 已经是正确排序的了。在后续
比较中,它们还一直在进行着比较,即使这是不必要的。因此,我们可以稍稍改进一下冒泡排序
算法。
1 | var bubbleSort = function (array) { |
大小为 5 的数组开销为 15 复杂度是 O(n^2-(1+2+..+n))
选择排序
选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并
将其放置在第一位,接着找到第二小的值并将其放在第二位,以此类推。
1 | var swap = function (array, index1, index2) { |
选择排序同样也是一个复杂度为 O(n2)的算法。和冒泡排序一样,它包含有嵌套的两个循环,
这导致了二次方的复杂度。
插入排序
插入排序每次排一个数组项,以此方式构建最后的排序数组。假定第一项已经排序了,接着,
它和第二项进行比较,第二项是应该待在原位还是插到第一项之前呢?
如果是之前,那么第一项应该向后移动一个位置,如果是之后,那么不用动。
这样,头两项就已正确排序,接着和第三项比较,以此类推。
1 | var insertionSort = function (array) { |
复杂度为 O(n-1+(2+3+..n-1))
排序小型数组时,此算法比选择排序和冒泡排序性能要好。
归并排序
归并排序是一种分治算法。其思想是将原始数组切分成较小的数组,直到每个小数组只有一个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。
因为已经排序好的两个数组 处于数组最左边的总是最小的,而只剩一项的数组是已经排序好的数组,
所以最后的大数组也是排序完毕的
1 | var merge = function (left, right) { |
归并排序是可以被实际使用的排序算法,归并排序性能不错,其复杂度为 O(nlog^n)。
快速排序
先看一下一个平民版的快速排序
1 | var quickSort = function (arr) { |
可以看到快速排序的过程是三步
- 在数据集之中,选择一个元素作为”基准”(pivot)。
- 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。
- 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
上面排序方法的的问题是每次递归都需要开了 2 个临时数组,导致了空间复杂度增大。不过对于快速排序的理解是有帮助的;
1 | var swap = function (arr, i, j) { |
快速排序复杂度为 O(nlogn),且它的性能通常比其他的复杂度为 O(nlogn)的排序算法要好。