数据结构-查找排序整理

查找

  • 线性结构
    • 顺序查找:从头到尾线性搜索
    • 折半查找:高低 mid 指针,向中间逼近
    • 分块查找:分成若干子块,拿出最大 / 小值作为索引。先搜索引找块,再块内搜索
  • 树形结构
    • 二叉排序树:左子树小,右子树大
    • 二叉平衡树:左右深度不超过 1
    • 红黑树:平衡树的优化,三次旋转。
  • 散列结构 - 散列表
    • 性能分析
    • 冲突分析
  • 效率指标 - 平均查找长度
    • 查找成功
    • 查找失败

顺序查找

内容:从头到尾线性遍历

时间复杂度(平均):O(n)

折半查找

复杂度:O(logn)

条件:有序数组

内容:

  • 设置高低指针
  • 中间开始,如果值相等则结束
  • 值不相等,高低指针向中间迫近
  • 指针相遇,结束

代码:

int Binary_Search(int A[], int key){
    int low = 0, high = A.size() - 1, mix = 0; // 高低指针
    // 指针未相遇时循环
    while(low <= high){
        mid = low + (high - low)/2;
        if(A[mid] == key)
            return mid;
        else if(A[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }//while
    return -1;
}

二叉排序树查找 == 插入和删除 ==

复杂度:O(logn)

条件:二叉排序树

内容:

  • 树空,查找失败
  • key 为根节点值,查找成功
  • key 小于根节点,查找左子树
  • 查找右子树

代码:

// 非递归
BSTNode* BST_Search(BSTNode* root, int key){
    BSTNode* p = root;
    while(p){
        if(p->data == key)
            return p;
        if(p->data < key)
            p = p->rchild;
        else
            p = p->lchild;
    }
    return NULL;
}

// 递归
BSTNode* BST_Search(BSTNode* root, int key){
    if(root == NULL)
        return NULL;
    
    if(root->data == key)
        return root; // 出口
    else if(root->data > key)
        BST_Search(root->lchild, key);
    else
        BST_Search(root->rchild, key);
}

删除:

插入:

分块查找

内容:

  • 元素划分为 m 块,块内不必有序,块与块之间有序(块1max<块2所有
  • 查找时,先二分法查索引(块),再线性搜索块内。

平均查找长度:[logs(b_1)] + (s+1)/2上取整。

哈希(散列表)== 代码?==

内容:

  • Hash(key) = Addr,通常用除留余
  • 用散列函数数据映射到数组下标、地址、索引
    • 函数会起冲突。== 冲突越少,占用空间越多 ==
    • 使用开地址法和拉链法。
      • 位置有元素,往后再用函数运算后的结果+diHash()找位置
      • H = (H(key) + di)%m di 可以是0、1、2、3也可以是 0方、1方、-1方、2方、-2方
  • 查找的时候直接用相同的函数求索引。
  • 链地址犹豫开地址,除留余优于其他散列函数

时间复杂度:理想情况O(1)(无冲突)

==KMP 算法 ==

排序

  • 插入排序
    • 直接插入:往后遍历,判断A[i]“已排序序列”中的位置,再插入进去。|有序序列|A[i]|无序序列| n^2
    • 折半插入:减小了比较次数。插入位置使用折半查找的方法。nlog2n
    • 希尔排序:每隔五个一分(16、27、38、49),组内排序。再三个一分,再到一个一分就排序成功
  • 交换排序
    • 冒泡排序:两个指针从后往前,小的交换在前面。注意设置哨兵判断结束情况。
    • 快速排序:选择枢纽,小的放在左边,大的放在右边。递归操作。(高低指针向中间迫近,低指针碰到大于的停下,等高指针碰到小于枢纽的,最后交换位置。最最后放入枢纽值)
  • 选择排序
    • 简单排序:选出最小的丢到头部。
    • 堆排序:需要维护一个堆,只能取堆顶元素。
  • 归并排序:全部分成两个一组,组内排序。再四个一组,组内排序(组内前后两个指针,类似快排向中间逼近)。最后到整个数组。
  • 基数排序

849589-20180402133438219-1946132192.png

直接插入排序

直接插入排序
  • 内容:往后遍历,判断A[i]“已排序序列”中的位置,再插入进去。|有序序列|A[i]|无序序列| n^2
  • 复杂度:O(n^2)前到后遍历 + 找插入位置。n(n-1)/2
  • 稳定,适用大多数线性表
  • 代码:

    void InsertSort(int A[], int n){
        for(int i = 1; i < n; i++){
            int temp = A[i]; // 待排关键字
            
            int j = i - 1; // 后往前找位置
            while(j >= 0 && temp < A[j]){ // 大于待排关键字,后移
                A[j+1] = A[j];
                j--;
            }
            R[j+1] = temp; // 插入位置
        }
    }
折半插入排序
  • 内容:相当于简单插入排序,折半是对找插入位置进行了优化,使用折半查找(因为已排序序列是有序的)。
  • 复杂度:最好O(nlog2n),最坏O(n^2),综合O(n^2),因为移动次数还是那么多,移动次数最少的时候为O(nlog2n)
  • 稳定,适用大多数线性表
  • 代码:

    void InsertSort(int A[], int n){
        for(int i = 1; i < n; i++){
            int temp = A[i]; // 待排关键字
            int low = 0, high = i - 1, mid = 0;
            while(low <= high){
                int mid = low + (high - low)/2;
                if(A[low] < temp)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            // 后移 mid到i-1元素后移
            for(int j = i-1; j > mid; j--)
                A[j+1] = A[j];
            A[mid] = temp; // 插入位置
        }
    }

交换排序

冒泡排序
  • 内容:从后往前,两个指针比较,把小的送到最前面。设置哨兵记录排序完成
  • 复杂度:最坏情况逆序:O(n^2)。比较次数:n(n-1)/2,移动次数:3n(n-1)/2(每次移动三次元素)
  • 稳定性:稳定
  • 其他:每趟排序,都有元素在最终位置
  • 代码:

    void BubSort(int A[], int n){
        for(int i = 0; i < n-1; i++){ // i指的是每轮排好的个数|i个已排好|n-i个未排好|,要遍历n-1次
            int flag = 0;
            for(int j = n-1; j > i; j++){
                if(A[j] < A[j-1]){// 逆序,交换次序
                    int temp = A[j];
                    A[j] = A[j-1];
                    A[j-1] = temp;
                    flag = 1;
                }
                // 从尾到头都没发生交换,证明已经有序
                if(flag == 0)
                    return;
            }
        }
    }
快速排序
  • 内容:找枢纽值,小的丢到左边,大的丢到右边。再递归对左右进行操作
  • 复杂度:递归操作O(logn),分类操作 O(n),故 O(nlogn)
    • 基本有序的序列,退化为冒泡排序
    • 空间复杂度为:借助栈,最好的情况[log2(n-1)]↑(栈深度),最坏O(n-1)(基本有序,n- 1 次递归),所以为O(log2n)
  • 稳定性:不稳定
  • 算法描述:高低指针向中间迫近(符合条件时,低小于枢纽,高大于枢纽)。一方先走,不符合就停下来,等另一方走到不符合。然后交换位置。
  • 代码:

    void QuickSort(int A[], int low, int high){
        if(low < high){
            int privot = Partition(A, low, high); // 划分
            QuickSort(low, pivot-1); // 左右子表递归,记得是low~pivot-1和pivot+1~high,中间是枢纽值。
            QuickSort(pivot+1, high);
        }
    }
void Partition(int A[], low, high){
    int pivot = A[low]; // 放入临时区
    while(low < high){
        // 注意是高指针先移动,才能保证正确交换。因为A[low]放入缓冲区了,所以这个位置可以先放数据
        while(low < high && A[high] >= pivot)
            high--;
        A[low] = A[high];
        while(low < high && A[low] <= pivot)
            low++;
        A[high] = A[low];
    }
    A[low] = pivot; // low后移动的,决定最终位置
    return low;
}

选择排序

简单选择排序

内容:选最小的丢到前面

复杂度:比较次数始终是n(n-1)/2,移动操作不超过3(n-1),最好情况不移动。复杂度:O(n^2)

稳定性:不稳定

代码:

void SelectSort(int A[], int n){
    for(int i = 0; i < n; i++){
        int min = 0; // 最小值的位置
        for(int j = ){
            min =i;
            for(int j = i+1; j < n; j++){ // 更新最小值
                if(A[j]< A[min])
                    min = j;
            }
            // 关键字交换
            int temp = A[min];
            A[min] = A[i];
            A[i] = temp;
        }
    }
}
堆排序
  • 内容:
    • 堆:父节点小于子节点(最小堆)或父节点大于子节点(最大堆)
    • 每次只能取堆顶元素
    • 需要维护堆。添加的时候,新节点放在最尾部(类似完全二叉树),然后交换位置直到满足条件。
  • 复杂度:建堆O(n),总的为 O(nlog2n)
  • 稳定性:不稳定
  • 代码:

    // A[low] 到 A[high] 的范围对low上的节点进行调整
    void Sift(int A[], int low, int high){
        int i = low, j = 2*i; // A[j] 是 A[i] 的左孩子
        int temp = A[i];
        
        while(j <= high){
            // 有孩子较大,j指向右孩子
            if(j < high && A[j] < A[j+1])
                j++;
            if(temp < A[j]){
                A[i] = A[j]; // A[j]调整到双亲位置
                i = j; // 修改i和j的值,以便继续向下
                j = 2*i;
            }else
                break; // 调整结束
        }
        A[i] = temp; // 被调整节点值放入最终位置
    }
    
    void heapSort(int R[], int n){
        int i;
        for(i = n/2; i >= 1; i--)
            Sift(A, i, n);//调整堆
        for(i = n; i >=2; i--){
            // 换出了根节点的关键字,将其放入最终位置
            int temp = A[1];
            A[1] = A[i];
            A[i] = temp;
            Sift(A, 1, i-1); // 在减少了一个关键字的无序序列中进行调整
        }
    }

归并排序

  • 内容:全部分成两个一组,组内排序。再四个一组,组内排序(组内前后两个指针,类似快排向中间逼近)。最后到整个数组。
  • 复杂度:O(nlog2n)log2n趟排序,每趟n次操作。
  • 空间复杂度:O(n),因为需要转存整个待排序列
  • 代码

    void merge(int *a, int low, int mid, int high, int *temp)
    {
        int i = low, j = mid+1;
        int k = 0;
        while(i <= mid && j <= high){
            if(a[i] <= a[j])
                temp[k++] = a[i++];
            else
                temp[k++] = a[j++];        
        }
        // 剩下的没归并进去的,直接复制
        while(i <= mid)
            temp[k++] = a[i++];
        while(j <= high)
            temp[k++] = a[j++];
        
        for(i = 0; i < k; i++)
            a[low+i] = temp[i]; // 复制到A
        
    }
     
    void mergeSort(int *A, int low, int high, int *temp)
    {    
        // 当left==right的时,已经不需要再划分了,出口
        if(low < last)
        {
            int mid = (low + high)>>1;
            mergeSort(A, low, mid, temp); // 左侧子序列递归
            mergeSort(A, mid+1, high, temp); // 右侧子序列递归
            merge(A, low, mid, high, temp); // 归并,A的low~mid, mid+1~high两段有序的归并成一段
        }
    }

树算法

遍历

// 递归先序遍历,visit()位置代表遍历类型
void Order(BTNode *p){
    if(p!=NULL){
        visit(p);
        Order(p->lchild);
        Order(p->rchild);
    }
}

层次遍历

思路:

  • 根节点入队
  • 队不空
    • 队头元素出队
    • 访问当前元素
    • 左右子树只要存在,就入队。先左后右
void LeveOrder(BTNode *root){
    if(!root)
        return;
    
    queue<BTNode*> Q;
    
    Q.push(root); // 根节点入队
    while(!Q.empty()){
        BTNode* q = Q.front();
        // cout<<q->data;
        Q.pop();
        // 左右子树根入队
        if(q->left)
           Q.push(q->left);
        if(q->right)
           Q.push(q->right);
    }
}

求二叉树深度

int getDepth(BTNode *p){
    if(p == NULL)
        return 0;
    else {
        int LD = getDepth(p->lchild);
        int RD = getDepth(p->rchild);
        return (LD>RD ? LD : RD) + 1; // 左右子树深度最大值加1(根节点)
    }
}

判断二叉树是否满

int IsFull(BTNode *bt){
    if(bt){
        // 只有根节点
        if(bt->lchild == NULL && bt->rchild == NULL)
            return 1;
        else if(bt->lchild == NULL || bt->rchild == NULL) // 左为空或右为空,单支
            return 0;
        else
            return (IsFull(bt->lchild) && IsFull(bt->rchild)) // 递归遍历左右子树
    }
}

判断二叉树是否平衡

int getDepth(BTNode *bt){
    if(bt == NULL)
        return 0;
    else {
        int LD = getDepth(bt->lchild);
        int RD = getDepth(bt->rchild);
        return (LD>RD ? LD:RD) + 1;
    }
}

int AVL(BTNode *bt){
    if(bt == NULL)
        return 1;
    int ld = getDepth(bt->lchild);
    int rd = getDepth(bt->rchild);
    
    int gap = ld - rd;
    if(gap<-1 || gap>1)
        return 0
    else
        return AVL(p->lchild) && AVL(p->rchild); 左右子树均返回1才能return,先左子树后右子树。
}

判断二叉树是不是二叉排序树

// 二叉排序树中序遍历有序
long last = LONG_MIN; // 父节值
bool flag = true; // 父结点是否大于子节点
bool IsBSTree(TreeNode* root){
    if(!root)
        return true;
    
    // 遍历左子树
    if(flag && root->left)
        IsBSTree(root->left);
    
    // 做判断
    // 当前节点小于等于上一个节点,不是二叉排序树
    if(root->val <= last)
        flag = false;
    last = root->data; // 记录父节点值
    
    //遍历右子树
    if(root->rchild && flag != 0)
        IsBSTree(root->right);
    
    // 树都遍历完 或 不是二叉排序树,就退出
    return flag;
}

判断两棵树是否相等

bool isSameTree(TreeNode* p, TreeNode* q){
    if(!p && q)
        return false;
    if(!q && p)
        return false;
    if(!p && !q)
        return true;
    
    if(p->val == q->val)
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    return false;
}

图算法

深度优先遍历

  • 代码:

    int visited[maxSize];
    // v是起始节点
    // 
    void DFSTraverse(Graph* G, int v){
        Graph* p;
        visit[v] = 1; // 标记已访问
        Visit(v); // 访问顶点
        p = g->adjlist[v].firstarc; // p指向顶点v的第一条边
        while(p != NULL){
            if(visit[p->adjvex] == 0) // 若访问的顶点未访问,递归访问它
                DFS(G, p->adjvex);
            p = p->nextarc; // p指向下一条边的终点
        }
    }

本文链接:https://ariser.cn/index.php/archives/348/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!