bubbleSort O(n^2) 两层循环嵌套 外层循环控制冒泡最大元素 内存具体操作, 比较, 完成一次内存循环, 冒出一个元素。 具体为比较相邻两个元素
selectionSort 找最小元素, 找到后放在第一位, 然后找第二小, 找到后放在第二位 怎么找:确定第一个数, 叫out, 然后剩下的所有值和out比较, 若小于out, 把值赋给min, out的值赋给找到的元素, swap(min, element) 完成排序,O(n^2), 与冒泡排序相比, 冒泡比较n(n-1)次, 选择也为n(n-1), 但交换次数大大减少。所以算法优于冒泡排序。
insertionSort 顾名思义, 就是插入, 找到第二个元素, 叫做out, 和第一个元素比较, 若小于第一个元素, 插到第一个前面, 由于前面没有元素, 完成操作。 然后, 找到第3个元素, 叫做out, 和第2个元素比较, 若小于第2个元素, 插到第2个前面, 由于前面有元素, 和第1个元素比较, 若小于第1个元素, 插到第1个前面, 由于前面有元素,完成操作。 算法, 优于选择排序, 应为比较和交换的次数大大减少。但还是o(n^2)
quickSort 一种常用的排序叫快排, 因为时间复杂度为nlog(n), 所以很常用, 思想是递归。先找pivot, 然后pivot 把所有的数分成两部分, 再继续找pivot, 在分成两部分, 再继续… 最后竟然神奇的排序完成了, 就没有然后了
mergeSort 一种常用的排序, 因为时间复杂度为nlog(n), 所以很常用, 思想是divide and conquor+递归。先分再合, 所谓分久必合。如果不能再分就开始swap(a, b) 交换相邻两个元素, 或一个, 然后逐步完成所有合并。 需要两个函数, 一个merge, 合并, 一个mergeSort, 完成排序。