Skip to content

Latest commit

 

History

History
1116 lines (960 loc) · 24.9 KB

9.模板.md

File metadata and controls

1116 lines (960 loc) · 24.9 KB
Raw

0 常用STL API

1.vector

push_back()
size()
clear()
at()
front()
back()
pop_back()

2.map & set

map:
empty()
find()!=ma.end()

set:
insert()

3.queue & stack

queue:

push()
front()
pop()


stack():

push()
top()
pop()

4.priority_queue

qu.top();
qu.pop();

5.stl排序

lamda:

    vector<node> qu;
    qu.push_back(node(5,3));
    qu.push_back(node(4,6));
    sort(qu.begin(),qu.end(),[](node &x,node &y){ return x.i<y.i;});
    for(auto k:qu){
        cout<<k.i<<" "<<k.j<<endl;
    }

一 树论模板

1.搜索树

typedef int ElementType;
typedef struct TreeNode *BinTree;
struct TreeNode{
	ElementType Data;
	BinTree Left;
	BinTree Right;
};

// 查找递归实现 
BinTree Find(ElementType X,BinTree BST){
	if(!BST)  // 如果根结点为空，返回 NULL 
		return NULL; 
	if(X < BST->Data) // 比根结点小，去左子树查找 
		return Find(X,BST->Left); 
	else if(BST->Data < X)  // 比根结点大，去右子树查找 
		return Find(X,BST->Right);
	else if(BST->Data == X) // 找到了 
		return BST;
}

// 查找非递归实现
BinTree IterFind(ElementType X,BinTree BST){
	while(BST){
		if(X < BST->Data)
			BST = BST->Left;
		else if(BST->Data < X)  // 比根结点大，去右子树查找 
			BST = BST->Right;
		else if(BST->Data == X) // 找到了 
			return BST;
	}
	return NULL;
} 

// 查找最小值的递归实现
BinTree FindMin(BinTree BST){
	if(!BST)    // 如果为空了，返回 NULL 
		return NULL;  
	else if(BST->Left)   // 还存在左子树，沿左分支继续查找 
		return FindMin(BST->Left);
	else  // 找到了 
		return BST;
} 

// 查找最大值的非递归实现
BinTree FindMax(BinTree BST){
	if(BST)  // 如果不空 
		while(BST->Right)   // 只要右子树还存在 
			BST = BST->Right;
	return BST;
} 

// 插入
BinTree Insert(ElementType X,BinTree BST){
	if(!BST){  // 如果为空，初始化该结点 
		BST = (BinTree)malloc(sizeof(struct TreeNode));
		BST->Data = X;
		BST->Left = NULL;
		BST->Right = NULL;
	}else{ // 不为空 
		if(X < BST->Data)  // 如果小，挂在左边 
			BST->Left = Insert(X,BST->Left);
		else if(BST->Data < X)  // 如果大，挂在右边 
			BST->Right = Insert(X,BST->Right);
		// 如果相等，什么都不用做 
	}
	return BST;
} 

// 删除
BinTree Delete(ElementType X,BinTree BST){
	BinTree tmp;
	if(!BST)
		cout<<"要删除的元素未找到";
	else if(X < BST->Data)   // X 比当前结点值小，在左子树继续查找删除 
		BST->Left = Delete(X,BST->Left);
	else if(BST->Data < X)   // X 比当前结点值大，在右子树继续查找删除 
		BST->Right = Delete(X,BST->Right);
	else{  //  找到被删除结点 
		if(BST->Left && BST->Right){  // 被删除结点有俩孩子结点 
			tmp = FindMin(BST->Right);   // 找到右子树中值最小的
			BST->Data = tmp->Data;     // 用找到的值覆盖当前结点 
			BST->Right = Delete(tmp->Data,BST->Right);    // 把前面找到的右子树最小值结点删除 
		}else{  // 被删除结点只有一个孩子结点或没有孩子结点 
			tmp = BST;
			if(!BST->Left && !BST->Right)  // 没有孩子结点 
				BST = NULL;
			else if(BST->Left && !BST->Right)  // 只有左孩子结点 
				BST = BST->Left;
			else if(!BST->Left && BST->Right)  // 只有右孩子结点 
				BST = BST->Right;
			free(tmp);
		}
	}
	return BST;
}

2.字典树

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MAX_NODE = 1000000 + 10;
const int CHARSET = 26;
int trie[MAX_NODE][CHARSET] = {0};
int color[MAX_NODE] = {0};
//代表当前节点个数
int k = 1;

void insert(char *w){
    int len = strlen(w);
    //p代表当前在哪个节点
    int p = 0;
    for(int i=0; i<len; i++){
        int c = w[i] - 'a';
        if(!trie[p][c]){
            trie[p][c] = k;
            k++;
        }
        p = trie[p][c];
    }
    color[p] = 1;
}

int search(char *s){
    int len = strlen(s);
    int p = 0;
    for(int i=0; i<len; i++){
        int c = s[i] - 'a';
        if(!trie[p][c]) return 0;
        p = trie[p][c];
    }
    return color[p] == 1;
}

int main(){
    int t,q;
    char s[20];
    scanf("%d%d", &t,&q);
    while(t--){
        scanf("%s", s);
        insert(s);
    }
    while(q--){
        scanf("%s", s);
        if(search(s)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

3.AVL平衡二叉树

#include<iostream>
#include<malloc.h>
typedef struct AVLNode *AVLTree;
struct AVLNode{
	int data;     // 存值 
	AVLTree left;  // 左子树 
	AVLTree right;  // 右子树 
	int height;  // 树高 
};
using namespace std;

// 返回最大值 
int Max(int a,int b){
	return a>b?a:b;
}

// 返回树高，空树返回 -1 
int getHeight(AVLTree A){
	return A==NULL?-1:A->height;
}

// LL单旋
// 把 B 的右子树腾出来挂给 A 的左子树，再将 A 挂到 B 的右子树上去 
AVLTree LLRotation(AVLTree A){
	// 此时根节点是 A 
	AVLTree B = A->left;  // B 为 A 的左子树  
	A->left = B->right;   // B 的右子树挂在 A 的左子树上 
	B->right = A;     //  A 挂在 B 的右子树上 
	A->height = Max(getHeight(A->left),getHeight(A->right)) + 1;
	B->height = Max(getHeight(B->left),A->height) + 1;
	return B;  // 此时 B 为根结点了 
}

// RR单旋
AVLTree RRRotation(AVLTree A){
	// 此时根节点是 A 
	AVLTree B = A->right;
	A->right = B->left;
	B->left = A;
	A->height = Max(getHeight(A->left),getHeight(A->right)) + 1;
	B->height = Max(getHeight(B->left),A->height) + 1;
	return B;  // 此时 B 为根结点了 
}

// LR双旋 
AVLTree LRRotation(AVLTree A){
	// 先 RR 单旋
	A->left = RRRotation(A->left);
	// 再 LL 单旋 
	return LLRotation(A);
}

// RL双旋
AVLTree RLRotation(AVLTree A){
	// 先 LL 单旋
	A->right = LLRotation(A->right);
	// 再 RR 单旋 
	return RRRotation(A); 
}

AVLTree Insert(AVLTree T,int x){
	if(!T){  // 如果该结点为空，初始化结点 
		T = (AVLTree)malloc(sizeof(struct AVLNode));
		T->data = x;
		T->left = NULL;
		T->right = NULL;
		T->height = 0;
	}else{  // 否则不为空， 
		if(x < T->data){  // 左子树 
			T->left = Insert(T->left,x);
			if(getHeight(T->left)-getHeight(T->right)==2){  // 如果左子树和右子树高度差为 2 
				if(x < T->left->data)  // LL 单旋 
					T = LLRotation(T); 
				else if(T->left->data < x)  // LR双旋
					T = LRRotation(T); 
			}
		}else if(T->data < x){
			T->right = Insert(T->right,x);
			if(getHeight(T->right)-getHeight(T->left)==2){
				if(x < T->right->data)  // RL 双旋 
					T = RLRotation(T); 
				else if(T->right->data < x)  // RR单旋
					T = RRRotation(T); 
			}
		}
	}
	//更新树高 
	T->height = Max(getHeight(T->left),getHeight(T->right)) + 1;
	return T;
} 


int main(){
	AVLTree T=NULL;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int tmp;
		cin>>tmp;
		T = Insert(T,tmp);
	}
	cout<<T->data;
	return 0;
}

4.线段树

class NumArray {
public:
    #define ls k<<1   //左子树
    #define rs k<<1|1   //右子树
    vector<int> t;
    vector<int> lazy;
    int n;
    vector<int> nums;
    NumArray(vector<int>& nums) {;
        n=nums.size();
        if(n==0)return;
        t=vector<int>(n*4,0);
        lazy=vector<int>(n*4,0);
        this->nums=nums;
        build(1,0,n-1);
    }

    //push up   ,push up函数是关键,这里是区间和,如果是区间最大值,修改pushUp即可
    void pushUp(int k){
        t[k]=t[ls]+t[rs];
    }
    //递归方式建树
    void build(int k,int l,int r){    //k为当前需要建立的结点，l为当前需要建立区间的左端点，r则为右端点
        if(l == r)    //左端点等于右端点，即为叶子节点，直接赋值即可
            t[k] = nums[l];
        else{
            int m = l + ((r-l)>>1);    //m则为中间点，左儿子的结点区间为[l,m],右儿子的结点区间为[m+1,r]
            build(ls,l,m);    //递归构造左儿子结点
            build(rs,m+1,r);    //递归构造右儿子结点
            pushUp(k);    //更新父节点
        }
    }
    //点更新
    //递归方式更新 update_point(p,v,1,n,1);
    void update_point(int p, int v, int l, int r, int k){    //p为下标，v为要加上的值，l，r为结点区间，k为结点下标
        if(l == r)    //左端点等于右端点，即为叶子结点，直接加上v即可
            t[k] += v;    //线段树数组都得到更新
        else{
            //先删除标记
            pushdown(k);
            int m = l + ((r-l)>>1);    //m则为中间点，左儿子的结点区间为[l,m],右儿子的结点区间为[m+1,r]
            if(p <= m)    //如果需要更新的结点在左子树区间
                update_point(p, v, l, m, ls);
            else    //如果需要更新的结点在右子树区间
                update_point(p, v, m + 1, r, rs);
            pushUp(k);    //更新父节点的值
        }
    }
    //区间更新
    void pushdown(int k){
        if(lazy[k])
        {
            int value=lazy[k];
            t[ls]+=value;
            t[rs]+=value;
            lazy[k]=0;
            lazy[ls]+=value;
            lazy[rs]+=value;
        }
    }
    void update_range(int i,int j,int v,int l,int r,int k)
    {
        if(l>=i&&r<=j)
        {
            t[k]+=v;
            lazy[k]+=v;
        }
        else
        {
            pushdown(k);
            int mid=l+(r-l)/2;
            if(mid>=i)
            {
               update_range(i,j,v,l,mid,ls);
            }
            else if(mid<=j)
            {
                update_range(i,j,v,mid+1,r,rs);
            }
            pushUp(k);
        }
    }
    //区间查询
    int range_sum(int L,int R,int l,int r,int k){    //[L,R]即为要查询的区间，l，r为结点区间，k为结点下标
        if(L <= l && r <= R)    //如果当前结点的区间真包含于要查询的区间内，则返回结点信息且不需要往下递归
            return t[k];
        else{
            pushdown(k);
            int res = 0;    //返回值变量，根据具体线段树查询的什么而自定义
            int m = l + ((r-l)>>1);    //m则为中间点，左儿子的结点区间为[l,m],右儿子的结点区间为[m+1,r]
            if(L <= m)    //如果左子树和需要查询的区间交集非空
                res += range_sum(L,R,l,m,ls);
            if(R > m)    //如果右子树和需要查询的区间交集非空，注意这里不是else if，因为查询区间可能同时和左右区间都有交集
                res += range_sum(L,R,m+1,r,rs);
            return res;    //返回当前结点得到的信息
        }
    }
};

二 图论模板

1.最短路

1.Dijkstra

    int dijkstra(vector<vector<int>>& gh, int N, int K) {
        const int INF = 0x3f3f3f3f;
        typedef pair<int, int> PII; // first:距离; second: 几号点
        vector<bool> vis(N + 1, false); // 是否已得到最短距离
        vector<int> dist(N+1, INF); // 距离起始点的最短距离
        unordered_map<int, vector<PII>> graph; // 邻接表；u->v,权重w
        priority_queue<PII, vector<PII>, greater<PII>> heap; // 小顶堆；维护到起始点的最短距离和点

        for (auto &t: gh){ // 初始化邻接表
            graph[t[0]].push_back({t[2],t[1]});
        }
        
        heap.push({0, K});
        dist[K] = 0;
        while(heap.size()){
            auto t = heap.top();
            heap.pop();
            int ver = t.second, distance = t.first;
            if (vis[ver]) continue; // 之前更新过，是冗余备份
            vis[ver] = true;
            for (auto &p: graph[ver]){
                if (dist[p.second] > distance + p.first){ // 用t去更新其他点到起始点的最短距离
                    dist[p.second] = distance + p.first;
                    heap.push({dist[p.second], p.second});
                }
            }
        }
        int ans = *max_element(dist.begin()+1, dist.end());
        return ans == INF ? -1: ans;
    }

2.floyd

    int floyd(vector<vector<int>>& gh, int N, int K) {
        const int INF = 0x3f3f3f3f;
        vector<vector<int>> dist(N+1,vector<int>(N+1,INF));
        for (int i = 0; i <=N ; ++i) {
            dist[i][i]=0;
        }
        for(auto k:gh){
            dist[k[0]][k[1]]=min(dist[k[0]][k[1]],k[2]);
        }
        for (int k = 1; k <=N ; ++k) {
            for (int i = 1; i <=N ; ++i) {
                for (int j = 1; j <=N ; ++j) {
                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
                }
            }
        }
        int ans=0;
        for (int l = 1; l <=N ; ++l) {
            ans=max(ans,dist[K][l]);
        }
        return ans> INF/2?-1:ans;
    }

2.最小生成树

1.Prim

typedef pair<int,int> ll;
int prim( vector<vector<int>> graph, vector<int> dist,int n){
    priority_queue<ll,vector<ll>,greater<ll>> q;
    vector<bool> vis(n+1, false);
    dist[1]=0;
    int sum=0;
    q.push({dist[1],1});
    while( !q.empty() ){
        int index=q.top().second;
        q.pop();
        if(vis[index])continue;
        #加上这条边
        sum+=dist[index];
        vis[index]= true;
        #对其邻接边,收录
        for (int i = 1; i <=n ; ++i) {
            if(!vis[i] && graph[index][i]<dist[i] ){
                dist[i]=graph[index][i];
                q.push({dist[i],i});
            }
        }
    }
    for (int i = 1; i <= n ; ++i) {
        if(!vis[i])return -1;
    }
    return sum;
}
int main(){
    int n,m;
    cin>>n>>m;
    int inf=10000000;
    vector<int> dist(n+1,inf);
    vector<vector<int>> graph(n+1,vector<int>(n+1,inf));
    int a,b,value;
    for(int i=0;i<m;i++){
        cin>>a>>b>>value;
        graph[a][b]=value;
        graph[b][a]=value;
    }
    cout<<prim(graph,dist,n);
}

2.Kruskal

#include <bits/stdc++.h>
using namespace std;
struct Edge{
    int a,b,w;
    Edge(int a,int b ,int w):a(a),b(b),w(w){}
    bool operator < (Edge o)const{
        return w<o.w;
    }
};
vector<Edge> g;
vector<int> fa;
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int kruskal(int n){
    //对边进行排序
    sort(g.begin(),g.end());
    int ans=0;
    int cnt=n;
    for(Edge e:g){
        int fax= find(e.a);
        int fay= find(e.b);
        if(fax!=fay){
            //计数
            cnt--;
            //合并
            fa[fax]=fay;
            //加上这条边的值
            ans+=e.w;
        }
    }
    return cnt==1?ans:-1;
}
int main(){
    int n,m;
    cin>>n>>m;
    int a,b,value;
    fa=vector<int>(n+1,0);
    for (int i = 1; i <=n ; ++i) {
        fa[i]=i;
    }
    for(int i=0;i<m;i++){
        cin>>a>>b>>value;
        g.push_back(Edge(a,b,value));
    }
    cout<<kruskal(n);
}

3.并查集

class UnionFind{
public:
    int UnionNums;
    int *graph;
    /**
     * find
     */
    int find(int k){
        if(graph[k]==k)return k;
        else return k=find(graph[k]);
    }
    /**
     * union
     */
    void Union(int i,int j){
        int pI=find(i);
        int pK=find(j);
        if(pI!=pK){
            graph[pK]=pI;
            UnionNums--;
        }
    }
    
    //初始化
    UnionFind(int nums){
        UnionNums=nums;
        graph=new int[nums+1];
        for(int i=0;i<=nums;i++){
            graph[i]=i;
        }
    }
};

4.拓扑排序

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
     int len=numCourses;
     int in[len];
     int out[len];
     vector<vector<int>> ve;
     queue<int> q;
     vector<int> v;
     for(int i=0;i<len;i++){
         in[i]=out[i]=0;
         ve.push_back(v);
     }
     
     //构建拓扑序列
     for(int i=0;i<prerequisites.size();i++){
         int l1=prerequisites[i][0];
         int l2=prerequisites[i][1];
         ve[l2].push_back(l1);
         in[l1]++;
     }
     //将入度为0的放入队列
     for(int i=0;i<len;i++){
         if(in[i]==0)q.push(i);
     }
     int cnt=0;
     while(!q.empty()){
         int cur=q.front();
         q.pop();
         cnt++;
         //遍历当前节点的邻接表
         for(int i=0;i<ve[cur].size();i++){
             int c=ve[cur][i];
             in[c]--;
             if(in[c]==0)q.push(ve[cur][i]);
         }
     }
     return cnt==len;
}
};

三 排序模板

1.快排排序

void quick_sort( vector<int> & arr, int start ,int end){
    if ( start<end ){
        int left = start;
        int right = end;
        int pivot= arr[start];
        while (left<right){
            while(left<right&&arr[right]>=pivot)right--;
            arr[left]=arr[right];
            while(left<right&&arr[left]<=pivot)left++;
            arr[right]=arr[left];
        }
        arr[left]=pivot;
        quick_sort( arr , start,left-1);
        quick_sort( arr ,left+1,end);
    }
}

2.归并排序

//归并排序
void merge( vector<int>& arr,int start,int mid,int end){
    vector<int> tempArr(end-start+1,0);
    int left = start;
    int right = mid+1;
    int index=0;
    while( left<=mid && right<=end){
        if( arr[left] <= arr[right] ){
            tempArr[index++]=arr[left++];
        }else if(arr[left]>=arr[right]){
            tempArr[index++]=arr[right++];
        }
    }
    while(left<=mid){
        tempArr[index++]=arr[left++];
    }
    while(right<=end){
        tempArr[index++]=arr[right++];
    }
    index=0;
    while(start<=end){
        arr[start++]=tempArr[index++];
    }
}
void merge_sort( vector<int>& arr,int start,int end){
    if(start<end){
        int mid=start+(end-start)/2;
        merge_sort(arr,start,mid);
        merge_sort(arr,mid+1,end);
        merge(arr,start,mid, end);
    }
}

3.选择排序

void select_sort( vector<int>& arr,int start,int end  ){
    int swap=0;
    for (int i = 0; i <arr.size()-1 ; ++i) {
        int pos= i;
        for(int j=i+1;j<arr.size();j++){
            if( arr[j]<arr[pos] ){
                pos=j;
            }
        }
        swap = arr[pos];
        arr[pos] = arr[i];
        arr[i] = swap;
    }
}

4.堆排序

#include<bits/stdc++.h>
using namespace std;
#define maxdata 100000
struct node{
	int * data;
	int size;
	int capacity;
};
typedef node * tree;
tree create(int maxsize){
	tree h=new node;
	h->data=(int *)malloc(sizeof(int)*(maxsize+1));
	h->size=0;
	h->capacity=maxsize;
	h->data[0]=maxdata;
	return h;
}
void LevelOrderTraversal(tree H){
	int i;
	printf("层序遍历的结果是：");
	for(i = 1;i<=H->size;i++){
		printf("%d ",H->data[i]);
	} 
	printf("\n"); 
} 
void Heapify(tree h,int i){
	int parent,child;
	int data=h->data[i];
	for(parent=i;parent*2<=h->size;parent=child){
		child=parent*2;
		if(child!=h->size){
			if(h->data[child]<h->data[child+1])child++;
		}
		if(h->data[child]<=data)break;
		else h->data[parent]=h->data[child];
	}
	h->data[parent]=data;
}
void adjust(tree h){
	int i=h->size/2;
	for(;i>0;i--){
		Heapify(h,i);//从最拥有子树的最小树开始--完全二叉树的特性,可以自己画个图验证一下
	} 
}
int main(){
	tree h;
	h=create(100);
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>h->data[++h->size];
	}
	adjust(h);
	LevelOrderTraversal(h);
}

5.希尔排序

//4.希尔排序
void shell_sort( vector<int>& arr , int n){
    for( int gap=n/2; gap>0 ;gap/=2){
        for( int i=gap ;i<arr.size();i+=gap){
            int j=i;
            int sentinel= arr[i];
            if( arr[j]<arr[j-gap] ){
                while( j-gap>=0 && arr[j-gap] > sentinel ){
                    arr[j]= arr[j-gap];
                    j-=gap;
                }
                arr[j]= sentinel;
            }
        }
    }
}

6.基数排序

/*
 * 获取数组a中最大值
 *
 * 参数说明：
 *     a -- 数组
 *     n -- 数组长度
 */
int get_max(int a[], int n)
{
    int i, max;

    max = a[0];
    for (i = 1; i < n; i++)
        if (a[i] > max)
            max = a[i];
    return max;
}

/*
 * 对数组按照"某个位数"进行排序(桶排序)
 *
 * 参数说明：
 *     a -- 数组
 *     n -- 数组长度
 *     exp -- 指数。对数组a按照该指数进行排序。
 *
 * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}；
 *    (01) 当exp=1表示按照"个位"对数组a进行排序
 *    (02) 当exp=10表示按照"十位"对数组a进行排序
 *    (03) 当exp=100表示按照"百位"对数组a进行排序
 *    ...
 */
void count_sort(int a[], int n, int exp)
{
    int output[n];             // 存储"被排序数据"的临时数组
    int i, buckets[10] = {0};

    // 将数据出现的次数存储在buckets[]中
    for (i = 0; i < n; i++)
        buckets[ (a[i]/exp)%10 ]++;

    // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
    for (i = 1; i < 10; i++)
        buckets[i] += buckets[i - 1];

    // 将数据存储到临时数组output[]中
    for (i = n - 1; i >= 0; i--)
    {
        output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];
        buckets[ (a[i]/exp)%10 ]--;
    }

    // 将排序好的数据赋值给a[]
    for (i = 0; i < n; i++)
        a[i] = output[i];
}

/*
 * 基数排序
 *
 * 参数说明：
 *     a -- 数组
 *     n -- 数组长度
 */
void radix_sort(int a[], int n)
{
    int exp;    // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
    int max = get_max(a, n);    // 数组a中的最大值

    // 从个位开始，对数组a按"指数"进行排序
    for (exp = 1; max/exp > 0; exp *= 10)
        count_sort(a, n, exp);
}

7.桶排序

public static void bucketSort(int[] arr){
    
    // 计算最大值与最小值
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    
    // 计算桶的数量
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    
    // 将每个元素放入桶
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    
    // 对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
    
    // 将桶中的元素赋值到原序列
	int index = 0;
	for(int i = 0; i < bucketArr.size(); i++){
		for(int j = 0; j < bucketArr.get(i).size(); j++){
			arr[index++] = bucketArr.get(i).get(j);
		}
	}  
}

四 散列表

1.平方探测法

#define MAXTABLESIZE 100000   // 定义允许开辟的最大散列表长度 
typedef int Index;
typedef int ElementType; 
typedef Index Position;
typedef enum{   // 分别对应：有合法元素、空、有已删除元素 
	Legitimate,Empty,Deleted
} EntryType;  // 定义单元状态类型 

typedef struct HashEntry Cell;
struct HashEntry{   //  哈希表存值单元 
	ElementType Data;  // 存放元素
	EntryType Info;  // 单元状态	
};

typedef struct HashTbl *HashTable;
struct HashTbl{  // 哈希表结构体 
	int TableSize;   // 哈希表大小 
	Cell *Cells;   // 哈希表存值单元数组 
};

using namespace std;

int NextPrime(int N);  // 查找素数 
HashTable CreateTable( int TableSize); // 创建哈希表 
Index Hash(int Key,int TableSize);   // 哈希函数 

// 查找素数 
int NextPrime(int N){
	int p = (N%2)?N+2:N+1;  // 从大于 N 的下个奇数开始
	int i;
		
	while(p <= MAXTABLESIZE){
		for(i = (int)sqrt(p);i>2;i--)
			if(!(p%i))  // p 不是素数 
				break;
		if(i==2) 
			break; 
		p += 2;  // 继续试探下个奇数 
	}
	return p;
}

// 创建哈希表 
HashTable CreateTable( int TableSize){
	HashTable H;
	int i;
	H = (HashTable)malloc(sizeof(struct HashTbl));
	// 保证哈希表最大长度是素数 
	H->TableSize = NextPrime(TableSize);
	// 初始化单元数组
	H->Cells = (Cell *)malloc(sizeof(Cell)*H->TableSize);
	// 初始化单元数组状态 
	for(int i=0;i<H->TableSize;i++)
		H->Cells[i].Info = Empty;
	return H;
}

// 平方探测查找 
Position Find(HashTable H,ElementType Key){
	Position CurrentPos,NewPos; 
	int CNum = 0 ;   // 记录冲突次数
	CurrentPos = NewPos = Hash(Key,H->TableSize);
	// 如果当前单元状态不为空，且数值不等，则一直做 
	while(H->Cells[NewPos].Info != Empty && H->Cells[NewPos].Data != Key){
		if(++CNum % 2 ){ // 冲突奇数次发生 
			NewPos = CurrentPos + (CNum+1)/2*(CNum+1)/2;
			// 如果越界，一直减直到再次进入边界 
			while(H->TableSize <= NewPos){
				NewPos -= H->TableSize; 
			}
		}else{  // 冲突偶数次发生 
			NewPos = CurrentPos - CNum/2*CNum/2;
			// 如果越界，一直加直到再次进入边界 
			while(NewPos < 0){
				NewPos += H->TableSize; 
			}
		}
	} 
	return NewPos;
}

// 插入
bool Insert( HashTable H,ElementType Key,int i){
	Position Pos = i;
	Pos = Find(H,Key);
	// 如果单元格状态不是"存在合法元素" 
	if( H->Cells[Pos].Info != Legitimate){
		H->Cells[Pos].Info = Legitimate;
		H->Cells[Pos].Data = Key;
	}
	return true;
} 

// 除留余数法哈希函数 
Index Hash(int Key,int TableSize){
	return Key % TableSize;
}