一、哈希表

1、相关概念

  1.哈希算法

        将数据通过哈希算法映射成一个键值，存取都在同一位置实现数据的高效存储和查找，并通过这种方式来降低时间复杂度

  2.哈希碰撞

        多个数据通过算法后得到简直相同的现象叫哈希碰撞

  3.哈希表

• 存储结构（桶/槽）：一般是一个数组，每个元素被称为一个桶。
• 哈希函数：将键映射到整数，再经过模运算等，得到数组下标，好的哈希函数应尽量使不同键映射到不同的桶

2、哈希表的实现

        在该板块中，我将构建一个存放0 - 100 熟知的哈希表，并以此为里说明哈希表的实现方法

  1.哈希表的插入

        思路：

• 哈希函数：在这里我们用数据除以10得到的余数值区分哈希表的桶
• 定义容量为10的数组指针，数组内指针分别表示每一个桶的地址
• 在目标桶中插入链表节点，节点中存储数据

        代码实现：

typedef struct node{      //定义链表节点变量
    int data;              //存贮的数据
    struct node *pnrext;   //下一个节点的地址
}linknode;

int *phashtable[10];       //定义数组指针

void insert_hashtable(int tmpdata)
{
    linknode *ptmpnode = NULL;      //插入的节点
    linknode **pptmpnode = NULL;    //桶寻址变量
    int key = 0;                    //存储余数变量

    key = tmpdata % 10;             //哈希函数
    for(pptmpnode = &phashtable[key];*pptmpnode != NULL && (*pptmpnode)->data <tmpdata;pptmpnode = &(*pptmpnode)->pnext);    //找到要插入的位置
    
    ptmpnode = malloc(sizeof(linknode));      //创建节点
    if(NULL == ptmpnode)
        prrer("error");
    
    ptmpnode->data = tmpdata;                 //将节点插入目标位置
    ptmpnode->pnext = *pptmpnode->pnext;
    *pptmpnode = ptmpnode;
}

2.哈希表的遍历

        思路：

        利用循环语句访问哈希表每一个桶区的链表

        代码实现：

void show_hashtable(void)
{
    linknode *ptmpnode = NULL;
    int i = 0;
    
    for(i = 0;i < 10;i++)
    {
        ptmpnode = phashtable[i];
        while(ptmpnode != NULL)
        {
            printf("%d ",ptmpnode->data);
            ptmpnode = ptmpnode->pnext;
        }
    }
}

3.哈希表的查找与销毁

        思路：与哈希表的遍历思路相同，分别查找或删除每一个同上的链表

        代码实现：

/* 哈希表的查找 */
 linknode *find_hashtable(int tmpdata)
 {   
    int key = 0;
    linknode *ptmpnode = NULL;
    key = tmpdata % 10;
    ptmpnode = phashtable[key];
    while (ptmpnode != NULL && ptmpnode->data <= tmpdata)
    {
        if (ptmpnode->data == tmpdata)
        {
            return ptmpnode;
        }
        ptmpnode = ptmpnode->pnext;
    }
    return NULL;
 }

/* 哈希表的销毁 */
 int destroy_hashtable(void)
 {
    int i = 0;
    linknode *ptmpnode = NULL;
    linknode *pfreenode = NULL;
    for(i = 0; i < INDEX; i++)
    {
        ptmpnode = phashtable[i];
        pfreenode = phashtable[i];
        while (ptmpnode != NULL)
        {
            ptmpnode = ptmpnode->pnext;
            free(pfreenode);
            pfreenode = ptmpnode;
        }
        phashtable[i] = NULL;
    }
    return 0;
}

二、几种时间复杂度较低的排序算法

1、插入排序

  1.特点：

• 时间复杂度为 O(n*n),如果是有序数列的话将会降为 O(n)
• 是一种稳定的排序算法（稳定是指具有相同关键字的元素在序列中的相对顺序保持不变）

  2.排序方法：

• 将要插入的元素从序列中取出，使其依次与前边的元素比较
• 比元素大的元素往后走，直到前一个元素比要插入的元素小，或者到 达有序数列开头停止

  3.代码实现

        思路：从数据的第一个数开始，大的数往右移，最后将数据插入到合适的位置，在该位置左边的书均比自身小，右边的数据均比自身大

void insert_sort(int *arry,int len)        //传入数组首地址与数组长度
{
    int i = 0;
    int j = 0;
    int tmp = 0;

    for(j = 1;j < len;j++)
    {
        tmp = arry[j];
        for(i = j,i > 0 && arry[i - 1] > tmp;i--)    //找到比当前值大的数
        {
            arry[i] = arry[i - 1];                   //将数据右移挖坑
        }
        arry[i] = tmp;                               //填坑
    }
}

2、希尔排序

  1.特点

• 时间复杂度为O(nlogn)
• 是一种不稳定的排序方法

  2.排序方法：

• 通过选择不同的步长，将序列分成若干个小序列
• 通过插入排序的方法，完成小数组的排序，让无序的序列变成部分有序的序列
• 缩短步长并完成之后新组合小数组的排序，直至步长为一时完成序列的排序

  3.代码实现：

void shell_sort(int *arry,int len)
{
    int i = 0;
    int j = 0;
    int step = 0;
    int tmp = 0;

    for(step = len / 2;step > 0;step /= 2)                   //逐步缩短步长
    {
        for(j = step;j < len;j++)                            //完成小序列的插入排序
        {
            tmp = arry[j];
            for(i = j;i >= step && arr[i-1] > tmp;i -= step)
            {
                arry[i] = arry[i - step];
            }
            arry[i] = tmp;
        }
    }
}

3、快速排序

  1.特点

• 时间复杂度与希尔排序相同
• 是一种不稳定排序算法

  2.排序方法

• 从最左边找一个数作为键值，找一个比他小的数放在左边，找一个比它大的数放右边，键值放在中间
• 若两边有其他元素，递归调用快速排序

  3.代码实现

void quiet_sort(int *arry,int low,int high)
{
    int i = 0;
    int j = 0;
    int key = 0;

    key = arry[low];
    i = low;
    j = high;

    while(j > i && arry[j] > key)  //从右端开始找一个比键值小的数
    {
        j--;
    }
    if(j > i)                      //将小的数放在键值左边
    {
        arry[i] = arry[j];
    }
    
    while(i < j && arry[i] < key)  //从左端开始找一个比键值大的数
    {
        i++;
    }
    if(i < j)                      //将大值放到键值右边
    {
        arry[j] = arry[i];
    }

    arry[i] = key;                 //将键值赋给相遇点

    if(i-1 > low)                  //若有元素未参与排序，递归调用本函数
    {
        quiet_sort(arry,low,i-1);
    }
    if(i+1 < high)
    {
        quiet_sort(arry,i+1,high);
    }   
}

4、二分查找

        功能：在有序数列中快速找到目标值

        思路：

• 找到中值
• 若中止小于目标值，则在序列上半区继续找中值与目标值比较
• 若中值大于目标值，则在序列下半区继续找中值与目标值比较
• 重复上述步骤，直到找到目标值的位置

        代码实现：

int mid_serach(int *arry,int low,int high,int tmpdata)
{
    int mid = 0;

    if(low > high)                        //没找到返回-1
        return -1;    

    mid = (low + high) / 2;

    if(arry[mid] == tmpdata)               //若满足条件，输出目标值序号
    {
        return mid;
    }
    if(arry[mid] > tmpdata)                //若不满足条件，递归嵌套
    {
        mid_serach(arry,low,mid,tmpdata)
    }
    if(arry[mid] < tmpdata)
    {
        mid_serach(arry,mid,high,tmpdata)
    }
}