3.交换排序

所谓交换,是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

冒泡排序

基本思想

从后往前(或从前往后)两两比较相邻元素的值,若为逆序(即A[i-1]>A[i]),则交换它们,直到序列比较完。我们称它为第一趟冒泡,结果是将最小的元素交换到待排序列的第一个位置(或将最大的元素交换到待排序列的最后一个位置),关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时,前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素〉放到了序列的最终位置......这样最多做$n-1$趟冒泡就能把所有元素排好序

image.png

• 空间效率:$O(1)$
• 时间效率
  • 有序时，比较次数为$n-1$,移动次数为 0,从而最好情况下的时问复杂度为$O(n)$
  • 逆序时，需要进行$n-1$趟排序,第$i$趟排序要进行$n-i$次关键字的比较,而且每次比较后都必须移动元素3次来交换元素位置,此时$\text { 比较次数 }=\displaystyle\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2} \text {, 移动次数 }=\sum_{i=1}^{n-1} 3(n-i)=\frac{3 n(n-1)}{2}$,即最坏情况下复杂度为$O(n^2)$
  • 平均复杂度为$O(n^2)$
• 是稳定排序

快速排序

8.3.2快速排序

---

00:00

【课件】8.3.2快速排序

---

快速排序的基本思想是基于分治法的：在待排序表 $L [1...n]$ 中任取一个元素 pivot 作为枢 轴 (或称基准, 通常取首元素), 通过一趟排序将待排序表划分为独立的两部分 $L[1 \ldots k-1]$ 和 $L[k+1 \ldots n]$, 使得 $L[1 \ldots k-1]$ 中的所有元素小于 pivot, $L[k+1 \ldots n]$ 中的所有元素大于或等于 pivot, 则 pivot 放在了其最终位置 $L(k)$ 上, 这个过程称为一次划分。然后分别递归地对两个子表重复上述过程, 直至每部分内只有一个元素或空为止, 即所有元素放在了其最终位置上。

提示

考研所考查的快速排序的划分操作基本以严蔚敏的教材 《数据结构》为主,假设每次总以当前表中第一个元素作为枢轴来对表进行划分,则将表中比枢轴大的元素向右移动,将比枢轴小的元素向左移动, 使得一趟Partition()操作后,表中的元素被枢轴一分为二

• 空间效率，最好$O(\log_{2} n)$,最坏$O(n)$,平均$O(\log_{2} n)$
• 时间效率，最坏$O(n^2)$,最好$O(n\log_{2}n)$，平均$O(n\log_{2}n)$
• 不稳定

image.png

警告

快速排序是所有内部排序算法中平均性能最优的排序算法。考研涉及的比较多，要求掌握代码