插入排序是我学的第一个排序 ， 速度还是很快的 ， 特别是在数组已排好了之后 ， 用它的思想来插入一个数据 ， 效率是很高的 。
因为不用全部排 。
他的数据交换也很少 ， 只是数据后移 ， 然后放入要插入的数据 。
（这里不是指调用插入排序 ， 而是用它的思想） 。
我觉得 ， 在数据大部分都排好了 ， 用插入排序会给你带来很大的方便 。
数据的移动和交换都很少 。
4.冒泡排序 ， n*n的时间复杂度 ， 稳定排序 ， 原地排序 。
冒泡排序的思想很不错 ， 一个一个比较 ， 把小的上移 ， 依次确定当前最小元素 。
因为他简单 ， 稳定排序 ， 而且好实现 ， 所以用处也是比较多的 。
还有一点就是加上哨兵之后他可以提前退出 。
5.选择排序 ， n*n的时间复杂度 ，稳定排序 ， 原地排序 。
选 。

19、择排序就是冒泡的基本思想 ， 从小的定位 ， 一个一个选择 ， 直到选择结束 。
他和插入排序是一个相反的过程 ， 插入是确定一个元素的位置 ， 而选择是确定这个位置的元素 。
他的好处就是每次只选择确定的元素 ， 不会对很多数据进行交换 。
所以在数据交换量上应该比冒泡小 。
6.插入排序 ， 选择排序 ， 冒泡排序的比较 ， 他们的时间复杂度都是n*n 。
我觉得他们的效率也是差不多的 ， 我个人喜欢冒泡一些 ， 因为要用它的时候数据多半不多 ， 而且可以提前的返回已经排序好的数组 。
而其他两个排序就算已经排好了 ， 他也要做全部的扫描 。
在数据的交换上 ， 冒泡的确比他们都多 。
举例说明插入一个数据在末尾后排序 ， 冒泡只要一次就能搞定 ， 而选择和插入都必须要n*n的复杂度 。

20、才能搞定 。
7.合并排序：n*log(n)的时间复杂度 ，稳定排序 ， 非原地排序 。
他的思想是分治 ， 先分成小的部分 ， 排好部分之后合并 ， 因为我们另外申请的空间 ， 在合并的时候效率是0(n)的 。
速度很快 。
貌似他的上限是n*log(n) ， 所以如果说是比较的次数的话 ， 他比快速排序要少一些 。
对任意的数组都能有效地在n*log(n)排好序 。
但是因为他是非原地排序 ， 所以虽然他很快 ， 但是貌似他的人气没有快速排序高 。
8.堆排序：n*log(n)的时间复杂度 ，非稳定排序 ， 原地排序 。
他的思想是利用的堆这种数据结构 ， 堆可以看成一个完全二叉树 ， 所以在排序中比较的次数可以做到很少 。
加上他也是原地排序 ， 不需要申请额外的空间 ， 效率 。

21、也不错 。
可是他的思想感觉比快速难掌握一些 。
还有就是在已经排好序的基础上添加一个数据再排序 ， 他的交换次数和比较次数一点都不会减少 。
虽然堆排序在使用的中没有快速排序广泛 ， 但是他的数据结构和思想真的很不错 ， 而且用它来实现优先队列 ， 效率没得说 。
堆 ， 还是要好好学习掌握的 。
9.希尔排序：n*log(n)的时间复杂度(这里是错误的 ， 应该是nlamda(1 lamda 2), lamda和每次步长选择有关 。
) ，非稳定排序 ， 原地排序 。
主要思想是分治 ， 不过他的分治和合并排序的分治不一样 ， 他是按步长来分组的 ， 而不是想合并那样左一半右一半 。
开始步长为整个的长度的一半 。
分成nLen/2个组 ， 然后每组排序 。
接个步长减为 。

22、原来的一半在分组排序 ， 直到步长为1 ， 排序之后希尔排序就完成了 。
这个思路很好 ， 据说是插入排序的升级版 ， 所以在实现每组排序的时候我故意用了插入排序 。
我觉得他是一个特别好的排序方法了 。
他的缺点就是两个数可能比较多次 ， 因为两个数据会多次分不过他们不会出现数据的交换 。
效率也是很高的 。
10.快速排序 ， 堆排序 ， 合并排序 ， 希尔排序的比较 ， 他们的时间复杂的都是n*log(n) ， 我认为在使用上快速排序最广泛 ， 他原地排序 ， 虽然不稳定 ， 可是很多情况下排序根本就不在意他是否稳定 。
他的比较次数是比较小的 ， 因为他把数据分成了大和小的两部分 。
每次都确定了一个数的位置 ， 所以理论上说不会出现两个数比较两次的情况 ， 也是在最后在交换 。

23、数据 ， 说以数据交换上也很少 。
合并排序和堆排序也有这些优点 ， 但是合并排序要申请额外的空间 。
堆排序堆已经排好的数据交换上比快速多 。
所以目前快速排序用的要广泛的多 。

来源：(未知)

【学习资料】网址：/a/2021/0126/0021177202.html

标题：排序|排序算法实验报告( 四 )