大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
先说结论
比较次数 与序列初态 无关 的算法是：二路归并排序、简单选择排序、基数排序
比较次数 与序列初态 有关 的算法是：快速排序、直接插入排序、冒泡排序、堆排序、希尔排序
排序趟数 与序列初态 无关 的算法是：直接插入排序、折半插入排序、希尔排序、简单选择排序、归并排序、基数排序
排序趟数 与序列初态 有关 的算法是：冒泡排序、快速排序
关于排序趟数
插入排序、选择排序 趟数都是固定的 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.net/172511.html原文链接：https://javaforall.net
