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

常用算法

排序算法

堆排序

• 特点：

  • 堆是一颗逻辑上的完全二叉树，其存储物理结构为顺序结构

  • 堆排序是利用堆这种数据结构设计的一种排序算法，是一种选择排序

  • 大根堆：堆中每个节点的值都大于或等于其左节点、右子节点的值，一般用于升序排序中

  • 小根堆：堆中每个节点的值都小于或等于其左节点、右子节点的值，一般用于降序排序中

  

  • 在做堆排序时，通过持续将无序数据构建成大根堆（小根堆），然后将最大值（最小值）与最后一个位置的元素交换；再将堆的节点数减小1个节点，重建成大根堆（小根堆）；最后堆的节点数为1时，整个物理结构的数据即为升序（降序）

  • 复杂度

    • 时间复杂度：O(nlogn)

    • 空间复杂度：O(1)

    • 稳定性：不稳定

• 排序过程（升序）：

• 详细示例见附件中merge\MergeSort.java

快速排序

• 特点：

  • 需要取一个基准值，记为pivot

  • 将数据(记为数组data，起始下标记为start、end)，然后分别按下标从右往左、从左往右与基准值进行循环比较

  • 复杂度

    • 时间复杂度：O(logn)

    • 空间复杂度：O(logn)

    • 稳定性：不稳定

• 逻辑：

  1. 比较开始时，记录初始下标值left=start、right=end，取基准值为最左值pivot=data[left]

  2. 【循环】条件是left<right，将基准值(pivot)放置到合理位置，最后让基准值左侧都小于基准值，右侧都大于基准值

     • 【子循环】从右往左循环比较，找出第1个小于基准值的数据

       • 如果当前下标位置的值大于基准值(data[right]>pivot)，下标位置左移1位(right--)，进行下轮循环

       • 如果当前下标位置的值小于等于基准值(data[right]<=pivot)，结束循环

       • 将最左下标值替换为退出循环的小于等于基准值的数据data[left]=data[right]

     • 【子循环】从左往右循环比较，找出第1个大于基准值的数据

       • 如果当前下标位置的值小于基准值(data[left]<pivot)，下标位置右移1位(left++)，进行下轮循环

       • 如果当前下标 位置的值大于等于基准值(data[left]>=pivot)，结束循环

       • 将最右下标值替换为退出循环的大于等于基准值的数据data[right]=data[left]

  3. 【递归】在上述循环后结束后，将基准值放到left==right的位置 ，然后对小于基准值的数据和大于基准值的数据再进行上述1-3个步骤的逻辑

• 排序过程（升序）：

• 详细示例见附件中quick\QuickSort.java