数据结构：排序趟数 / 比较次数与序列的原始状态有关的排序方法有哪些？「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

先说结论

比较次数 与序列初态 无关 的算法是：二路归并排序、简单选择排序、基数排序 比较次数 与序列初态 有关 的算法是：快速排序、直接插入排序、冒泡排序、堆排序、希尔排序

排序趟数 与序列初态 无关 的算法是：直接插入排序、折半插入排序、希尔排序、简单选择排序、归并排序、基数排序 排序趟数 与序列初态 有关 的算法是：冒泡排序、快速排序

关于排序趟数

插入排序、选择排序 趟数都是固定的 n-1。对于插入排序来说，即使序列有序，也要依次从第二个元素开始，向前找它的插入位置。

冒泡排序 趟数与数据有关，优化冒泡排序的最优复杂度为O(n)，其主要优化就是记录了前一趟是否冒泡，如果没有产生冒泡就说明数组已经有序，直接return。如果产生了冒泡，才继续执行。

快速排序 的排序趟数就是它的递归深度。当 快排 的数据是有序时候，会退化为冒泡，所以快排趟数也与初始序列顺序有关了。如下图：

在这里插入图片描述

关于比较次数

有同学在评论中提出了疑问，我在这里补充一下吧，关于对于比较次数和初始状态的关系的理解 堆排序：比如元素下沉的操作，虽然一个元素是从底部拉上来的，但这不代表这个元素一定会接着沉到底部，如果沉到中间就停止下沉的话，比较次数就少了。而这个过程的比较次数自然和下沉的深度是相关的。 希尔排序：希尔排序是对简单插入排序的改进，每一趟希尔的内部使用的就是简单插入排序。而简单插入排序随着数据变成正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。当数据是反序时，执行效率最差，此时时间复杂度为O(N*N). 类比到希尔排序中，希尔排序本身就是属于插入排序。当然会随着有序而少比较几次。 (这里说的比较次数是精确的次数，区别于时间复杂度的概念，时间复杂度只是描述了数量级)

选择排序

i 从头开始，每次遍历之后所有的元素，k 从 i 开始，向后标记 选出 最小的元素，循环后如果大于 i ，则与 i 位置元素 交换，一直到最后。 简单选择排序它最大的特点是，交换移动数据次数相当少，这样也就节约了相应的时间，无论最好最坏的情况，其比较次数都是一样多。第 i 次排序需要进行n-i 次关键字的比较，此时需要比较n-1+n-2+…+1=n(n-1)/2次，所以 总比较次数 与初始状态 无关，时间复杂度为O（n^2)。

对于交换次数而言，最差的时候，也就初始排序，交换次数为n-1次,复杂度为O（n)。当全部已经排序好时，则不发生交换，所以 元素总移动次数 与初始状态 有关。

直接插入排序

从当前关键字之前的关键字开始扫描，如果大于待排关键字，则后移一位。直到全部记录插入完成。

如果全部有序，则只需要遍历一趟就完成了排序，比较次数为 n-1，并且在这个过程中没有发生元素的移动。因此，比较次数 与序列初态 有关 。初始序列基本有序时，移动元素最少（效率最高）。

在这里插入图片描述

void insertSort(int A[],int n)
{ 
   
        int i, j, temp;
        for (i = 1; i < n; i++) { 
    // 将各元素插入已经排好的序列中
            if (A[i] < A[i - 1]) { 
    // 若A[i]关键字小于前驱
                temp = A[i]; // 用 temp 暂存 A[i]
                for (j = i - 1; j >= 0 && A[j] > temp; --j) // 检查所有前面已经排好序的元素
                    A[j + 1] = A[j]; // 将所有大于 temp 的元素右移一个位置
                A[j + 1] = temp; // 复制到插入位置
            }
        }
}

若使用 折半插入 来进行优化，虽然减少了元素的比较次数，但并未使时间复杂度脱离O(n^2)

关于算法复杂度与序列初态的关系

算法复杂度 与初始状态 无关 的有哪些？

首先看内排序总结表：

在这里插入图片描述

由表中红线标出的地方可以轻易得出，以下四种排序方法的算法复杂度与数组的初始状态无关：

一堆（堆排序）乌龟（归并排序）选（选择排序）基（基数排序）友。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/172511.html原文链接：https://javaforall.cn