XIAOSUO 记录个人学习的足迹

摘要：对于排序大列表数据，一个有效的排序算法是归并排序。类似于快速排序算法，其使用的是分治法来排序。归并排序的基本思想是：将两个或两个以上的有序子序列”归并”为一个有序序列。在内部排序中，通常采用的是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…… 阅读全文

摘要：希尔排序(Shell Sort)是插入排序的一种。因D．L．Shell于1959年提出而得名。 一、基本思想 　　对待排记录序列先作“宏观”调整，再作“微观”调整。 　　所谓“宏观”调整，指的是 “跳跃式”的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序。关键是，这种子序列不是由相邻的记录构成的。假设将n个记录分成d个子序列，则这d个子序列分别为： { R[1]，R[1+d]，R[1+2d]，…，R[1+kd] } { R[2]，R[2+d]，R[2+2d]，…，R[2+kd] } … { R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] } 　　其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。 　　下图为希尔排序示意图： 　　　　 二、希尔排序的实现 public class ShellSort { public static Listint Demo(Listint data) { for (int gap =(int) Math.Floor(((decimal)(data.Count / 2))); gap 0; gap = (int)Math.Floor(((decimal)(gap / 2)))) { for (var i = gap; i data.Count; i++) { var j = i; var current = data[i]; while (j - gap = 0 current data[j - gap]) { data[j] = data[j - gap]; j = j - gap; } data[j] = current; } } return data; } } 三、时间复杂度分析 　　大量研究证明，若增量序列的取值比较合…… 阅读全文

摘要：插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的数据序列的适当位置，直到全部记录插入完成为止。 一、基本思想 　　假设待排序的记录存放在数组R[0…n-1]中。初始时，R[0]自成1个有序区，无序区为R[1…n-1]。从i=1起直至i= n-1为止，依次将R[i]插入当前的有序区R[0…i-1]中，生成含n个记录的有序区。 　　通常将一个记录Ri插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第i趟插入排序。 　　排序过程的某一中间时刻，R被划分成两个子区间R[0…i-1]（已排好序的有序区）和[i…n-1]（当前未排序的部分，可称无序区）。 　　插入排序的基本操作是将当前无序区的第1个记录R[0]插人到有序区R[0…i-1]中适当的位置上，使 R[0…i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。 　　下图为插入排序是示意图： 　　　　 二、插入排序的实现 public class InsertSort { public static Listint Demo(Listint data) { int preIndex, currentIndex; for (var i = 1; i data.Count; i++) { preIndex = i - 1; currentIndex = data[i]; while (preIndex = 0 data[preIndex] currentIndex) { data[preIndex + 1] = data[preIndex]; preIndex--; } data[preIndex + 1] = currentIndex; } return data; } } 三、时间复杂度分析 　　插入排序算法的时间复杂度分为最好、最坏和随机三种情况： 　　　　（1）最好的情况是关键字在序列中顺序…… 阅读全文

摘要：　　设树T如下图所示，结点R是根，根的子树从左到右依次为T1，T2，…，Tk。 　　　　 一、树的前序遍历 　　若树T非空，则： 　　　　①访问根结点R； 　　　　②依次前序遍历根R的各子树T1，T2，…，Tk。 　　先序遍历树结点算法实现如下： //先序遍历树结点 public void PreOrder(MLNodeT root) { if (root == null) { re... 阅读全文

摘要：　　树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树；反之，任何一棵二叉树也能惟一地对应到一个森林或一棵树。 一、树转换为二叉树 　　树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树： 　　①在所有兄弟结点之间加一连线； 　　②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。... 阅读全文

摘要：三、 孩子链表表示法 孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。 　　下面的(a)图就是用孩子链表表示法来存储图中的树。 　　　　 　　注意： 　　① 孩子结点的数据域仅存放了它们在向量空间的序号。 　　② 与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。 　　③ 将双亲链表表示法和孩子... 阅读全文