大门|大门-CS-2006 |问题14

以下哪种就地排序算法需要最少的交换次数？ （A） 快速排序 （B） 插入排序 （C） 选择排序 （D） 堆排序 答复: （C） 说明： 让我们尝试分析每个给定排序算法中的交换数量。

快速排序 –最大交换次数的最坏情况输入已按降序排序。

在这种情况下，互换总数的重复性： T（n）=T（n-1）+O（n）//O（n）交换将在对分区算法的交替调用中发生。 =O（n2）

插入排序 –最大交换次数的最坏情况输入已按升序排序。当一个新元素被插入到一个已经排序的k大小数组中时，在最坏的情况下，它可能导致k次交换（如果它是所有交换中最小的）。对于插入排序的n-1次迭代，总交换量为O（n2）。

选择排序 –选择排序没有最坏情况输入。因为它在第k次迭代中搜索第k个最小元素的索引，然后在一次交换中，它将该元素放置到正确的位置。对于选择排序的n-1次迭代，它可以有O（n）次交换。

堆排序 –堆排序中的交换总数可以是O（nlogn），因为在执行可能需要O（n）交换的构建堆之后，它会执行n-1次提取分钟操作，从而生成O（nlogn）交换。

见本报告问题3 https://www.geeksforgeeks.org/data-structures-and-algorithms-set-7/

这个解决方案是由 Pranjul Ahuja 这个问题的小测验