前言八种排序算法和三种查找方法是《数据结构》中非常基础的知识点。作为回顾，这里有八种常见的排序算法。八种常见的排序算法之间的关系如下：它们的性能比较：下面用Python实现。直接插入排序算法的思想：直接插入排序的核心思想是：将数组中的所有元素依次与之前排列的元素进行比较，如果选择的元素小于已排序的元素，则进行交换直到所有元素都比较通过。因此，从上面的描述我们可以发现，直接插入排序可以用两个循环来完成：一级循环：遍历所有要比较的数组元素二级循环：比较本轮（选中）的元素与已经对排好序的元素（ordered）进行了比较。如果：selected>ordered，则交换两个代码，实现希尔排序算法思想：分组排序；每次将间隙缩小一半，重复上述操作；当gap=1时，使用直接插入完成排序。同上：从上面的描述我们可以发现，希尔排序的整体实现应该是通过三个循环来完成的：第一层循环：将gap依次减半，对序列进行分组，直到gap=1第二层和第三层layersLoop：即直接插入排序所需要的两个循环。有关详细说明，请参见上文。代码实现：简单选择排序算法思想简单选择排序的基本思想：比较+交换。从待排序的序列中，找到key最小的元素；如果最小元素不是待排序序列的第一个元素，则与第一个元素交换；从剩下的N-1个元素中，找到key最小的元素，重复步骤（1）和（2），直到排序结束。因此，我们可以发现，简单的选择排序也是通过两层循环实现的。一级循环：依次遍历序列中的每个元素。2级循环：将遍历得到的当前元素与剩余元素依次比较，满足最小元素条件则交换。代码实现了堆排序堆的概念：本质上是一个数组对象。一个特别重要的属性：任何叶节点都小于（或大于）其所有父节点。对此又进一步分为大顶堆和小顶堆。大顶堆要求节点的元素大于其子节点，小顶堆要求节点的元素小于其左右子节点。要求。使用堆排序是一种基于大顶堆或小顶堆的排序方法。接下来我们通过大顶堆来实现。基本思想：堆排序可以按以下步骤进行：首先，构建序列称为大顶堆；（这就满足了大顶堆的性质：根节点的元素一定是当前序列的最高值）取出当前大顶堆的根节点，和末尾的元素交换顺序;（此时：序列末尾的元素为排序后的值；由于元素的交换，当前根节点的堆不一定满足大顶堆的性质）调整交换的n-1个序列元素，满足大顶堆的性质；重复步骤2.3，直到堆中只有1个元素代码实现：冒泡排序基本思想冒泡排序思想比较简单：依次比较序列中的左右元素，保证右边的元素总是大于左边的元素；（第一轮结束后，序列中的最后一个元素必须是当前序列的最大值；）对于序列，对剩余的n-1个元素再次执行步骤1。对于一个长度为n的序列，一共需要进行n-1轮比较（使用while循环可以减少执行次数）*实现快速排序算法思想的代码：基本思想快速排序：挖洞填数+分治法从序列中选择一个枢轴数（pivot）这里我们选择序列中的第一个数作为枢轴数依次遍历序列中的所有数，比主元数大的在右边，比主元数小的在左边重复1.2的步骤，直到所有子集中只有一个元素。伪代码描述如下：1.i=L;j=R;挖出参考号，形成第一个坑a[i]。2.j—从后往前找一个比它小的数，找到后挖出这个数填上前面的坑a[i]。3、i++从前到后找一个比它大的数，找到后把这个数挖出来填到前面的坑a[j]中。4、重复步骤2和3，直到i==j，将引用数填入a[i]代码实现：归并排序算法思想：归并排序是一种基于归并操作的有效排序算法，该算法是对分而治之的方法。它的基本操作是：合并已有的子序列，得到一个完全有序的序列；即先把每个子序列排好序，再把子序列段排好序。归并排序其实需要做两件事：分解——每次将序列对半拆分合并——将拆分后的序列段成对排序合并。因此归并排序实际上是两个操作。如何合并拆分和合并？L[first...mid]是第一段，L[mid+1...last]是第二段，两端已经排好了，现在我们要把两端合成到L[first...last]也有顺序。首先从第一段和第二段中取出元素进行比较，将较小的元素赋值给temp[]，重复上一步。当某一段赋值结束后，将另一段剩余元素赋值给temp[]，此时将temp[]中的元素复制到L[]中，如何分解得到的L[first...last]整齐的？这里，我们采用递归的方法，首先将待排序的列分成两组，A和B；然后重复A、B序列的分组；直到分组后组内只有一个元素，这时我们认为组内所有元素都是有序的，分组结束。代码实现基数排序算法思想基数排序：通过序列中每个元素的值，通过多次“分配”和“收集”对排序好的N个元素进行排序，实现排序。赋值：我们取出L[i]中的元素，先确定其个位的个数，根据编号分配到序号相同的桶中收集：当序列中的所有元素都赋值到对应的桶，然后收集桶中的元素，以组成一个新的待排序序列L[]在新形成的序列L[]中重复分配和收集几十上百个元素，直到序列中的所有*分配了**位，排序结束。根据上面“基数排序”的展示，我们可以清楚的看到整个实现过程。写完后记，我们运行一下时间对比：1wdata:10wdata:从运行结果来看，堆排序，归并排序，基数排序确实很快。对于快速排序迭代深度超过的问题，可以考虑用非递归的方式实现快速排序。参考数据数据结构可视化：visualgo山排序介绍：山排序堆排序：《算法导论》读书笔记第六章堆排序博客园：silentvoid
