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

常用算法

排序算法

希尔排序

• 特点：

  • 是经过改造后的插入排序，相比简单插入排序，有更高的效率，也称为缩小增量排序

  • 排序过程：把一组要排序的数据按照小于数据长度的一定增量(gap)，对要排序的数据进行分组，然后组内数据使用插入排序方法进行排序；随着增量(gap)的逐渐缩小，分组越来越少，最后增量(gap)变为1，此时只有一组，数据变成有序

  • 增量(gap)序列，如一个需要排序数组，长度为n，则增量(gap)序列为{n/2,(n/2)/2,((n/2)/2)/2,...1}

  • 复杂度

    • 时间复杂度：O(n1.3)

    • 空间复杂度：O(1)

    • 稳定性：不稳定

• 逻辑：

  1. 【增量循环】条件增量(gap)从排序数据.length/2作为起始值，每次循环后增量值=原来增量值/2，且条件增量必须大于0

     • 【分组循环】分组循环变量(i)以当前条件增量值(gap)为起始值，每次循环后分组循环变量+1，且分组循环变量必须小于排序数组的长度

       • 【插入排序循环】插入排序变量(j)以[当前分组循环变量(i)-当前条件增量(gap)]作为起始值，每次循环后插入排序变量+gap，且插入排序变量(j)必须大于等于0

         • 在循环中，按照升序或降序对下标为j和j+gap的数据按条件进行交换

  2. 通过上述步骤，就能将排序数据由无序变成有序

• 排序过程（升序）：

• 详细示例见附件中shell\ShellShort.java

选择排序

• 特点：

  • 将待排序数据分成已排序区和未排序区，初始时，已排序区为空，未排序区包含所有待排序数据

  • 排序过程中，每次取未排序区中最大（或最小）的数据，插入到已排序区的末尾

  • 如此，对于n个数据的排序，通过n次从未排序区取到最大（最小）的数据插入到已排序区尾部，整个数据集合就变成有序集合

  • 复杂度

    • 时间复杂度：O(n2)

    • 空间复杂度：O(1)

    • 稳定性：不稳定

• 排序过程（升序）：

• 详细示例见附件中的selection\SelectionSort.java