查找和排序

字数统计: 2.1k字   |   阅读时长≈ 8分

查找

查找的方法种类：

顺序查找、折半查找、分块查找、树表查找及Hash表查找等等。查找算法的优劣将影响计算机的使用效率，应根据应用场合选择相应的查找算法。

key：关键字，主key：一定不会有重复的关键字。

记录：一条数据项。

监视哨：顺序表的头节点不用于储存记录，用于在查找时记录要查找key，从顺序表尾网前遍历，如果没有一条记录和key匹配，头节点一定是匹配的（头结点是刚刚写进去的key），查找结构将返回0，代表没有查找到。

不用监视哨查找失败就是返回-1。

  • 顺序查找

从尾到头依次比较每条记录和key是否相等

  • 折半查找

折半查找的记录必须是有序的记录。

每次取low和high的中间那条记录和key比较，不断缩减查找的范围low~high。直到匹配查找成功，或者查找的范围为的 high < low 代表查找失败。

小结：优点：折半查找对存在大量记录时效率高，缺点：记录必须要有序排列。

  • Hash表查找

将记录和储存位置建立关系，得到一张表，通过hash表（位置表）就能算出位置里面的值。达到不需要每次查找都要比较很多次的缺点。

映射：字面量到值建立关系。建立关系的：H(key) – f –> key，f 叫做hash函数。实际是个地址映射函数。

冲突：不同的key通过哈希函数可能得到同一个地址。

减少冲突方法：选取hash表时尽量使记录均匀分布在地址范围内。

hash函数

链表地址法：

把有冲突的都串在一个链表里。

排序

基本概念：

稳定排序和非稳定排序：相同记录排序后的顺序。

内排序和外排序：记录储存的位置，RAM或者FLASH。

主要讲的是内排序，记录储存在内存中的排序。

内排序分类：插入排序、交换排序、选择排序、归并排序、基数排序。

  • 直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 直接插入排序算法 */
/* 
   1.首先将record分成两个表，一个是有序表：只含有一个元素，另一个是无序表：含record_size - 1个元素
   2.首先j = i -1找到有序表的表尾，从无序表取头节点record[i]，先保存在temp里面，然后依次从尾到头遍历有序表，
   有序表工作下标每次向前移动一位， 找到temp > record[j]的位置，或者已经到达有序表的表头减一（越界）j < 0 停止移动j工作下标，
   record[j + 1] = temp 完成本个节点的插入，i++无序表表头++。
   3.循环2步骤，直到无序表表头下标越界record数组，停止。
   */
int pkt_direct_insert_sort(int *record, int record_size)
{
    int i = 1, j = 0;           /* j是有序表的表尾，i是无序表的表头 */
    int temp;

    while (i < record_size) /* i到达数组的最后的后一位，已越界，停止循环 */
    {
        j = i - 1;              /* 计算有序表的尾节点下标 */
        temp = record[i];
        while (temp < record[j] && j >= 0)
        {
            record[j + 1] = record[j];  /* 有序表节点依次向后移到一位，直到找到 temp >  record[j] */
            j--;
        }
        record[j] = temp;   /* 插入temp */
        i++;                    /* 无序表表头向后移到一位 */
    }
}

直接插入排序：1.直接：从头到尾每次逐个比较简单粗暴，2.插入：通过比较后找到插入点进行一次插入。

小结：如果待排序的是链表而不是顺序表采用此方法效率更高，因为插入节点后的所有节点不需要一次向后移到，如果记录很多在查找有序表的时候可以再增加采用折半查找法提高查找效率。

  • shell排序算法

直接排序算法的改进：将需要排序的记录分组，分成若干个子记录组，首先在若干个子记录组内部直接插入排序。

1.分组：按增量分组，初始增量：d = N / 2

2.对每组交替直接插入排序

3.逐渐减小增量

过程：

1.将10个记录分成5组子记录，增量为 10 /2 = 5

2.对每组进行直接插入排序

排序后结果：12 、25 、 36 、24、8、50、36、66、76、95

3.继续缩小分组的增量得到新的2个记录组，增量等于是那个一次增量 / 2：5 / 2 = 2

排序后结果：8、24、12、25、36、50、36、66、76、95

4.再继续缩减增量：2 / 2 = 1

排序后结果：8、12、24、25、36、36、50、66、76、95

5.增量：1 / 2 = 0，增量 d < 0 排序结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* shell排序 */
int pkt_shell_sort(int *record, int record_size)
{
    int i, j;           /* i是有序表的表尾，j是无序表的表头 */
    int temp;
    int d;

    for (d = record_size / 2; d > 0; d /= 2)
    {
        
        for (i = d; i < record_size; i++) /* i无序表头到达数组的最后的后一位，已越界，停止循环 */
        {
            j = i - d;              /* 计算有序表的尾节点下标 */
            temp = record[i];
            while (temp < record[j] && j >= 0)
            {
                record[j + d] = record[j];  /* 向后移动一位，给temp腾位置 */       
                j -= d;
            }
            record[j + d] = temp;   /* 插入temp */  
        }
    }
}

小结：shell排序内部采用直接插入排序，将记录分组，对各个记录“跳跃”式的排序，然后调整记录分组的个数，这样总的key的比较次数有所减少，尤其是记录移到的次数大大降低。

  • 快速排序

直接插入排序属于插入排序，快速排序属于交换排序。

一般把记录的第一个元素作为基准

通过一趟排序下来，确定基准的位置，基准左边的数都小于基准，基准右边的数都大于基准。

通过一趟排序，确定了基准最终的位置，并得到两组小的记录（基准不在其中），下一趟排序本次的基准就不参与了。之后不断得到更多的记录小组，记录组中的成员不断减小，直到没有组可分，也就是素有的元素都成了某一趟比较的基准。

递归实现快速排序：

因为每趟的排序的操作都是一样的，但前一趟的排序后才能产生新的记录组，才能接着对新的记录组排序，所以可以采用递归函数。

1.确定第一个节点为基准，对需要排序的记录进行快速排序。

2.得到两组新的记录，然后确定两组中的第一个节点为基准，再随这两个组进行快速排序。

3.直到有所记录组基准两边都没有元素：一分配基准后就有 i = j，这就是递归的结束条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* 一趟快速排序 */
int pkt_quick_pass(int *record, int i, int j)
{
    int temp;       /* 基准 */
    temp = record[i];       /* 基准 */

    while (i < j)
    {
        while (i < j && record[j] >= temp)  /* 从下界比较，在高的一边找小于temp的值的下标j */
        {
            j--;
        }
        if (i < j)              /* 证明由于 record[j] >= temp 条件不成立退出的while */
            record[i] = record[j]; /* 交换高一边的元素到低的一边去 */

        while (i < j && record[i] <= temp)  /* 从上界比较，在低的一边找大于temp的值的下标i */
        {
            i++;
        }
        if (i < j)
            record[j] = record[i]; /* 交换低一边的元素到高的一边去 */
    }

    record[i] = temp;        /* 此时肯定是 i == j，基准的位置i保存基准 */
    return i;                /* 返回本次比较的基准位置 */
}

/* 快速排序：递归实现 */
void pkt_quick_sort(int *record, int low, int high)
{
    int mid;        /* 基准 */
    
    if (low < high)
    {
        mid = pkt_quick_pass(record, low, high);  /* 一趟快速排序 */
        pkt_quick_sort(record, low, mid - 1); /* 基准左边快速排序 */
        pkt_quick_sort(record, mid + 1, high); /* 基准右边快速排序 */
    }
}

小结：快速排序的思想就是交换，在low和high区域，在low++边找到大于基准的值就交换给high边，然后再在hight–边找一个小于基准的值交换给low边，直到low和high相遇。

代码仓库：http://gitea.880755.xyz/private/sort.git

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

从事嵌入式开发