文章目录前言一、选择排序二、堆排序1.什么是堆排序2.代码的实现过程总结前言我们前面探讨了插入排序和希尔排序今天我们来一起探讨一下选择排序和堆排序。一、选择排序选择排序顾名思义就是在[begin,end]区间中选择最大值和最小值将最大值放到右边最小值放到左边不断重复以上操作通过缩小区间从而达到排序的目的。代码理解通过第一个while循环确定了begin和end的范围在[begin,end]这个范围中找最大值最小值找到之后将最小值与begin交换最大值与end交换。特殊处理时间复杂度分析无论是数据是有序还是无序时间复杂度都是O(N^2)稳定性不稳定空间复杂度O(1)二、堆排序1.什么是堆排序说到堆我们很快想起在数据结构中学到的堆结构但真正的堆排序是利用堆的思想不是堆数据结构那给定一个乱序数组怎么用堆的思想将其有序。1首先将乱序数据变成堆结构升序建大堆降序建小堆为什么这样建呢后面会有解释2将堆顶元素和堆底元素交换利用向上/向下调整算法将交换后的数组变成堆结构这样一来大的/小的元素将放在数组的后面不断重复以上过程这样就完成了排序。2.代码的实现过程向上调整建堆时间复杂度为n*logn证明过程空间复杂度O1稳定性不稳定因为每次都要交换堆顶和堆底时间复杂度分析代码理解从最后一个非叶子节点向前遍历对每个节点执行向下调整此时该节点的左右子树都已经是合法堆。时间复杂度向下调整算法建堆时间复杂度为O(n)证明过程我们可以看出向上调整算法建堆时间复杂度大于向下调整算法建堆所以在实际中常用向下调整算法建堆总结选择排序法选择最大值和最小值最小值放在前面最大值放在后面无论数组有没有序时间复杂度都为O(N^2)堆排序用向上调整算法建堆/向下调整算法建堆再取堆顶和堆底元素交换。向上调整算法建堆时间复杂度O(n*logn),向下调整算法建堆时间复杂度O(N)