XIAOSUO 记录个人学习的足迹

摘要：　　通常有两类方法处理冲突：开放定址(Open Addressing)法和拉链(Chaining)法。前者是将所有结点均存放在散列表T[0..m-1]中；后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表T[0..m-1]中。 一、开放定址法 （1）开放地址法解决冲突的方法 　用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(... 阅读全文

摘要：一、散列函数的选择有两条标准：简单和均匀。 　简单指散列函数的计算简单快速； 　均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集K随机均匀地分布在表的地址集{0，1，…，m-1}上，以使冲突最小化。 二、常用散列函数 　为简单起见，假定关键字是定义在自然数集合上。 （1）平方取中法 　具体方法：先通过求关键字的平方值扩大相近数的... 阅读全文

摘要：一、散列表 　设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K（|K|比|U|小得多）。 　散列方法是使用函数h将U映射到表T[0..m-1]的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。 其中： 　 ① h：U→{0，1，2，…，m-1} ，通常称h为散列函... 阅读全文

摘要：(1)若n较小(如n≤50)，可采用插入或选择排序。 　当记录规模较小时，插入排序较好；否则因为选择移动的记录数少于插人，应选选择排序为宜。 (2)若文件初始状态基本有序(指正序)，则应选用插人、冒泡或随机的快速排序为宜； (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。 　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 　若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和插入排序结合在一起使用。先利用插入排序求得较长的有序子文件，然后再两两归并之。因为插入排序是稳定的，所以改进后的归并排序仍是稳定的。 (4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。 　当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlgn)的时间。 (5)如果编程语言没有提供指针及递归，导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。 (6)这些排序算法中，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量t作为辅助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交换R[i]和R[j]，则只需交换t[i]和t[j]即可；排序结束后，向量t就指示了记录之间的顺序关系： R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key 　　若要求最终结果是： R[0].key≤R[1].key≤…≤R[n-1].key 则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是O(n)。 阅读全文

摘要：分配排序的基本思想：排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。 一、两种多关键码排序方法 　　最高位优先法（MSD法）。先按k1排序，将序列分成若干子序列，每个子序列中的记录具有相同的k1值；再按k2排序，将每个子序列分成更小的子序列；然后，对后面的关键码继续同样的排序分成更小的子序列，直到按kd排序分组分成最小的子序列后，最后将各个子序列连接起来，便可得到一个有序的序列。前面介绍的扑克牌先按花色再按面值进行排序的方法就是MSD法 　　最次位优先法（LSD法）。先按kd排序，将序列分成若干子序列，每个子序列中的记录具有相同的kd值；再按kd-1排序，将每个子序列分成更小的子序列；然后，对后面的关键码继续同样的排序分成更小的子序列，直到按k1排序分组分成最小的子序列后，最后将各个子序列连接起来，便可得到一个有序的序列。前面介绍的扑克牌先按面值再按花色进行排序的方法就是LSD法。 二、基于LSD方法的链式基数排序的基本思想 　　“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。 　　　　　　 三、基数排序的实现 public class RadixNodeT { private T data; //数据域 private RadixNodeT next; //引用域 public RadixNode(T val, RadixNodeT p) { data = val; next = p; } public RadixNode(RadixNodeT p) { …… 阅读全文

摘要：对于排序大列表数据，一个有效的排序算法是归并排序。类似于快速排序算法，其使用的是分治法来排序。归并排序的基本思想是：将两个或两个以上的有序子序列”归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列“归并”为一个有序序列。 一、基本思想 　　二路归并排序的基本思想是：将有n个记录的原始序列看作n个有序子序列，每个子序的长度为1，然后从第一个子序列开始，把相邻的子序列两两合关，得到n/2个长度为2或1的子序列（当子序列的个数为奇数时，最后一组合并得到的序列长度为1），我们把这一过程称为一次归并排序，对一次归并排序的n/2个子序列采用上述方法继续顺序成对归并，如此重复，当最后得到长度为n的一个子序列时，该子序列便是原始序列归并排序后的有序序列。 　　　　　　 　　　　第一步，将列表中的11个元素看成11个有序的序列，每个子序列的长度为1，然后两两归并，得到5个长度为2和1个长度为1的有序子序列。 　　　　第二步，将6个有序子序列两两归并，得到2个长度为4和1个长度为3的有序子序列。 　　　　第三步，将2个长度为4的有序子序列归并，得到第三趟归并结果。 　　　　第四步，将长度为8有序子序列和长度为3的有序子序列归并，得到第四趟归并结果，是长度为11的一个有序子序列。 二、并归排序的实现 public class MergeSort { //P=NP: public static Listint Demo(Listint data) { var arr = data.ToArray(); if (data.Count 2) { return data; } int middle = (int)Math.Floor(((decimal)(data.Count / 2))); var left = arr.AsSpan().Slice(0, middle).ToArray(); var right = arr.AsSpan().Slice(middle).ToArray(); return Merge(Demo(left.ToList()), Demo(ri…… 阅读全文

摘要：快速排序是C.R.A.Hoare于1962年提出的一种分区交换排序。它采用了一种分治法(Divide-and-ConquerMethod)策略，分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序是目前己知的平均速度最快的一种排序方法。 一、基本思想 　　快速排序方法的基本思想是：从待排序的n个记录中任意选取一个记录Ri（通常选取序列中的第一个记录）作标准，调整序列中各个记录的位置，使排在Ri前面的记录的关键字都小于Ri的关键字，排在Ri后面的记录的关键字都大于Ri的关键字，我们把这样一个过程称作一次快速排序。在第一次快速排序中，确定了所选取的记录Ri最终在序列中的排列位置，同时也把剩余的记录分成了两个子序列。对两个子序列分别进行快速排序，又确定了两个记录在序列中应处的位置，并将剩余的记录分成了四个子序列，如此重复下去，当各个子序列的长度为1时，全部记录排序完毕。　　　 　　　　 二、快速排序的实现 public class QuickSort { //排序算法--- 遍历--判断 ---交换-------降低 public static Listint Demo(Listint data, int left = 0, int? right = null) { int len = data.Count, partitionIndex; right = right ?? data.Count - 1; if (left right) { partitionIndex = partition(data, left, right.Value); Demo(data, left, partitionIndex - 1); Demo(data, partitionIndex + 1, right); } return data; } //分块的 左边是啥??? 右边是啥?? static int partition(Listin…… 阅读全文

摘要：一、基本思想 将被排序的记录的关键字垂直排列，首先将第一个记录的关键字与第二个记录的关键字进行比较，若前者大于后者，则交换两个记录，然后比较第二个记录与第三个记录的关键字，依次类推，直到第n-1个记录与第n个记录的关键字比较为止。上述过程称为第一趟起泡排序，其结果使得关键字最大的记录被安排在最后一个记录的位置上。然后进行第二趟起泡排序，对前n-1条记录进行同样的排序，使得关键字次大的记录被安排在第n-1个记录的位置上。一般地，第i趟起泡排序从第一条记录到第i条记录依次比较相邻两条记录的关键字，并在逆序时交换相邻记录，其结果使得这i条记录中关键字最大的记录被交换到第i条记录的位置上。整个排序过程需要K（1≤K≤n-1）趟起泡排序，判断起泡排序结束的条件是在一趟起泡排序的过程中，没有进行过记录交换的操作。从下图中可见，在起泡排序的过程中，关键字较小的记录像水中的气泡逐渐向上飘浮，而关键字较大的记录好比石块逐渐向下沉，每一次有一块最大的石块沉到底。 　　　　 二、冒泡排序的实现 public class BubbleSort { public static Listint Demo(Listint data) { for (var i = 0; i data.Count; i++)//i { for (var j = 0; j data.Count - 1 - i; j++)//j { if (data[j] data[j + 1]) { var temp = data[j + 1];///空间复杂度 //J+1--多了一个 data[j + 1] = data[j];//-j+1-- data[j] = temp; } } } return data; } } 三、时间复杂度分析 　　冒泡排序算法的最好情况是…… 阅读全文

摘要：一、基本思想 　　堆排序是针对直接选择排序所存在的上述问题的一种改进方法。它在寻找当前关键字最小记录的同时，还保存了本次排序过程中所产生的其他比较信息。 　　设有n个元素组成的序列{a0,a1,…an-1}，若满足下面的条件： （1）这些元素是一棵完全二叉树的结点，且对于i=0，1，…，n-1，ai是该完全二叉 树编号为i的结点； （2）满足下列不等式： 　　　　　　 　　　　　　则称该序列为一个堆。堆分为最大堆和最小堆两种。满足不等式(a)的为最小堆，满足不等式(b)的为最大堆。 　　 　　 　　由堆的定义可知，堆有如下两个性质： （1）最大堆的根结点是堆中关键码最大的结点，最小堆的根结点是堆中关键码最小的结点，我们称堆的根结点记录为堆顶记录。 （2）对于最大堆，从根结点到每个叶子结点的路径上，结点组成的序列都是递减有序的；对于最小堆，从根结点到每个叶子结点的路径上，结点组成的序列都是递增有序的。 　　将待排序的记录序列建成一个堆，并借助于堆的性质进行排序的方法叫作堆排序。堆排序的基本思想是：设有n个记录，首先将这n个记录按关键码建成堆，将堆顶记录输出，得到n个记录中关键码最大（或最小）的记录；调整剩余的n-1个记录，使之成为一个新堆，再输出堆顶记录；如此反复，当堆中只有一个元素数时，整个序列的排序结束，得到的序列便是原始序列的非递减或非递增序列。 　　从堆排序的基本思想中可看出，在堆排序的过程中，主要包括两方面的工作： （1）如何将原始的记录序列按关键码建成堆； （2）输出堆顶记录后，怎样调整剩下记录，使其按关键码成为一个新堆。 　　首先，以最大堆为例讨论第一个问题：如何将n个记录的序列按关键码建成堆。 考虑数字序列70、30、40、10、80、20、91、100、75、60、45 　　　　 　　完全二叉树构建最大堆的示意图 　　　　　　　　 二、堆排序的实现 　　在实现堆排序算法之前，先要实现将完全二叉树构建成最大堆的算法，然后在构建的堆之上实现堆排序，具体实现如下： public class HeapSort { static int _count; public static Listint Demo(Listint data) { Build(data); …… 阅读全文

摘要：选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的记录序列的最后，直到全部记录排序完毕。 一、基本思想 　　选择排序是一种简单且直观的排序方法。选择排序的做法是：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。 　　在选择排序中，每次排序完成一个记录的排序，也就是找到了当前剩余记录中关键字最小的记录的位置，n-1次排序就对n-1个记录进行了排序，此时剩下的一个记录必定是原始序列中关键码最大的，应排在所有记录的后面，因此具有n个记录的序列要做n-1次排序。 　　下图为选择排序的示意图： 　　　　 　　　　从上图中我们可以看出，在初始关键字序列中，10是当前最小的关键字，因此在第一趟排序过程中，10和70互换；在第二趟排序时，20是从第二个记录30开始的最小关键字，互换20与30；依此类推……。 二、选择排序的实现 public class SelectSort { public static Listint Demo(Listint data) { int minIndex, temp; for (var i = 0; i data.Count - 1; i++) { minIndex = i; for (var j = i + 1; j data.Count; j++) { if (data[j] data[minIndex]) { minIndex = j; } } temp = data[i]; data[i] = data[minIndex]; data[minIndex] = temp; } return data…… 阅读全文