数据结构
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
tanknee 56b11c41bf 测试结束 8 months ago
.vscode 稍微调整了一下,但是如果顺串过多还是会出错 8 months ago
SortSource 测试结束 8 months ago
.gitignore tt 8 months ago
AVLTree.c 使用了邻接表的方式完成了图的拓扑排序 8 months ago
BucketSort.c 桶排,快排,合并排序 8 months ago
CFileTest.c change repo 8 months ago
DFS.c change repo 8 months ago
DataStructDesign.cbp initial commit 8 months ago
DataStructDesign.layout 完成了AVL树的插入 8 months ago
Dijkstra.c Dijkstra的C语言实现 8 months ago
DiskMergeSort.c 基本完成外部排序,但是数据量较大的时候会跑不出来 8 months ago
Fibnacci_DP.c fibnacci数列动态规划实现 8 months ago
Huffman.c 测试 8 months ago
InsertSort.c 实现了C语言的插入排序和希尔排序。 8 months ago
MaxSubsequenceSum.c 求数组中的子序列和的最大值 8 months ago
MergeSort.c 桶排,快排,合并排序 8 months ago
MinEditDistance.c 有向图的DFS深度优先遍历 8 months ago
QuickSort.c 桶排,快排,合并排序 8 months ago
README.md upload readme 8 months ago
RandomCreate.c 测试结束 8 months ago
ShellSort.c 桶排,快排,合并排序 8 months ago
TopologicalSort.c 实现了C语言的插入排序和希尔排序。 8 months ago
TopologicalSort_mine.c 使用了邻接表的方式完成了图的拓扑排序 8 months ago
file.txt change repo 8 months ago
main.exe 完成了AVL树的插入 8 months ago

README.md

数据结构复习

11.28考试 10题-100分 [TOC]

算法分析

运行时间的计算分析

上界:$O(f(N))$

下界:$Ω(g(N))$

准确表达则为:$Θ(h(N))$

也就是说都是一个关于N的函数!

这么做的目的是为了比较两个算法的相对增长速率

求解算法时间复杂度的步骤

  1. 找出算法中的基本语句;

  算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。

  1. 计算基本语句的执行次数的数量级;

  只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。

  1. 用大Ο记号表示算法的时间性能。

  将基本语句执行次数的数量级放入大Ο记号中。

  1. 可以忽略末尾带上的常数项
// 求数组中的子序列的和的最大值
int MaxSubsequenceSum(const int A[],int N){
    int maxSum = 0;
    int tempSum = 0;
    for(int i = 0;i < N;i++){
        tempSum += A[i];
        if(tempSum > maxSum){
            maxSum = tempSum;
        }else if(tempSum < 0){
            tempSum = 0;
        }
    }
    return maxSum;
}

复杂度函数的运算规则

抽象数据类型ADT

表分为两种,顺序表与链表。其中顺序表要求系统给其分配的内存单元是连续的,因此,顺序表的访问时间可以做到线性时间,第二种是链表,链表不要求连续的内存空间,但其中的每一块都是与其他链表节点耦合的。

顺序表

即数组,内存地址连续。

访问时为线性访问,速度较快。插入删除时代价较大,因为需要更改其后所有元素的信息才能维持当前的顺序表。

链表

在C语言中是通过建立结构体然后存储指针的方式来进行访问的。

// 邻接表中表的顶点
typedef struct _VNode
{
    int index;          // 顶点信息
    ENode *firstEdge; // 指向第一条依附该顶点的弧
} VNode;

// 邻接表
typedef struct _LGraph
{
    int vexNum; // 图的顶点的数目
    int edgNum; // 图的边的数目
    VNode vexs[MAX];
} LGraph;

代码片段

循环链表
双向链表
双向循环链表

特点:先进后出FILO

只需要一个指针就可以利用链表来实现栈的数据结构,在栈中只有栈顶可以出入数据,栈底的数据只有等其他数据都出去了才能被弹出

两个栈操作:PUSH POP

实例:使用栈数据结构来实现后缀表达式

队列

特点:先进先出FIFO

对于队列而言,有两个口可以与外界交换数据,分别是队列头和队列尾部。

只允许在队列尾部入队,在队列头部出队。

两个操作:Enqueue Dequeue

二叉树

二叉查找树

之前写的二叉树博客

本地

AVL树

AVL树是带有平衡条件的二叉查找树。

平衡条件必须要相对容易保持,而且必须保证树的深度是$O(logN)$,那么在AVL树中,就是保证节点的左右子树的高度之差小于2,即只能为1或者0 。

下面是AVL树插入的C语言实现

#include <stdio.h>
#include <stdlib.h>
#define MAX(a,b) (a > b) ? (a) : (b)
/**
 * AVL树的结构体定义
 * */
typedef struct AVLTreeNode
{   
    int data;   //节点存储的值
    int height; //当前节点的高度
    struct AVLTreeNode *leftChild;  //左儿子
    struct AVLTreeNode *rightChild; //右儿子
}Node,*AVLTree;
/***
 * @param data 存储的数据
 * @param left 左儿子
 * @param right 右儿子
 * */
static Node *createAVLTreeNode(int data,Node *left,Node *right){
    // 为这个新的节点开辟内存空间
    Node *node;
    if (((node = (Node *)malloc(sizeof(Node))) == NULL)){
        return NULL;
    }
    // 为这个node赋初值
    node->data = data;
    // 空子树的高度为0
    node->height = 0;
    node->leftChild = left;
    node->rightChild = right;

    return node;
}
// 获取节点的高度
int getHeightOfNode(Node *node){
    return (node==NULL) ? 0 : node->height;
}
/*
 * LL:左左对应的情况(左单旋转)。
 *
 * 返回值:旋转后的根节点
 */
static Node* leftLeftRotation(AVLTree k2){
    AVLTree k1;

    k1 = k2->leftChild;
    // k2与k1的右子树进行互换
    k2->leftChild = k1->rightChild;
    k1->rightChild = k2;

    k2->height = MAX( getHeightOfNode(k2->leftChild), getHeightOfNode(k2->rightChild)) + 1;
    k1->height = MAX( getHeightOfNode(k1->leftChild), k2->height) + 1;
    // 旋转完成之后的根节点是k1,即k1上浮了而原本的k2下沉为k1的儿子了
    return k1;
}
/*
 * RR:右右对应的情况(右单旋转)。
 *
 * 返回值:旋转后的根节点
 */
static Node* rightRightRotation(AVLTree k2){
    AVLTree k1;

    k1 = k2->rightChild;
    // k2与k1的右子树进行互换
    k2->rightChild = k1->leftChild;
    k1->leftChild = k2;

    k2->height = MAX( getHeightOfNode(k2->leftChild), getHeightOfNode(k2->rightChild)) + 1;
    //此时的k2为k1的左儿子,所以只需要比较k2和k1的右儿子的高度就好了
    k1->height = MAX( getHeightOfNode(k1->rightChild), k2->height) + 1;
    // 旋转完成之后的根节点是k1,即k1上浮了而原本的k2下沉为k1的儿子了
    return k1;
}
/**
 * 
 * LR
 * 相当于进行了一次RR旋转一次LL旋转。
 * */
static Node *leftRightRotation(Node *k3){
    //先对k3的左子树进行RR旋转,再对旋转后的k3进行LL旋转
    k3->leftChild = rightRightRotation(k3->leftChild);
    return leftLeftRotation(k3);
}
/**
 * 
 * RL
 * 相当于进行了一次LL旋转一次RR旋转。
 * */
static Node *rightLeftRotation(Node *k3){
    //先对k3的右子树进行LL旋转,再对旋转后的k3进行RR旋转
    k3->rightChild = leftLeftRotation(k3->rightChild);
    return rightRightRotation(k3);
}
/**
 * 传入要插入的树
 * 传入要插入的数据
 * 返回更新后的树的根节点
 * */
Node *insertIntoAVLTree(AVLTree tree,int data){
    // 如果树是一个空树
    if (tree == NULL){
        // 那么就建立一个空节点
        tree = createAVLTreeNode(data,NULL,NULL);
        // 如果创建失败的话
        if (tree == NULL){
            printf("Create Node Failed");
        }
        
    }
    if (data < tree->data)//如果要插入的数值比根节点的值要小,那么就插入到其左子树中
    {
        // 然后递归调用插入方法,直到找到一个空节点再插入!
        tree->leftChild = insertIntoAVLTree(tree->leftChild,data);
        // 由于是插入到左子树中,因此只可能是左子树的高度大于右子树的高度
        if (getHeightOfNode(tree->leftChild) - getHeightOfNode(tree->rightChild) == 2)
        {
            // 如果需要插入的值根节点的左子树还要小那么说明插入到了左子树的左侧,那就可以判断此时的不平衡状态为左左LL,调用LL旋转即可
            if (data < tree->leftChild->data)
            {
                tree->leftChild = leftLeftRotation(tree->leftChild);
            }else   // 否则就说明大于这个节点的值,插入到在左子树的右儿子上,调用LR旋转
            {
                tree->leftChild = leftRightRotation(tree->leftChild);
            }
        }
    }
    else if (data > tree->data)
    {//如果要插入的数值比根节点的值要大,那么就插入到其由子树中
        tree->rightChild = insertIntoAVLTree(tree->rightChild,data);
        if (getHeightOfNode(tree->rightChild) - getHeightOfNode(tree->leftChild) == 2)// 由于插入到右子树中那么就是只有可能右子树的高度大于左子树的高度
        {
            if (data > tree->rightChild->data)
            {
                tree->rightChild = rightRightRotation(tree->rightChild);
            }else
            {
                tree->rightChild = rightLeftRotation(tree->rightChild);
            }
        }
    }else
    {
        printf("Don't Insert The Same Node");
    }
    // 更新根节点的高度
    if (((MAX(getHeightOfNode(tree->leftChild),getHeightOfNode(tree->rightChild))) == 0) && (tree->leftChild != NULL || tree->rightChild != NULL))
    {
        // 其子节点全部都是叶子节点
        // 说明两个子树至少存在一个,那么这个根节点的高度就是1
        tree->height = 1;
    }else if (tree->leftChild == NULL && tree->rightChild == NULL)
    {
        // 如果两个子树都不存在那么说明这个节点就是叶子节点,直接返回就好
        return tree;
    }else
    {
        tree->height = (MAX(getHeightOfNode(tree->leftChild),getHeightOfNode(tree->rightChild))) + 1;
    }
    
    return tree;
}

int main()
{
    Node *root = createAVLTreeNode(10,NULL,NULL);
    Node *left = createAVLTreeNode(6,NULL,NULL);
    Node *right = createAVLTreeNode(13,NULL,NULL);
    root->leftChild = left;
    root->rightChild = right;
    root = insertIntoAVLTree(root,5);
    // 此时接着插入值为3的节点就会破坏AVL树的平衡条件
    root = insertIntoAVLTree(root,3);
    printf("Hello world!\n");
    return 0;
}

伸展树

B-树

B-树是为了磁盘存储而设计的一种多叉树,是多叉平衡查找树

用阶数来定义B-树:

B 树又叫平衡多路查找树。一棵m阶的B 树具有以下性质:

  1. 每个节点的子节点个数为 $$ M/2 ≤ N ≤ M $$

  2. 并且B树的全部叶子节点在同一高度上

  3. 根节点至少有两个子树

  4. 由$N$ 个子树的节点一定含有$N-1$个关键字

  5. Ki (i=1...n)为关键字,且关键字按顺序升序排序K(i-1)< Ki

  6. Pi为指向子树根的接点,且指针P(i-1)指向子树中所有结点的关键字均小于Ki,但都大于K(i-1)。--指针域的定义

树的遍历

先序遍历,后序遍历。其中的前/后都是儿子节点相对于父节点而言的!

  • 先序遍历:对根节点的处理在儿子节点的处理之前
  • 后序遍历:对儿子节点的处理在根节点的处理之前
  • 中序遍历:先遍历左子树在遍历根节点最后遍历右子树。可以生成自然的中缀表达式

树中很重要的一个思想就是递归,因为树,树的子节点,等等结构都是相似的,因此同一种规律/算法就可以不断的反复套用。在遍历,插入,增删查改中都会用到递归的思想。

散列

散列的定义

散列表的实现被称为散列(Hashing)

散列是一种以常熟平均时间执行插入删除查找的技术。但是散列表中的元素之间的排列顺序是随机的,因此是无法通过线性时间来打印散列表

散列函数:其作用就是将关键字尽可能合适的映射到不同的存储单元中去。

但是毫无疑问,由于存储单元的数目是有限的而关键字的个数是无穷的,在后期的散列分配映射过程中肯定会遇到冲突现象,因此需要解决冲突。

当关键字是整数时,可以通过对单元个数取模来实现散列函数的确定,但是如果散列表的大小为10,而关键字多是以0结尾,那么这种情况下散列分配的结果就不够理想,因此,在设计散列表的大小时应该尽量采用素数大小!

解决散列冲突问题

如果当一个元素被插入时另一个元素已经存在,即两个元素的散列值相同,那么就会产生一个冲突!

分离链接法

分离链接法的做法是将散列到同一个散列值的所有元素都保留到一个表中,并且这些表都有表头,如果空间较为局促,那也可以不使用表头

填装因子$λ$为散列表中的元素个数与散列表大小的比值

  • 装填因子Load factor $λ$=元素个数/哈希表的大小=链表的平均长度
  • 输入规模的大小不用N,而用λ
  1. 平均情况分析(λ=O(1),O(1))
    • 不成功的查找: λ 次比较( 1+λ
    • 成功查找:1+λ/2( 1+λ
    • 插入:1+λ
    • 删除:1+λ/2( 1+λ
  2. 最坏情况分析(λ=O(N),所有元素哈希到同一链表,O(N))
    • 不成功的查找
    • 成功查找
    • 插入
    • 删除

分离链接法的一般法则是使得表的大小尽量与预料的元素个数差不多,即尽量让$λ≈1$,是表的大小尽量是一个素数,且各个冲突处理链表尽可能短。

缺点是分离链接法浪费了大量时间在分配内存空间上。

开放定址法

在开放定址法中,不使用指针,而是用了另一种方式,它在遇到冲突时,选择在散列表中寻找其他没有被使用的单元,直到选中了空单元才停止。 $$ h_i(X) = (Hash(X)+F(i)) \mod TableSize $$ 因此开放定址法的空间需求相对分离链接法要更大一般而言$λ≤0.5$。

线性探测法

在线性探测法中,函数F是i的线性函数,即F的最高次数为1次,典型情况为 $$ F(i) = i $$ 这相当于逐个探测每个散列表单元,并且必要时可以返回循环遍历整个散列表直到查到一个可用的空单元。

容易看出,如果插入的关键字的散列结果较为接近,那么就会出现一次聚集现象。

如果表有超过一半可以被使用的话,那么线性探测法就是一个较好的办法,然而如果$λ = 0.5$,那么平均插入操作只需要探测2.5次,而对于成功的操作只需要探测1.5次。因此我们在使用线性探测法使应该尽量使填充因子小于0.5!

平方探测法

该方式是消除线性探测法中一次聚集问题的冲突解决办法。平方探测法的冲突函数是二次函数,其较为主流的选择为 $$ F(i) = i^2 $$

规律:使用平方探测法,当表有一半是空的时,并且表的大小为素数,那么我们总能保证此时可以插入一个新的元素。

在开放定址散列表中,标准的删除操作是无法施行的,因为相应的单元可能已经发生了冲突,其元素已经被挪到了其他位置上了。

优先队列-堆

二叉堆

排序

插入排序

void insertSort(int A[],int length){
    // 插入排序的主要思想是排过序的前一部分是永远有序的,只需要将当前元素放置到正确位置就好
    int temp = 0;
    int j = 0;
    for (int i = 1; i < length; i++)//可以选择直接从第一个元素开始
    {
        temp = A[i];
        for (j = i; j > 0 && A[j-1] > temp; j--)// 第一个j=i的元素是还没有被排序的待排元素!所以要从第i-1个元素开始排序
        {
            A[j] = A[j-1];
        }
        // 退出上一个循环的原因要么是找到了该放的正确位置,要么是到了数组的第一位。
        // 但是不管是那种情况,此时j就是正确位置的下标!
        A[j] = temp;
    }
}

希尔排序

void shellSort(int A[],int length){
    // int A[5] = {7,6,5,9,3};
    int temp = 0;
    int j = 0;
    for (int increment = length/2; increment > 0; increment /= 2)
    {
        for (int i = increment; i < length; i++)
        {
            temp = A[i];
            // 从下标为increment 的元素开始,由于每次的间隔已知,且开头已知,那么由后向前找较为的方便
            // 确保每个元素在这个增量间隔序列中的位置是正确的!
            for (j = i; j >= increment; j -= increment)
            {
                if (temp < A[j - increment])
                {
                    A[j] = A[j - increment];
                }else
                {
                    break;
                }
            }
            A[j] = temp;
        }
    }
}

堆排序

public static void main(String[] args) {
        int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
		System.out.println("排序之前:");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
 
		// 堆排序
		heapSort(arr);
 
		System.out.println();
		System.out.println("排序之后:");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
    }
    public static void heapSort(int[] arr) {
        // Create a big top heap
        for (int i = arr.length/2; i >=0; i--) {
            heapAdjust(arr, i, arr.length);
        }
        // 将堆顶最大的那个元素和后面的元素进行交换,然后再生成大顶堆
        for (int i = arr.length-1; i >= 0; i--) {
            // 交换堆顶和队列中最后一个元素的值
            exchange(arr, 0, i);
            // 判断这个队列是否能构成大顶堆不能的话就调整
            // 这里调整的实质是:只有堆顶一个元素需要调整,因此只需要将堆顶的元素下沉到相应的位置就好了不需要调整太多元素!!
            heapAdjust(arr, 0, i);
        }
    }
    public static void heapAdjust(int[] arr,int root,int length) {
        // 以 root节点为根节点,遍历这个长度为length的子树,判断其是否满足大顶堆的要求
        int child;  // 子节点的值
        int father; // 父节点的值
        for(father = arr[root];2*root+1 < length;root = child){
            child = 2*root+1; // 以root节点为根节点的左子树的下标

            // 如果这个根节点的左子树不是这个堆的最后一个元素并且左子树小于右子树。那么就把下标指向右子树
            // 因为小的元素要下沉就必须要跟两个子树中较大的那个进行交换,否则如果跟较小的节点进行交换的话可能还需要交换两次!
            if (child != length-1 && arr[child] < arr[child+1]) {
                child++;
            }
            // 如果此时的父节点小于子树中的那个较大者,就与之交换!
            if (father < arr[child]) {
                arr[root] = arr[child]; // 父节点的原有值已经记录在father这个变量内了!
            }else{
                // 说明该节点符合大顶堆的标准,退出for循环
                break;
            }
        }
        // 由于当前下表为root的节点值可能是废弃的,即已经被交换过,所以这个节点位置的应有值是该移动节点的值,即最初始的父节点
        arr[root] = father;
    }
    public static void exchange(int[] arr,int began,int end) {
        int temp = arr[began];
        arr[began] = arr[end];
        arr[end] = temp;
    }

归并排序

#include<stdio.h>
#define Max_ 10
 
// 归并排序中的合并算法
void Merge(int array[], int left, int m, int right)
{
    int aux[Max_] = {0};  // 临时数组 (若不使用临时数组,将两个有序数组合并为一个有序数组比较麻烦)
    int i; //第一个数组索引
    int j; //第二个数组索引
    int k; //临时数组索引
    
    for (i = left, j = m+1, k = 0; k <= right-left; k++) // 分别将 i, j, k 指向各自数组的首部。
    {
        //若 i 到达第一个数组的尾部,将第二个数组余下元素复制到 临时数组中
        if (i == m+1)
        {
            aux[k] = array[j++];
            continue;
        }
        //若 j 到达第二个数组的尾部,将第一个数组余下元素复制到 临时数组中
        if (j == right+1)
        {
            aux[k] = array[i++];
            continue;
        }
        //如果第一个数组的当前元素 比 第二个数组的当前元素小,将 第一个数组的当前元素复制到 临时数组中
        if (array[i] < array[j])
        {
            aux[k] = array[i++];
        }
        //如果第二个数组的当前元素 比 第一个数组的当前元素小,将 第二个数组的当前元素复制到 临时数组中
        else
        {
            aux[k] = array[j++];
        }
    }
    
    //将有序的临时数组 元素 刷回 被排序的数组 array 中,
    //i = left , 被排序的数组array 的起始位置
    //j = 0, 临时数组的起始位置
    for (i = left, j = 0; i <= right; i++, j++)
    {
        array[i] = aux[j];
    }
}
 
// 归并排序
void MergeSort(int array[], int start, int end)
{
    // 先拆分,直到拆分到最小部分才结束,也就是只剩下一个元素的时候开始递归返回
    // 排序是在合并的时候发生的,通过下标来控制拆分后的元素位置,然后将需要排序的元素输出到临时数组中,最后重新覆盖原始数组中的元素列
    if (start < end)
    {
        int i;
        i = (end + start) / 2;
        // 对前半部分进行排序
        MergeSort(array, start, i);
        // 对后半部分进行排序
        MergeSort(array, i + 1, end);
        // 合并前后两部分
        Merge(array, start, i, end);
    }
}
 
int main()
{   //测试数据
    int arr_test[Max_] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };
    MergeSort( arr_test, 0, Max_-1 );
    return 0;
}

快速排序

快排的核心思想就是哨兵,通过两个pivot来实现将所给的数组中的所有元素排序(大致排序,只按照与标兵的大小比较),最后哨兵会和的时候就是标兵元素的正确存放地址,此时左边为小于标兵的元素,右边是大于标兵的元素。

#include <stdio.h>
#include <stdlib.h>
/*****************************************************
File name:Quicksort
Author:Zhengqijun    Version:1.0    Date: 2016/11/04
Description: 对数组进行快速排序
Funcion List: 实现快速排序算法
*****************************************************/

#define BUF_SIZE 12

/**************************************************
 *函数名:display
 *作用:打印数组元素
 *参数:array - 打印的数组,maxlen - 数组元素个数
 *返回值:无
 **************************************************/
void display(int array[], int maxlen)
{
    int i;

    for (i = 0; i < maxlen; i++)
    {
        printf("%-3d", array[i]);
    }
    printf("\n");

    return;
}

/************************************
 *函数名:QuickSort
 *作用:快速排序算法
 *参数:
 *返回值:无
 ************************************/
void QuickSort(int *arr, int low, int high)
{
    if (low < high)
    {
        int i = low;
        int j = high;
        int k = arr[low];
        while (i < j)
        {
            // 此时的K就是这次快速排序的基准值
            // 通过不断地左右探测,找到大于k的放在右边,小于k的放在左边。
            // 每次只找到第一个大于或者小于k的数,然后直接交换,再去寻找另一边的元素
            while (i < j && arr[j] >= k) // 从右向左找第一个小于k的数
            {
                j--;
            }

            if (i < j)// 确保上面的循环是因为arr[i] < k而退出的也就是找到了第一个小于k的数
            {
                arr[i++] = arr[j];//然后把这个数放入到arr[i]中
            }

            while (i < j && arr[i] < k) // 从左向右找第一个大于等于k的数
            {
                i++;
            }

            if (i < j)
            {
                arr[j--] = arr[i];
            }
        }// 当i == j时就是k应该放的位置。
        // 此时左边全部都是小于k的元素,因为所有大于k的元素都被交换到当时k所在的位置了,所有大于k的元素都被放到右侧了

        arr[i] = k;

        // 递归调用
        QuickSort(arr, low, i );  // 排序k左边。排序当前数组的最低位到i位
        QuickSort(arr, i + 1, high); // 排序k右边,排序当前数组i之后的所有元素
    }
}

// 主函数
int main()
{
    int array[BUF_SIZE] = {1,5,2,4,3,4564,2345,11,23,3423,4352,0};
    int maxlen = BUF_SIZE;

    printf("排序前的数组\n");
    display(array, maxlen);

    QuickSort(array, 0, maxlen - 1); // 快速排序

    printf("排序后的数组\n");
    display(array, maxlen);

    return 0;
}

桶式排序

桶排的原理就是归类!基数排序也是类似的原理。直接将元素放入到以该元素的数值为下标的数组单元中,不过实际操作时数组单元记录的是相同大小元素的个数!而在打印的时候只需要将数组下标打印数组元素值次就好了。

Java实现

/**
     * 桶排序
     * 
     * @param A
     * @return
     */
    public static int[] bucketSort(int[] A, int max) {
        int[] B = new int[max + 1];// 0-max 总共max+1个数
        int[] reArray = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            B[A[i]]++;
        }
        int k = 0;
        for (int i = 0; i < B.length; i++) {
            for (int j = 1; j <= B[i]; j++) {
                // i 是被排序的数的大小 B[i] 是大小为i的被排序数的个数
                reArray[k] = i;
                k++;
            }
        }
        return reArray;
    }

C语言实现:

void bucketSort(int A[],int length,int max){
    int B[max+1];// 根据A中元素的最大值来确定B的元素个数
    memset(B,0,(max+1)*sizeof(int));//使用memset时记得引用string.h头文件
    for(int i = 0; i < length;i++){
        B[A[i]]++;
    }
    int k = 0;
   for (int i = 0; i < max+1; i++) {
        for (int j = 1; j <= B[i]; j++) {
            // i 是被排序的数的大小 B[i] 是大小为i的被排序数的个数
            A[k] = i;
            k++;
        }
    }
}

外部排序

图论算法

图的定义

拓扑排序

最小生成树

Prim算法

求图的最小生成树

Dijkstra算法

求两个顶点间的最短路径,是一种贪婪算法

算法设计技巧

贪婪算法

分治算法