算法和数据结构详细解析排序与堆

Sorting And Heaps

• 选择排序（Selection Sort）

  • 冒泡排序（Bubble Sort）

  • 插入排序（Insertion Sort）

  • 快速排序（Quicksort）

  • 归并排序（Mergesort）

  • 堆结构（Heap）

  • • 上滤操作（Siftup）：
    • 下滤操作（Siftdown）

  • 堆排序算法（Heapsort）

  • • 构建堆过程（Makeheap）

  • 主要排序算法性能对比分析

  • 参考文献

选择排序(Selection Sort)

1. 对数组进行扫描操作，以确定其中的最小数值。
2. 若该最小值未位于x[0]位置，则将其与该位置元素进行交换。（此时x[0]存储的是当前最小值）
3. 对数组中除首个元素外的部分继续扫描，以识别次小的数值。
4. 若次小值未处于x[1]位置，则将其与该位置元素进行交换。（此时x[1]存储的是次小值）
5. 按照此方式依次处理x[2]、x[3]、…、x[n-2]的位置。

选择排序算法在执行过程中始终需要完成n(n-1)/2次比较操作。
即便原始数组已经按照升序排列，这一比较次数仍无法避免。
因此，该算法在效率方面存在明显不足。

冒泡排序(Bubble Sort)