当前位置：首页 > news >正文

查缺补漏----内部排序算法排序趟数和比较次数

news 2024/11/8 8:15:44

排序趟数：

插入排序（分为直接插入排序和折半插入排序）：每趟确定一个元素，排序趟数固定为n-1，和序列初始状态无关。

希尔排序：希尔排序的趟数取决于所选的d（增量序列）。不同的增量序列会导致不同的排序趟数。

冒泡排序：冒泡排序的趟数是1~n-1，和初始序列有关。
快速排序算法：排序的趟数为 $\left \lfloor log_2n \right \rfloor+1$ ~n（递归深度），具体取决于序列的原始状态（还取决于划分方法，例如枢轴元素的位置）

对于 $\left \lfloor log_2n \right \rfloor+1$ 的情况，枢轴每次都等分子表：

对于n的情况，递归树退化为单链表：

简单选择排序：简单选择排序每趟都选出一个最小(或最大)的元素，排序的趟数固定为n-1。与序列的原始状态无关。

堆排序：固定n-1趟排序（总共n-1趟的交换和建堆）。

归并排序:归并的趟数固定为 $\left \lceil log_2n \right \rceil$ 趟。

基数排序：每趟都要进行分配和收集，排序趟数固定为d，和序列初始状态无关。

看下下面两道题：

我并没有看到题目有明显的暗示两者的区别，解析说的是第1题指的是交换趟数，所以不计最后一趟无交换排序，大家自行理解下。

比较次数：

直接插入排序：比较次数与初始序列。在最好情况下，直接插入只需要n-1次比较操作，且不需要交换操作。最坏情况： $\frac{n(n-1)}{2}$ （不带哨兵）。在平均情况和最坏情况下，直接插入的比较和交换操作都需要O(n^2)次比较。
折半插入排序：

折半插入排序每趟的比较次数都为O(log2m)(m为当前已排序好的子序列的长度)，因此总比较次数的确定的。

这里补充一下：折半查找的最多比较次数是 $\left \lfloor log_2n \right \rfloor+1$
希尔排序：希尔排序的比较次数也取决于增量序列。
冒泡排序：比较次数与初始序列有关。冒泡排序最好情况下只需要一趟排序过程就可以完成，只需要n-1次比较操作，不需要交换操作。最坏情况： $\frac{n(n-1)}{2}$ 。
快速排序算法：比较次数与初始序列有关，最多比较次数与最少比较，以8个元素为例：

简单选择排序：总比较次数固定，并且为 $\frac{n(n-1)}{2}$ 。但是移动次数与序列的初始排列有关，最好情况是不移动，最坏情况是n-1次移动，如果算上每次的3条赋值语句：

void swap(int *a, int *b)
{
int temp;；
temp = *a;
*a = *b;
*b = temp;
}

最坏情况应该是3(n-1)次移动次数。

堆排序：比较次数与初始序列有关（例如某元素只有左孩子，只用和左孩子比较（比较1次），若某元素有左，右两个孩子，则比较次数为2。即左，右孩子先比较，再与父结点比较）。

对于插入和删除堆元素：

查缺补漏----堆排序易错点_将关键字依次插入到大根堆和直接构造大根堆做法一样吗-CSDN博客

归并排序：和序列初始状态有关，比较次数不确定。

若两个递增序列进行归并，一个表长为m，一个为n，那么最多比较次数m+n-1，最少则是min{m,n}。

基数排序：不是基于比较的排序算法。