排序

1 衡量排序算法质量

    1）时间效率：排序速度

    2）空间效率：占内存辅助空间的大小

     3）稳定性：相等的两个数，排序后次序不变

 排序方法

1 插入排序

 1）直接插入排序：将第二到n个序列，依次与前n个序列比较，逐个插入，直到整个序列有序（n-1趟）

    1）时间复杂度：n的平方

     2）空间复杂度：仅占用一个缓冲单元 O(1)

    2）算法的稳定性：稳定

  2）希尔排序：取正整数d1<n，把所有相隔d的元素归为一组，各自进行直接插入排序，迭代取d2<d1

一般取d1=n/2，di+1=di/2（如果di/2<2，那么接下来分组di=1 ），如果结果为偶数，di+1

不稳定，序列不同，效率不同

选择排序

优：简单 劣：效率低

  1）直接选择排序

    从待排序数据中选择最小，存放于已排序列最后

  2）堆排序

  堆是满足下列性质的数列{r1,r2,...,rn

小顶堆/大顶堆

  小顶堆：根节点小于其左右子树

堆排序：利用堆的特性对记录进行排序。将无序序列建成堆，取最小/大值置于根，取次小/大、次次小/大值置于左、右子树（无序）。循环

小顶堆输出：while{输出根

                                              取最后的数置于根。

                                              while(最小数不能下移){与左右节点比较，置换小的}

                                              }

交换排序

1）冒泡排序

循环{

       从前到后，两两比较，大者置后

}

若顺序，则只需一趟；若逆序，则需要n-1趟

2）快速排序

对于r[0....n-1进行快速排序

选定基准元素x（一般选第一个），初始指针i=0+1；j=n-1。

while(i!=j){

      j 从后往前搜寻小于x的数，

      r[j]与x相颠倒。

      i从前往后搜寻小于x的数

      r[i]与x相颠倒。

}

//此时完成一趟循环（结果）：子序列1（小于x的数） x  子序列2（大于x的数）

迭代循环子序列1 子序列2 （直到每个子序列长度为1）

归并排序

将一个长度为n的无序序列看成是n个长度为1 的有序序列

while(进行log2N次排序){

 两两归并（排序）有序序列

}

排序

查找

静态查找

1 顺序查找

    1）查找方法：逐一比较、顺序查找。

     2）性能：平均查找长度：(n+1)/2，时间效率O(n)

     3）优：算法简单，适应面广，对表没有要求

     4）缺点：n值较大时，平均查找长度大，效率低

2 折半查找/二分查找

     1）查找方法：

           数据排序

           while(要查找元素!=中间值){

              与中间值比较

              大则选择前半部分

              中间值=前半部分/2（如果前半部分%2=0，则中间值前移，否则向上取整）

              小则选择后半部分

              中间值=同上

            }

2）平均查找长度：

3）要求顺序存储、按关键字有序排序。适用于不经常增删改的

3 分块查找/索引顺序查找

   位于顺序查找和折半查找之间

   1）把表分成若干块（保证块间有序（后一块的关键字（最     大）大于与之紧邻的右侧那块的关键字（最大）））

   2）按关键字建立索引表（关键字，块起始位置（1开始））

   3）折半查找索引表，确定所处块

   4）块内顺序查找

哈希表

  1）查找方法：根据关键码值直接进行访问的数据结构

  2）映射函数：散列函数；存放记录的数组：散列数组

  3）优点：查找速度极快(O(1))，查找效率与元素个数无关

  4）冲突：不同码值映射到同一位置

减少冲突：1）构造好的哈希函数：所选函数简单，提高运转速度；计算出的地址应在哈希地址中均匀分配，减少空间浪费

                   2）制定规则，在冲突发生时调整位置