高级班补充算法

1、1一、常见排序算法的时间复杂度二、排序算法三、查找算法四、进制转换补充算法举例28.Shell排序一、常见排序算法的时间复杂度O(n2)O(nlog2n)O(n(log2n)2)1.直接插入排序法 2.冒泡排序法3.直接选择排序法4.堆排序5.合并排序6.二分插入排序7.快速排序31.选择法排序2.冒泡法排序（沉淀法排序）3.插入法排序4.合并法排序二、排序算法4 对已经存放在数组中的n个数，用按递增顺序排序。选择法基本思想： (1) 从n个数的序列中选出最小的数，与第1个数交换位置； (2) 除第1个数外，其余n-1个数再按(1)的方法选出次小的数，与第2个数交换位置。 (3) 重复(1)

2、n-1遍，最后构成递增序列。1. 选择法排序（比较和交换）5原始数据:8 6 9 3 2 7第1趟交换后 2 6 9 3 8 7 第2趟交换后 2 3 9 6 8 7 第3趟交换后 2 3 6 9 8 7 第4趟交换后 2 3 6 7 8 9 第5趟无交换 2 3 6 7 8 9选择法排序交换过程6输入10个数给a(1)到a(10)输出a(1)到a(10)For i=1 To 9 For j=i+1 To 10a(j)a(imin)真假imin=jimin= iimini真假a(imin)与a(i)对调选择法排序N-S流程图7 对已经存放在数组中的n个数，用按递增顺序排序。冒泡法基本思想： 将

3、相邻两个数比较，将小的调到前面，比较的同时就交换。 例如对序列：9 8 5 4 2 0按递增排序。2.冒泡法排序（比较和交换）8输入10个数给a(1)到a(10)输出a(1)到a(10)For i=1 To 9 For j=1 To 10-ia(j)a(j+1)真假a(j)与a(j+1)交换冒泡法排序N-S流程图9 插入排序的算法思想： 假设数组A(1 to n)中已有n-1个元素，且已经按从小到大排好序，x为要插入的数，若要将x插入A数组中，且使A数组仍保持有序，主要步骤为：3.插入排序法10 （1）将x与A中的元素比较，找到x应插入的位置p； （2）将A(p)-A(n-1)依次向后移一个元

4、素位置，即：A(i+1)=A(i) （3）A(p)=x例如已有排好序的数组A：1 4 7 10 13，现在要将5插入到数组A中。11 将两个有序的数组合并成另一个有序的数组。要求需要合并的两个数组A和B是严格递增（递减）的，将A和B合并成C也是严格递增（递减）的。4.合并法排序12合并法基本思想：（1）先将数组A、B中各取一个元素进行比较，将小的元素放入数组C；（2）取小的元素所在的数组的下一个元素与另一个数组中上次比较后较大的元素比较，重复上述过程，指导某个数组被比较完。（3）将另一个数组的剩余元素抄入数组C中，合并完成。例如：A数组中的元素：2，4，6，10 B数组中的元素：1，3，5，7

5、，9，11 C数组中的元素为？13 查找是程序设计中最常用的算法之一。 所谓查找是要在含有N个元素的数组中查找X的值是否存在。 结果两种：找到和没找到。查找方法： 1. 顺序查找 (无序表) 2. 二分查找 (折半查找) (有序表)三、查找算法14 A数组元素： 32 67 45 12 83 90 20 21 45 341.顺序查找 要查找的X值结果输出： A（3）= X A（9）= X 算法思想:将数组中每个数组元素与 X 一一比较, 适用于一般数组，算法执行效率低；4515 二分查找的要求：被查找的数据是已经排好序（从大到小或从小到大）。二分查找基本思想： 将需要查找的X先与这一列数中的中间一个数比较，如果比它小：则到左边分支中去找，如果比它大：则到右边分支中去找，如果相等：则已经找到。重复上述方法直到没有分支可以查找为止。2.二分查找16 二分查找的要求：被查找的数据是已经排好序（从大到小或从小到大）。 例如数组A中有15个整数： 3，9，12，18，21，25，37，40，48，59，67