排序
2016-07-31 23:30:15 0 举报AI智能生成
数据结构
作者其他创作
大纲/内容
插入类排序
直接插入排序
时间复杂度
平均情况O(n^2)
最坏情况O(n^2)
最好情况O(n)
空间复杂度 O(1)
算法思想
每趟将一个待排序的元素作为关键字，按照其关键字值的大小插入到已经排好的部分序列的适当位置上（从后向前比对插入），直到插入完成。
折半插入排序
时间复杂度 平均情况O（n^2）
最差情况O（n^2）
最好情况O（nlog2n）
空间复杂度 O（1）
算法思想
折半查找的一个基本条件是序列已经有序，将未排序的数据与原有序列中间处的数值进行对比，判断新数据插入低半区还是高半区，然后再将新数据与低半区（或高半区）的数据中间处的数值进行对比，以此类推，直到找到合适位置，将此位置之后的数据全部向后移动一位，再将新数值插入。
希尔排序（不稳定）
时间复杂度 O（nlog2n）
空间复杂度 O（1）
算法思想
希尔排序又叫缩小增量排序。
例如，先以增量5来分割序列，即将下标1、6、11、16、……的记录分成一组，将将下标2、7、12、17、……的记录分成一组等，然后分别对这些组进行直接插入排序，这是一趟希尔排序。
将上面排好序的整个序列，再以增量3分割，即将下标为1、4、7、10、13、……的记录分成一组，将下标为2、5、8、11、14、……的记录分成一组等，然后然后分别对这些组进行直接插入排序，这又是一趟希尔排序。
最后以增量1分割整个序列，其实就是对整个序列进行一趟直接插入排序，从而完成整个希尔排序。
【注】
①希尔排序是不稳定的
②增量5、3、1是逐渐缩小的
③增量序列最后一个值一定是1
④增量序列中的值没有除1以外的公因子，例如8、4、2、1这样的序列就不要取（8、4、2有公因子2）
交换类排序
起泡排序
时间复杂度
平均情况为 O（n^2）
最好情况为 O（n）
最坏情况为 O（n^2）
空间复杂度 O（1）
算法思想
第一个数和第二个数比较，如果第一个大，则二者交换，否则不交换；然后第二个和第三个比较，如果第二个大，则二者交换，否则不交换……以此类推，最终最大的那个数被交换到了最后，一趟起泡排序完成。
第二趟即针对以上所有数据重复以上步骤（除去最后一个数）
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
【注】起泡排序算法结束的条件是在一趟排序过程中没有发生元素交换
快速排序（不稳定）
时间复杂度
平均情况为 O（nlog2n）
最好情况为 O（nlog2n）
最坏情况为 O（n^2）
空间复杂度 O（nlog2n）
算法思想
一趟快速排序是以一个“枢轴”（通常是选第一个数为枢轴）为中心，将序列分成两部分，枢轴的一边全是比它小或者小于等于的，另一边全是比它大或者大于等于的
【注】
①就平均时间而言，快速排序是所有排序算法中最好的。
②快速排序的排序趟数和初始序列有关
选择类排序
简单选择排序（不稳定）
时间复杂度O（n^2）
空间复杂度 O（1）
算法思想
从头至尾顺序扫描序列，找出最小的一个数据，和第一个数据交换，接着从剩下的数据中继续这种选择和交换，最终使序列有序。
【注】
①完全二叉树的高度为⌈log2(n+1)⌉ 所以时间复杂度是O（nlog2n）
②时间复杂度最坏情况下也是O（nlog2n），这是堆排序相对于快速排序的最大优点
③堆排序空间复杂度为O（1），在所有时间复杂度为O（nlog2n）的排序中是最小的，这也是其一大优点
④堆排序适合的场景是记录数很多的情况，典型例子是从10000个记录中选出前10个最小的。如果记录数少，则不提倡使用堆排序
堆排序（不稳定）
时间复杂度 O（nlog2n）
空间复杂度 O（1）
1.算法思想
堆是一种数据结构，可以把堆看成一棵完全二叉树。完全二叉树满足：任何一个非叶节点的值都不大于其左右孩子节点的值（父亲小孩子大 小顶堆），或任何一个非叶节点的值都不小于其左右孩子节点的值（父亲大孩子小 大顶堆）。
将一个无序序列调整为一个堆，就可以找出这个序列的最大或最小值（即完全二叉树的根节点的值），然后将找出的这个值交换到序列的最后或最前，这样有序序列元素增加一个，无序序列元素减少一个，对于新的无序序列重复这样的在操作，就实现了排序。
2.执行流程（以大顶堆为例）
①从无序序列所确定的完全二叉树的第一个非叶子节点开始，从右至左，从下至上，对每个节点进行调整，最终将得到一个大顶堆。
对节点的调整方法如下：将当前节点a的值，与其孩子节点进行比较，如果存在大于a值的孩子节点，则从中选出一个最大的一个与a交换，当a来到下一层的时候，重复上述过程，直到a的孩子结点值都小于a的值为止。
②将当前无序序列中第一个元素，反应在树中是根节点（假设为a），与无序序列中最后一个元素交换（假设为b），a进入有序序列到达最终位置，无序序列中元素减少一个，有序列中元素增加一个，此时只有节点b可能不满足堆的定义，对其进行调整。
③重复②中过程，直到无序系列中的元素，剩下一个时排序结束。
【注】
①完全二叉树的高度为⌈log2(n+1)⌉ 所以时间复杂度是O（nlog2n）
②时间复杂度最坏情况下也是O（nlog2n），这是堆排序相对于快速排序的最大优点
③堆排序空间复杂度为O（1），在所有时间复杂度为O（nlog2n）的排序中是最小的，这也是其一大优点
④堆排序适合的场景是记录数很多的情况，典型例子是从10000个记录中选出前10个最小的。如果记录数少，则不提倡使用堆排序
二路归并排序
时间复杂度 O（nlog2n）
空间复杂度 O（n）
算法思想
将原始序列看成n个只有一个元素的子序列；两两归并，形成若干个有序二元组（最后一个子序列长度可能是1，也可能是2）；再两两归并，形成若干个有序四元组（同样最后的子序列中不一定有四个元素）……以此类推，直到最后只有两个子序列，再进行一次归并，就可完成整个二路归并排序。
基数排序
时间复杂度 O（d（n+rd））
空间复杂度 O（rd）
算法思想
基数排序的思想是多关键字排序。
最高位优先：先按最高位排成若干子序列，再对每个子序列按次高位排序，扑克牌的例子，就是先按花色排成四个子序列，再对每个花色的13张牌进行排序，最终使所有扑克牌整体有序。
最低位优先（重点）：这种方式不必分成子序列，每次排序全体元素都参与。最低位可以优先这样进行，不通过比较，而是通过分配和收集。扑克牌的例子，可以先按数字将牌分配到13个桶中（所谓的桶，其实是一个先进先出的队列，从桶的上面进，下面出 ），然后再从第一个桶开始依次收集，再将收集好的牌，按花色分配到四个桶中，然后还是从第一个桶开始依次收集，经过两次分配和收集操作，最终使牌有序。（如果全是数字的数据，要从最低位也就是个位开始分配）
【注】
①基数排序适合的场景是序列中的元素数很多，但组成元素的关键字的取值范围较小，如数字0~9是个可以接受的。
②如果关键字的取值范围很大，如26个字母，并且序列中大多数元素的最高为关键字都不相同，那么可以考虑使用最高为优先法，先据最高位排成若干子序列，然后分别对这些子序列进行直接插入排序。
③时间复杂度中：n为序列中的元素数；d为元素的关键字位数，如930，由3位做成，d=3；rd为关键字的取值范围，如930，每一位都是数字，取值范围是0~9，所以rd=10.
0 条评论
下一页
为你推荐
查看更多
