直接插入排序将后面的无序区中的元素挨个与前面的有序区中的元素比较插入有序区。1.将顺序表中R[0]用作哨兵按索引i2...n的次序将R[i]向有序区R[1...i-1]中执行插入操作。2.插入操作可采取在有序区中从后向前的查找比较和移动的方法。3.此操作中比较的次数与原序列的排列状态有关原序列为正序时在插入操作中插入位置为尾部即只需要比较一次原序列为反序时插入位置为头部则需要和有序序列中的每个元素比较一次。时间复杂度正序时O(n)反序时 O(n²)平均时间复杂度 O(n²)空间复杂度O(1)就地排序直接插入排序是稳定的。二分法插入排序在查找插入位置时使用二分法查找替换顺序查找。等步分组插入排序、希尔排序缩小增量排序基本思路是分组的直接插入排序。分组由多到少、步长由大到小、每组元素由少到多。1.把序列分为dlength/2个组分组方法为所有距离为d的元素划到一个组内距离d称为增量。2.各组内进行直接插入排序。3.按照避免增量序列中的值互为倍数及最后一个增量必须为1的原则设定增量序列d。4.d除以2减小继续执行执行步骤1、2直到d为1。希尔排序是不稳定的。冒泡交换排序bubble sort1.从下面无序区的最底部元素开始向上两两比较最小者交换到无序区的最顶部它同时也处了在有序区的最底部。2.当某一趟扫描中的两两比较未出现交换则说明无序区已全部有序排序结束。时间复杂度正序时O(n)反序时 O(n²)平均时间复杂度 O(n²)空间复杂度属于就地排序冒泡排序是稳定的。性能低于直接插入排序。快速交换排序、基准分冶快速排序算法是对冒泡算法的一种改进算法减少重复的数据移动。1.确定基准在区间R中可随机选择一个元素作为基准和R[0]交换位置。2.对比划分以R[0]作为基准做一趟划分操作从区间两端开始向中间依次交替与基准比较根据小在左侧、大在右侧的规则与基准交换位置最终生成比基准值小和大的左右两个无序的子区间。3.递归对每个子区间递归定基准-划分过程。划分操作结果中有一个子区间为空及两个子区间都不为空这两种情况比较前者整体排序中做的比较次数更多。时间复杂度最好 O(nlgn)最坏 O(n²)平均 O(nlgn)空间复杂度O(lgn)快速排序是不稳定的。直接选择排序1.从后面的无序区中采取贪心选择策略选择最小的元素与无序区头部元素交换即有序区末尾增加一个元素。2.对新的有序区和无序区执行上一步操作。时间复杂度O(n²)空间复杂度O(1)就地排序直接选择排序是不稳定的。插入排序是先在指定位置取元素然后再找合适的位置插入重心在第二步的插入。选择排序是先找最小的元素然后交换到指定位置重心在第一步的选择。堆排序树形选择排序改进了直接选择排序算法利用了完全二叉树的特性调整堆筛选判断调整根子树将根与两个孩子中较大者大根堆交换继而判断调整有变动的子子树。1.构造堆从下往上依次对位置为[n/2]...1为根的子树做调整堆操作。结果构造出了堆此时只是符合堆性质但并不有序。2.将堆根元素交换到无序区尾部。i为本次调整的序号将堆顶元素R[1]和最后一个元素R[n-i1]交换则新的无序区变为R[1...n-i]有序区为R[n-i1,n]。3.重建堆对新的无序区判断调整堆。4.重复2、3步骤共n-1次。时间复杂度O(nlgn)空间复杂度O(1)就地排序堆排序是不稳定的。堆排序在实际应用中往往不如快速排序高效但在优先队列中堆发挥着关键作用。归并排序二路归并排序1.将区间内的元素两两做二路归并。2.将上一步形成的各个有序组两两做二路归并。3.直至全部元素进入同一个有序组。4.二路归并需要同等的辅助空间。时间复杂度O(nlgn)空间复杂度O(n)归并排序是稳定的。以上基于关键字比较的排序时间下限是O(nlgn)而分配排序无须比较关键字通过分配和收集过来实现排序它们的时间复杂度可以下破到线性阶O(n)。分配排序前面的基于关键字比较的排序时间最低是O(nlgn)而分配排序通过分配和收集时间复杂度可达到线性阶O(n)。箱排序桶排序先定义若干有序箱子再把要排序的记录装某个箱子中。第一种箱排序是设置箱子个数和关键字的种类的个数相同。同一种类可以是关键字值相同或映射值相同。第二种桶排序是关键字映射到某个桶中桶中的所有元素再单独做关键字比较排序基数排序基数排序要分析关键字的结构分为多关键字和单关键字每个关键字又由多个位组成。单关键字的每位即每个分量可能取值个数称为基数基数排序是按基数的个数次数从低位到高位对序列元素进行箱排序每箱排序的结果作为下一趟排序的输入。基数排序是稳定的。效率比较直接插入排序、冒泡排序、直接选择排序等算法的时间复杂度为0(n2),这些排序算法简单易懂,思路清楚,算法结构为两重循环,共进行n-1趟,每趟排序将一个元素移动到排序后的位置。数据比较和移动在相邻的两个元素之间进行,每趟排序与上一趟之间存在较多重复的比较、移动和交换,因此排序效率较低。另一类较快的排序算法有希尔排序、快速排序、堆排序及归并排序这些算法设计各有巧妙之处,它们共同的特点是:与相距较远的元素进行比较,数据移动为距离较远,跳跃式地向目的地前进,避免了许多重复的比较和移动。h1直接插入排序/h1将后面的无序区中的元素挨个向前面的有序区中插入。1.将顺序表中R[0]用作哨兵按索引i2...n的次序将R[i]向有序区R[1...i-1]中执行插入操作。2.插入操作可采取在有序区中从后向前的查找比较和移动的方法。3.此操作中比较的次数与原序列的排列状态有关原序列为正序时在插入操作中插入位置为尾部即只需要比较一次原序列为反序时插入位置为头部则需要和有序序列中的每个元素比较一次。时间复杂度正序时O(n)反序时 O(n²)平均时间复杂度 O(n²)空间复杂度O(1)就地排序直接插入排序是稳定的。h1希尔排序分组插入排序/h11.把序列分为d个组分组方法为所有距离为d的元素划到一个组内。2.各组内进行直接插入排序。3.按照避免增量序列中的值互为倍数及最后一个增量必须为1的原则设定增量序列d。希尔排序是不稳定的。h1冒泡交换排序/h11.从下面无序区的最底部元素开始向上两两比较最小者交换到无序区的最顶部它同时也处了在有序区的最底部。2.当某一趟扫描中的两两比较未出现交换则说明无序区已全部有序排序结束。时间复杂度正序时O(n)反序时 O(n²)平均时间复杂度 O(n²)空间复杂度属于就地排序冒泡排序是稳定的。性能低于直接插入排序。h1快速交换排序基准分冶/h11.确定基准在区间R中可随机选择一个元素作为基准和R[0]交换位置。2.对比划分以R[0]作为基准做一趟划分操作从区间两端开始向中间依次交替与基准比较大根据小在左侧、大在右侧的规则与基准交换位置最终生成比基准值小和大的左右两个无序的子区间。3.递归对每个子区间递归定基准-划分过程。划分操作结果中有一个子区间为空及两个子区间都不为空这两种情况比较前者整体排序中做的比较次数更多。时间复杂度最好 O(nlgn)最坏 O(n²)平均 O(nlgn)空间复杂度O(lgn)快速排序是不稳定的。h1直接选择排序/h11.从后面的无序区中选择最小的元素与无序区头部元素交换即有序区末尾增加一个元素。2.对新的有序区和无序区执行上一步操作。时间复杂度O(n²)空间复杂度O(1)就地排序直接选择排序是不稳定的。插入排序是先在指定位置取元素然后再找合适的位置插入重心在第二步的插入。选择排序是先找最小的元素然后交换到指定位置重心在第一步的选择。h1堆排序树形选择排序/h1调整堆筛选判断调整根子树将根与两个孩子中较大者大根堆交换继而判断调整有变动的子子树。1.构造堆从下往上依次对位置为[n/2]...1为根的子树做调整堆操作。结果构造出了堆此时只是符合堆性质但并不有序。2.将堆根元素交换到无序区尾部。i为本次调整的序号将堆顶元素R[1]和最后一个元素R[n-i1]交换则新的无序区变为R[1...n-i]有序区为R[n-i1,n]。3.重建堆对新的无序区判断调整堆。4.重复2、3步骤共n-1次。时间复杂度O(nlgn)空间复杂度O(1)就地排序堆排序是不稳定的。h1归并排序二路归并排序/h11.将区间内的元素两两做二路归并。2.将上一步形成的各个有序组两两做二路归并。3.直至全部元素进入同一个有序组。4.二路归并需要同等的辅助空间。时间复杂度O(nlgn)空间复杂度O(n)归并排序是稳定的。以上基于关键字比较的排序时间下限是O(nlgn)而分配排序无须比较关键字通过分配和收集过来实现排序它们的时间复杂度可以下破到线性阶O(n)。h1箱排序桶排序/h1分配排序不基于关键字比较而是通过分配和收集过程实现排序。时间复杂度可达线性阶。第一种箱排序是设置箱子个数和关键字的种类的个数相同第二种桶排序是关键字映射到某个桶中桶中的所有元素再单独做关键字比较排序h1基数排序/h1基数排序要求分析关键字的结构分为多关键字和单关键字每个关键字又由多个位组成。单关键字的每位即每个分量可能取值个数称为基数基数排序是按基数的个数次数从低位到高位对序列元素进行箱排序每箱排序的结果作为下一趟排序的输入。基数排序是稳定的。