网站的站点的管理系统,推广点击器,网站访客记录,渭南网站制作学校比较分析
排序类别排序算法时间复杂度#xff08;最好#xff09;时间复杂度#xff08;最坏#xff09;时间复杂度#xff08;平均#xff09;辅助空间复杂度稳定性插入排序直接插入排序O(n)O(n)O(n)O(1)稳定插入排序折半插入排序O(n)O(n)O(n)O(1)稳定插入排序希尔排序…比较分析
排序类别排序算法时间复杂度最好时间复杂度最坏时间复杂度平均辅助空间复杂度稳定性插入排序直接插入排序O(n)O(n²)O(n²)O(1)稳定插入排序折半插入排序O(n)O(n²)O(n²)O(1)稳定插入排序希尔排序O(n)O(n²)O(n^1.3)O(1)不稳定交换排序冒泡排序O(n)O(n²)O(n²)O(1)稳定交换排序快速排序O(nlog₂n)O(n²)O(nlog₂n)O(log₂n)不稳定选择排序简单选择排序O(n²)O(n²)O(n²)O(1)不稳定选择排序堆排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(1)不稳定归并排序二路归并排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(n)稳定基数排序基数排序O(d(n k))O(d(n k))O(d(n k))O(n k)稳定
快速排序
步骤
任取一元素作为枢轴pivot图中取的枢轴值为 56。将序列划分成两部分左部分元素值 枢轴右部分元素值 枢轴。然后递归处理左右部分直到子序列为空或只剩一个元素。 图示 pivot 56
索引012345678910值空(56)23457669204593168227leftright
index 0 存放枢轴 56
(1) 若 right 对应的值小于 56 则填到 left 处然后 left此时 right 处有空需要左边的填到右边
(2) 若 right 对应的值大于 56 则不需改变只需要 right--
(3) 若 (1) 成立则看 left后指向的位置是否大于 56若大于 56 则填到 right 处后 right--
若 left后的值小于 56 则不改变位置 left空位仍在右边
(4) 重复上述过程直到划分完毕选择枢轴pivot 56 左部分left pivot右部分right pivot 操作步骤 right 从右往左找比枢轴小的元素去填 left 的坑。left 从左往右找比枢轴大的元素去填 right 的坑。 冒泡排序
步骤
从序列的第一个元素开始依次比较相邻的两个元素。如果前一个元素大于后一个元素则交换它们的位置。对整个序列重复上述比较和交换操作每次遍历都会将当前未排序部分的最大元素 “冒泡” 到末尾。持续进行上述操作直到整个序列有序。
图示 假设初始序列为
索引012345678910值2723457669204593168256
(1) 第一轮比较
比较第 0 个元素和第 1 个元素27 和 23因为 27 23交换位置。序列变为2327457669204593168256比较第 1 个元素和第 2 个元素27 和 45不交换。依次类推比较第 2 个元素和第 3 个元素45 和 76不交换……比较第 9 个元素和第 10 个元素82 和 56因为 82 56交换位置。第一轮结束后最大的元素 93 “冒泡” 到了末尾。 (2) 第二轮比较重复上述比较和交换操作但这次只需要比较到倒数第二个元素因为最大元素已经在末尾了。第二轮结束后第二大的元素 82 “冒泡” 到了倒数第二个位置。 (3) 持续进行上述操作每一轮都会将当前未排序部分的最大元素移动到正确位置。直到整个序列有序。操作步骤总结 每一轮从序列的开头开始依次比较相邻元素如果顺序不对就交换。每一轮过后未排序部分的最大元素就会移动到末尾下一轮比较的范围就减少一个元素。重复这个过程直到整个序列有序。 优化方式 设置一个 bool 类型的swapped 变量每一轮初始化为 false只要在本轮内存在交换操作那么久 swapped true如果某一轮执行完毕后 swapped 仍然为 fasle 说明在此轮中没有交换产生数列已经有序 (这样防止了在排序过程中某轮结束后已经有序但是仍然遍历的情况) 堆排序
堆
是个完全二叉树 (除最下面一层都是满的最下面一层从左到右依次排序没有空的)大根堆 任意节点其左右孩子小根堆 任意节点其左右孩子 一般用顺序存储存放堆 如下所示 上边是逻辑结婚下边是存储结构 下标从 1 开始 index有这个规律 父亲 ⌊ i / 2 ⌋ \lfloor i/2\rfloor ⌊i/2⌋ 左孩子 2 i 2i 2i 右孩子 2 i 1 2i1 2i1
步骤
建堆 从最后一个非叶结点开始依次向下调整 排序 每轮堆顶换到最后向下调整新的堆顶 (n - 1) 轮 手算
快速排序
手算快速排序时 L R 指针左右移动R 指到 pivot 的放到 L 处L 原先为空 放入后 R 为空 L 非空 然后视角切换到 L 若 R 未指到 pivot 的则 R 继续移动L 指到 pivot 的放到 R 处R 原先为空放入后 L 为空 R 非空 然后视角切换到 R 若 L 未指到 pivot 的则 L 继续移动L R 时pivot 归位递归的处理 pivot 左右两边的部分方法同上
堆排序
看到一组乱序关键字时
先按照关键字目前的顺序依次填入一棵完全二叉树 (横着一行一行的填入)然后依次调整树为大根堆/小根堆调整完成之后树的根节点和最后一个关键字 (序号最大的) 调换位置 此时的便是第一轮排序后的结果 (最后一个也就是刚由根节点调换过来的关键字已归位)然后再不包括最后一个关键字的基础上对于前 n-1 个数重新做上述工作直到每个关键字都归位
