测试派 Give testers a home.

常用算法

排序算法

冒泡排序

• 特点：
  • 类似于水中冒泡，较重（大）的物质慢慢沉下去，较轻（小）的物质慢慢冒出来
  • 一般针对线性列表或数组，假设其长度为n，需要经过n-1轮的冒泡；每一轮冒泡挑选一个最大的沉下去
  • 复杂度
    • 时间复杂度：O(n²)
    • 空间复杂度：O(1)
    • 稳定性：稳定
• 排序过程（升序）：
  
• 详细示例见附件中的bubble\BubbleSort.java
• 扩展：泛型排序，见bubble包下的其他示例

插入排序

• 特点：
  • 将待排序数据从左到右分成已排序区和未排序区，初始时，已排序区为左边第1个数据，第2个及以后的所有数据都为未排序区
  • 排序过程中，每次取未排序区的第1个数据，与左侧已排序区的数据从右向左一一比较，找到在已排序区的合适的位置，完成这个数据排序
  • 如此，对于n个数据的排序，通过每2~n个数据都做一次合适的插入排序后，整个数据集合就变成有序集合
  • 复杂度
    • 时间复杂度：O(n²)
    • 空间复杂度：O(1)
    • 稳定性：稳定
• 排序过程（升序）：
  
• 详细示例见附件中的insertion\InsertionSort.java