算法

冒泡算法

冒泡排序是一种简单直接暴力的排序算法,因为每一轮比较可能多个元素移动位置,而元素位置的互换是需要消耗资源的,所以这是一种偏慢的排序算法,仅适用于对于含有较少元素的数列进行排序。

  • 稳定性:我们从代码中可以看出只有前一个元素大于后一个元素才可能交换位置,所以相同元素的相对顺序不可能改变,所以它是稳定排序

  • 比较性:因为排序时元素之间需要比较,所以是比较排序

  • 时间复杂度:因为它需要双层循环n*(n-1)),所以平均时间复杂度为O(n^2)

  • 空间复杂度:只需要常数个辅助单元,所以空间复杂度为O(1),我们把空间复杂度为O(1)的排序成为原地排序(in-place)

  • 记忆方法:想象成气泡,一层一层的往上变大

选择排序

设第一个元素为比较元素,依次和后面的元素比较,比较完所有元素找到最小的元素,将它和第一个元素互换

重复上述操作,我们找出第二小的元素和第二个位置的元素互换,以此类推找出剩余最小元素将它换到前面,即完成排序

插入排序

插入排序比冒泡排序和选择排序既快又简单。举个例子,在玩纸牌游戏时会整理自己的牌!在每个循环迭代中,插入排序从数组中删除一个元素。然后,它在另一个排序数组中找到该元素所属的位置,并将其插入其中。它重复这个过程,直到没有输入元素。 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法

归并排序

归并排序是分而治之算法的完美例子。它简单地使用了这种算法的两个主要步骤:
(1)连续划分未排序列表,直到有N个子列表,其中每个子列表有1个“未排序”元素,N是原始数组中的元素数。
(2)重复合并,即一次将两个子列表合并在一起,生成新的排序子列表,直到所有元素完全合并到一个排序数组中。

快速排序

首先要打乱序列顺序 ,以防算法陷入最坏时间复杂度。快速排序使用“分而治之”的方法。 对于一串序列,首先从中选取一个数,凡是小于这个数的值就被放在左边一摞,凡是大于这个数的值就被放在右边一摞。然后,继续对左右两摞进行快速排序。 直到进行快速排序的序列长度小于 2 (即序列中只有一个值或者空值)

comments powered by Disqus