数据结构与算法（Java 语言描述）【六】

常用算法

排序算法

冒泡排序

• 特点：

  • 类似于水中冒泡，较重（大）的物质慢慢沉下去，较轻（小）的物质慢慢冒出来

  • 一般针对线性列表或数组，假设其长度为n，需要经过n-1轮的冒泡；每一轮冒泡挑选一个最大的沉下去

  • 复杂度

    • 时间复杂度：O(n²)

    • 空间复杂度：O(1)

    • 稳定性：稳定

• 排序过程（升序）：

• 详细示例见附件中的bubble\BubbleSort.java

• 扩展：泛型排序，见bubble包下的其他示例

插入排序

• 特点：

  • 将待排序数据从左到右分成已排序区和未排序区，初始时，已排序区为左边第1个数据，第2个及以后的所有数据都为未排序区

  • 排序过程中，每次取未排序区的第1个数据，与左侧已排序区的数据从右向左一一比较，找到在已排序区的合适的位置，完成这个数据排序

  • 如此，对于n个数据的排序，通过每2~n个数据都做一次合适的插入排序后，整个数据集合就变成有序集合

  • 复杂度

    • 时间复杂度：O(n²)

    • 空间复杂度：O(1)

    • 稳定性：稳定

• 排序过程（升序）：

• 详细示例见附件中的insertion\InsertionSort.java