6. 交换排序的代价¶
6.1. 交换排序的代价¶
待处理
- type: Revision
按这个思路重写：有两种衡量"失序"程度的指标： 逆序对与最少交换次数。选择排序（尤其是带优化的版本） 能达到最少交换次数，但这一指标一般并不实用。插入排序 追踪逆序对，其代价为 I + n。那么，如果有一种交换排序， 代价会是多少？接着给出证明。
下面总结了插入排序、冒泡排序和选择排序在最好、平均和最坏情况下 所需的比较次数和交换次数。 这些排序在平均和最坏情况下的运行时间都是 \(\Theta(n^2)\) 。
\[\begin{split}\begin{array}{rccc}
&\textbf{Insertion}&\textbf{Bubble}&\textbf{Selection}\\
\textbf{Comparisons:}\\
\textrm{Best Case}&\Theta(n)&\Theta(n^2)&\Theta(n^2)\\
\textrm{Average Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n^2)\\
\textrm{Worst Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n^2)\\
\\
\textbf{Swaps:}\\
\textrm{Best Case}&0&0&\Theta(n)\\
\textrm{Average Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n)\\
\textrm{Worst Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n)\\
\end{array}\end{split}\]
大多数"好的"排序算法在典型条件下的平均情况运行时间都明显优于 这三种排序。 但在研究它们之前，先考察一下这三种排序为何如此慢是很有启发的。 关键的瓶颈在于，只有 相邻 记录会被比较和交换。 这意味着（对插入排序和冒泡排序而言）移动只能一步一步地进行。 交换相邻记录称为 交换 。 因此，这些排序有时被称为 交换排序 。 任何交换排序的代价至多只能是数组中记录必须进行的比较总次数，而 这又与它们离"正确"位置有多远有很大关系。 所需的比较总次数至少是该记录的逆序对个数，所谓 逆序对 ， 是指一条键值大于当前记录键值的记录出现在它之前。
