算法-排序算法

一、算法和算法分析

什么是算法：

​ 对特定问题的求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

算法的五个重要特性：

• 有穷性
• 确定性
• 可行性
• 输入
• 输出

算法设计的要求：

• 正确性
• 可读性
• 健壮性
• 高效率与低存储

算法效率的度量：

​ 算法的执行时间需要依据该算法所编制的程序在计算机上运行所消耗的时间来度量，一般有两种方法：

事后统计的方法：

​ 很多计算机内部都有计时功能，不同的算法的程序可通过一组或若干相同的统计数据以分辨优劣，例如：time ./a.out，但这种方法有两个缺陷，一是必须先运行依据算法编程的程序，如果程序不满足要求编写程序所耗费的人力物力就浪费了，二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣，因此人们常常采用另一种事前分析法。

事前分析估算的方法：

​ 一个用户高级程序语言编写的程序在计算机上运行所消耗的时间取决于下列因素：

​ 1、依据算法先用何种策略，比如循环操作，可使用函数递归或for、while、do while等循环语句。

​ 2、问题的规模，少量数据的问题求解、大规模数量的问题求解、海量数据的问题求解。

​ 3、书写程序的语言，对于同一种算法，实现的语言级别越高，执行效率就越低。

​ 4、编译程序所产生的机器代码的质量。

​ 5、机器执行指令的速度，相同的编程语言，使用的编译器不同，产生的机器指令就会不同，从而执行的速度就会不同.

​ 总结：同一个算法用不同的语言实现，或者用不同的编译器进行编译，或者不同的计算机上运行，效率均不相同，这表明使用绝对的时间单位衡量算法的效率是不合适的，抛开这些与计算机硬件、软件有关因素，可以认为特定算法“运行工作量”的大小，只依赖于问题的规模，或者说，它是问题规模的函数。

​ 一个算法是由控制结构（顺序、分支、循环等3种基本结构）和原操作（指固有数据类型类型的操作）构成的，则算法时间取决于两者的统合效果，为了便于比较同一问题的不同算法，基本做法是，从算法中选取一种对于 所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。因此用算法执行的次数来代表算法的时间复杂度

​ 所以：算法中基本操作重复执行的次数是问题规模n的某个函数\(f(n)\)，算法的时间量度记叙\(T(n)=O(f(n))\)，它表示问题规模n的增大，算法执行时间的增长率和\(f(n)\)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。

注意：一般时间复杂度取的是一种大约情况不会精确到特别详细，也就是不会百分百正确。

最差时间复杂度：

​ 数据的极端排序顺序会让算法执行效率最差的一种情况。

最优时间复杂度：

​ 数据的极端排序顺序会让算法执行效率最优的一种情况。

平均时间复杂度：

​ 数据的排序顺序队伍事物发展规律，算法执行效率接近真实的一种情况。

空间复杂度：

​ 它代表随着问题规模n的某个函数f(n)，它表示问题规模n的增大，算法所需要的存储空间增长率，被称为算法的空间复杂度。

​ 通常来说，只要算法不涉及到动态分配的空间以及递归、栈所需的空间，空间复杂度通常为O(1)

​ 例如求第N个斐波那契数，空间复杂度即为O（N）。

注意：对于一个算法，其时间复杂度和空间复杂度往往是相互影响的，需要综合考虑

二、查找算法

什么是查找算法：

​ 在一个数据序列中，查找某个数据是否存在或存在的位置，在实际开发过程中使用的频率非常高，例如对数据常见的操作有增、删、改、查，增加数据时需要查询新增加的数据是否重复，删除数据时需要先查询到数据所在位置再删除，修改数据时也需要先查询到被修改的数据在什么位置，查找算法在编程中重要性排列在第一位。

顺序查找：

顺序表的顺序查找：

//	从顺序表中从前往后查找数据，找到返回下标，找不到返回-1
int orderSearch(int *arr, size_t len, int key) {
    for (int i = 0; i < len; ++i) {
        if (key == arr[i]) 
            return i;
    }
    return -1;
}

链表的顺序查找：

ListNode* orderSearch(ListNode *head, int key) {
    for (ListNode *n = head; NULL != n; n = n->next) {
        if (n->data == key) return n;
    }
    return NULL;
}

顺序查找的优点：

• 对待查找的数据没有有序性的要求，无论是否有序都可以顺序查找
• 对待查找的数据的存储方式也没有要求，无论是顺序表还是链表都可以顺序查找

顺序查找的缺点：

• 相比于其他查找算法速度要慢，最优时间复杂度 O(1) 最差O(N) 平均O(N)

二分查找：

​ 数据序列必须有序，然后关键字key与中间数据比较，如果相等则立即返回，如果key小于中间数据，则只需要在中间数据左边继续查找即可，如果key大于中间数据，则只需要在中间数据右边继续查找即可，重复该步骤，直到找到关键字，或中间数据左右两边为空，则查找失败。

//	循环实现  查找前已有序
int binarySearch(int* arr, size_t len, int key) {
    int l = 0, r = len - 1;
    while(l < r) {
        int mid = l + r >> 1;
        if (arr[mid] == key) {
            return p;
        }
        if (arr[mid] < arr[r]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return -1;
}

//	递归实现
int _binarySearch(int *arr,size_t len, int key, int l, int r) {
    if (l > r) return -1;
    int mid = l + r >> 1;
    if (key < arr[mid]) {
        return _binarySearch(arr, len, key, l, mid - 1);
    } else if (key > arr[p]) {
        return _binarySearch(arr, len, key, mid + 1, r);
    }
    return p;
}

int binarySearch(int* arr, size_t len, int key) {
    return _binarySearch(arr, len, key,0, len - 1);
}

二分查找的优点：

​ 查询速度快，时间复杂度：O(log2N)。

二分查找的缺点：

• 对待查找的数据有序性有要求，必须先排序才能二分查找
• 对数据存储结构有要求，不适合链式表中直接使用，因为无法快速地访问中间位置，以及快速地让左右标杆位置进行移动

索引查找：

​ 索引查找是在索引表和主表(即线性表的索引存储结构)上进行的查找，但需要先建立索引表，索引表就类似图书的目录，能大提高查找效率。

给顺序表创建索引表：

typedef struct Stduent
{
    int id;
    char name[20];
    char sex;
   	short age;
    float score;
}Student;

Student stu[10000];	//	主表

//	索引表元素结构
typedef struct Index
{
    int id;
    void* addr;
}Index;

//	索引表
Index indexs[10000];

//	对主表与索引表之间建立索引
void create_index(Student* stu,Index* indexs,size_t len)
{
    for(int i=0; i<len; i++)
    {
        indexs[i].id = stu[i].id;
        indexs[i].addr = stu+i;
    }
}
//	注意：建立索引表后，后面使用索引查找的是索引表，再通过找到的索引表中记录的主表元素的位置信息，来最终找到待查找的数据元素
//	注意：索引表如何建立索引，根据实际需求来选择

索引表的顺序查找：

//	它比直接查询数据的主表的跳转速度要快，如果使用stu[i]查找，i每加1，要跳转过sizeof(Student)个字节数，如果使用索引表indexs[i]查询，i每加1，则只需要跳转sizeof(Index)个字节数，比主表跳转字节数要少。
//	如果主表的数据不存在内存而是存储在磁盘上，而索引表是建立在内存中，通过索引表访问效率、速度远高于访问磁盘的主表
int order_index_search(Index* indexs,size_t len,int id)
{
    for(int i=0; i<len; i++)
    {
        if(indexs[i].id == id)
            return i;
    }
   	/*
   	for(int i=0; i<len; i++)
   	{
   		if(stu[i].id == id)
        	return i;
   	}
   	*/
}

索引表二分查找：

//	需要对索引表先排序
//	对索引表排序的效率和速度要远比直接对主表的排序要快
void sort_index(Index* indexs,size_t len)
{
    for(int i=0; i<len-1; i++)
    {
        int min = i;
        for(int j=i+1; j<len; j++)
        {
            if(indexs[j].id < indexs[min].id)
                min = j;
        }
        if(min != i)
        {
            Index temp = indexs[min];
            indexs[min] = indexs[i];
            indexs[i] = temp;
        }
    }
}

//	对索引表进行二分查找
//	因为索引表已经重新排序了，而主表没有排序过，所以不能返回在索引表中找到元素的下标，该下标与主表对应元素的下标很可能不一致了，所以需要直接返回主表对应元素的地址
Student* binary_index_search(Index* indexs,size_t len,int id)
{
    int l = 0, r = len-1;
    while(l <= r)
    {
        int p = (l + r)/2;
        if(indexs[p].id == id)
            return indexs[p].addr;
        if(id < indexs[p].id)
            r = p-1;
        if(id > indexs[p].id)
            l = p+1;
    }
    return NULL;
}

给链表创建索引表：

//	给链表head创建一张顺序的索引表 表中的元素是ListNode* 用来指向链表中的节点 
//	返回值是返回索引表首地址，len_i输出型参数，返回索引表中元素的个数
ListNode** create_index_list(ListNode* head,size_t* len_i)
{
    if(NULL == head || NULL == len_i) return NULL;
    //	索引表的长度
    *len_i = 0;
    ListNode** indexs = NULL;
    //	遍历链表head 给每个节点建立普通索引
    for(ListNode* n=head; NULL!=n; n=n->next)
    {
        //	申请索引表元素ListNode*的内存
        indexs = realloc(indexs,sizeof(ListNode*)*(*len_i+1));
        //	让索引表中的最后一个元素指向对应的链表节点
        indexs[(*len_i)++] = n;
    }
    
    //	对索引表进行排序，交换索引表中指针的指向
    for(int i=0; i<(*len_i)-1; i++)
    {
        int min = i;
        for(int j=i+1; j<*len_i; j++)
        {
            if(indexs[j]->data < indexs[min]->data)
            	min = j;
        }
        if(min != i)
        {
            //	交换索引表中指针的指向 不修改链表
            ListNode* temp = indexs[min];
            indexs[min] = indexs[i];
            indexs[i] = temp;
        }
    }
}

//	链表的二分查找，本质上是对顺序的索引表进行二分
int binary_list_index_search(ListNode** indexs,size_t len,int key)
{
    int l = 0, r = len - 1;
    while(l <= r)
    {
        int p = (l + r)/2;
        if(indexs[p]->data == key)
            return p;
        if(key < indexs[p])
            r = p-1;
        if(key > indexs[p])
            l = p+1;
    }
    return -1;
}

索引查找的优点：

• 对于顺序表的顺序查找，索引查找可以缩短数据的查找跳转范围
• 对于顺序表的二分查找，通过排序索引表也能提高排序的速度
• 对于链式表，可以先建立顺序的索引表后，进行之前无法实现的二分查找了

索引查找的缺点：

• 使用了额外的存储空间来创建索引表，是一种典型的以空间换时间的算法策略

索引查找的使用场景：

• 如果针对的是内存中的顺序表中的数据，通过索引查找提升的速度和效率其实并不是很明显，毕竟内存的运算速度很快
• 但是对于存储在机械硬盘上的数据，通过在内存中建立对应硬盘数据的索引表，访问起来提升的效率就很多了，因此在一些常用的数据库中的索引查找使用非常多

分块查找：

​ 先对数据进行分块，可以根据日期进行分块，可以对整形数据根据数据的最后一位分为10个分表，针对字符串数据可以根据第一个字母分为26个分表，然后再对这些分表进行二分查找、顺序查找，它是分治思想的具体实现。

分块查找的优点：

​ 可以把海量数据进行分化，降低数据规模，从而提升查找速度。

分块查找的缺点：

​ 操作比较麻烦，可能会有一定的内存浪费。

二叉排序树和平衡二叉树：

​ 二叉排序树也叫二叉搜索树是根据数据的值进行构建的，然后进行前序遍历查找，它的查找原理还是二分查找，我在二叉搜索树中已经详细过，在此不再赘述。

​ 平衡二叉树首先是一棵二叉排序树或二叉搜索树，二叉排序树在创建时，由于数据基本有序，会导致创建出的二叉排序树呈单枝状，或者随机数据的插入、删除导致二叉排序树左右失衡呈单枝状，就会导致二叉树排序的查询速度接近单向链表的O(N)；

​ 平衡二叉树要求左右子树的高度差不超过1，这样就会让二叉排序树左右均匀，让二叉排序树的查找速度接近二分查找（要了解AVL树和红黑树的区别）。

哈希表查找：Hash

​ 在查找数据时需要进行一系列的比较运算，无论是顺序查找、二分查找、索引查找、这类的查找算法都是建立在比较的基础上的，但最理想的查找算法是不经过任何比较，一次存取就能查找到数据，那么就需要在存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和数据中的唯一的存储位置相对应。在查找时，根据对应关系找到给定的关键字所对应的数据，这样可以不经过比较可以直接取得所查找的数据。

​ 我们称存储位置在关键字之间的对应关系为哈希函数，按这个思想建立的表为哈希表。

​

设计哈函数的方法：

直接定值法：

取关键字的值或某个线性函数作为k哈希地址：H(key) = key 或H(key)=a*key-b，但这种方法对数据有很高的要求。

问题：假设有10000个范围在0_{255之间的随机整数，请任意输入0}255之间的一个整数，帮查询该整数总共出现了多少次？

#include <stdio.h>
#include <stdlib.h>

int main(int argc,const char* argv[])
{
    int arr[10000] = {};

    for(int i=0; i<10000; i++)
    {
        arr[i] = rand() % 256;
    }

    //  建立哈希表
    int hash[256] = {};
    //  通过直接定值法 建立哈希函数
    for(int i=0; i<10000; i++)
    {
        hash[arr[i]]++;
    }

    unsigned char num = 0;
    printf("请输入:");
    scanf("%hhu",&num);

    printf("次数:%d\n",hash[num]);
}  

时间复杂度：O(1)

​ 但是有很大的局限性，因为很多数据是无法直接用做数组的下标的，其次可能会出现数据量少，但是数据值的差值较大，导致哈希表长度过大，造成内存浪费

数字分析法：

分析数据的特点设计哈希，常用方法是找到最大最小值，最大值-最小值+1 确定哈希表的长度，通过 数据-最小值 访问哈希表下标

以上两种方法局限比较大，但计算出的哈希地址没有冲突的可能，以下方法：平方取中法、折叠法、除留余数法等方法对关键字的要求不要，但计算出的哈希地址可能会有冲突。称为哈希冲突

解决哈希值冲突的方法：

• 开方地址法
• 再哈希法
• 链地址法
• 创建公共溢出区

哈希查找的优点：

​ 查找速度极快，时间复杂度能达到O(1)。

哈希查找的缺点：

​ 1、局限性比较大，对数据的要求比较高。

​ 2、设计哈希函数麻烦，没具体的设计哈希函数的方法，只是有一些大致的思路。

​ 3、需要建立哈希表，占用了额外的空间。

​ Hash函数的应用：MD5、SHA-1都属于Hash算法