希尔排序的算法，希尔排序js

10大经典排序算法江山图

这里我们不再重复排序算法的指标。我在上一篇文章中已经清楚地列出并分析了它们，它们非常重要。上一篇文章我没有看好友推荐。这里是。通票极客算法培训笔记（五），十大经典排序：冒泡排序、选择排序、插入排序。

冒泡排序、选择排序和插入排序的时间复杂度都比较高，都是O(n2)，适合对小数据进行排序，但是如果你有大数据需要排序，这三种排序算法可能会有点吃不消。需要优化。首先我们来看一下优化思路。

首先，对气泡、选择和插入进行排序的第一步是全盘扫描。如果想要有所突破，将平均时间复杂度降低到O(n log n)，从头开始扫描根本不可能。考虑部分扫描。接下来，排除小弟中的选择排序后，我们分析Eyama图，发现冒泡排序和插入排序的时间复杂度在最好和最差的情况下是呈指数级差异的，我明白了。大神们为这个地方的优化发挥了作用。

事实上，半隐山排序和快速排序（程序员可能听说过，但大多数人不知道）是插入排序和冒泡排序的变种，而这两种排序分别有前腿和后腿。一场发生在1959 年，一场发生在1960 年。

互联网上的许多文章解释了什么是山排序，但没有解释为什么这个版本的排序存在以及它是如何演变的，所以我将尝试在这里分析它。Masu。如果您有不同意见，请随时提出。分享它们。

虽然排名前十的排序将军都有正经的名字，但希尔排序却有一个外国名字，但没有人知道它是以算法的提出者唐纳德·谢尔（Donald Shell）的名字命名的。我想你可以猜到。学习算法是非常困难的。更令人惊奇的是我们如何能够突破固有的思维模式并创建算法。希尔的微小改变将插入排序的时间复杂度从指数级降低，并将废话带到了公共屏幕上。看上一篇文章可以乘坐上面提到的直达列车）。

首先，获取并比较上一篇文章中的插入排序算法。你可以看到，这不是我上面说的。插入排序代码： public class InsertSort { public static int[] insertSort(int[] arr) { if (arr==null || arr.length 2) return arr; int n=arr.length; //下标0处的数字默认情况下已订购。从索引1处的数字开始遍历，放到应该在的地方for (int i=1; i n; i++) { //设置记录要插入数据的变量，动画中的红色元素Apply int tmp=arr[i]; //从排序好的序列中，从右侧开始比较，找到较低的数字，即动画中的绿色元素编号。 int j=i; //红色元素的索引大于0。满足插入元素和遍历元素的大小关系。遍历的元素将被撤消并移动到新位置。 //继续遍历，直到不再满足大小关系。这就是位置。 //也就是说，如果红色元素小于绿色元素，则绿色元素会被移动while (j 0 tmp arr[j - 1]) { //将绿色元素移动一位arr [j]=arr [j - 1]; j--; } //如果有小于数字的元素，则插入if (j !=i) { arr[j]=tmp; } } return arr; }} public class ShellSort { public static int[] shellSort(int arr[]) { if (arr==null || arr.length 2) { return arr; } int n=arr.length; //对每组以h 为间隔的元素进行初始排序h=n/2; for (int h=n/2; h 0; h /=2) { //i代表右边的组每个局部组依次进行插入排序( int i=h; i n; i++) { //依次对每组进行插入排序insertSort( arr, h, i); } } return arr; } /** * 部分插入排序* @param arr 原始数组* @param h 组中元素个数， number组数、间隔数、增量数。例如，Chestnut 的第一组f=5 是{arr[0],arr[5]]} , {arr[1],arr[6]]} , {arr[2],arr[7]]} . * @param f 每组的第二个元素。默认为第一个元素。从第二个元素开始排序*/private static void insertSort(int[] arr, int h, int f) { int n=arr.length; //索引0 处的数字默认排序。从索引1处的数字开始遍历，放到该放的地方(int i=f; i n; i++) { //应用从动画元素中取出的变量，记录要插入的数据。 int tmp=arr[i]; //从排序后的序列右端开始比较，找到较小的值int j=i; //将原来的排序区间1插入到区间h中，插入上一篇排序为j0，这实际上对应于j=1。这里j=h。不难理解，但是(j=h tmp arr[j - h]) { //在本地数组中向上移动一位arr[j]=arr [j-h]; j -=h ; } //如果数量比较小， if (j !=i) { arr[j]=tmp; } } }} 看代码，插入排序几乎是一样的，都是使用分组插入排序的逻辑，可以看到是已更改，1 现在为h。希尔排序代码为：稳定性分析不稳定。首先，我们发现插入排序是稳定的，因为它可以保证每次插入时数据的顺序都是相对有序的，并且顺序不需要被相同大小的元素打乱。排序的分区有一个顺序。然而，山排序只能确保组内的元素按顺序排列。相同大小且排在后面的元素可能会在组排序中直接移动到前面，从而导致排序混乱。例如，数组arr 为3 1 1 2。根据希尔排序，第一组是[arr[0]、arr[2]]、[arr[1]、arr[3]] 或[3]。 1], [1, 2]，第三个1在前面。时间复杂度分析是最好情况和最坏情况。具体数值请参考Eyama图表。由于计算方法过于复杂，这里我们不进行具体计算。如果您有兴趣，可以参考相关论文。

快速排序百度百科上说快速排序是冒泡排序的一种，但我查遍了也没明白为什么。我讨厌人们说“，这就是结论”，但他们不告诉我原因。我们并非生来叛逆、不听话。有些东西不会凭空出现。请告诉我们您的背景。比看代码更好。我读了半辈子了，还是想不起来。我喜欢探索事物之间的联系。这很有趣，可以扩展你的记忆，帮助你记忆（推论1）如果你同意请写在评论里）。

快速排序使用分而治之的概念。分而治之算法的基本思想是将一个规模为N的问题分解为K个规模更小的子问题。这些子问题相互独立且具有相同的性质。求解子问题的解并将它们组合起来得出原始问题的解。分而治之算法大多是递归实现的，因为并不总是能够将问题一一分解。

该算法描述了快速排序A[p.r] 的分治过程。拆分：选择一个枢轴元素来拆分数组。将数组A[p.r] 拆分为两个子数组（可能为空）A[p.q-1] 和A[q+1.使得A[q] 大于或等于A.r] 。 [p.q-1] 的每个元素都小于A[q+1.r] 的每个元素。计算下标q的值也是分裂过程的一部分。解决方案：递归调用快速排序，分别对子数组A[p.q-1] 和A[q+1.r] 进行排序。合并：因此子数组不需要合并操作，并且数组A[p.r] 已经排序。该算法的思想是每次选择一个主元（分区值），将其他数字按顺序与该主元进行比较，较大的放在右侧，较小的放在左侧，然后选择该主元。比较左右两组数字，将较大的放在左边，较小的放在右边，如此重复，直到成为一个元素，整体完成。数组变成有序序列。

为什么快速排序是冒泡排序的变体？

首先，每次重复时枢轴的顺序都必须正确。这与冒泡排序非常相似。冒泡排序是指每次遍历冒泡时，都会有一个元素被正确排序。此外，快速排序还执行比较。交换对和位置也和冒泡排序类似，快速排序的核心交换代码和冒泡排序类似，从这些点我们可以说快速排序是冒泡排序的一个变体。

动画显示亮黄色代表此次遍历期间选定的枢轴。每次，都会选择数组中的第一个数字作为主元。该数组中的枢轴为3、38、19、4、26、27、46、47。 50; 深黄色代表已排序的元素。绿色表示小于主元值的数据，紫色表示大于主元值的数据。绿色子数组和紫色子数组表示该子数组有一个元素；每次遍历后，至少有一个元素是有序的，主元元素也必须是有序的。图形分析：图形分析继续使用上面数组中的数据。动画图形包含太多元素。浅黄色代表该组选定的枢轴，深黄色代表重新排序的枢轴。如果组中只有一个元素，则无需进一步排序。每次遍历之后，主元都必须是有序的，如果组中只剩下一个元素，我们就知道其他元素也将是有序的。代码实现将数组的第一个元素作为基值主元，并每次设置数组的基值主元。右边第一个数字是标记，用于存储小于主元的元素以及遍历数组。如果该元素大于枢轴，我们通常会继续遍历；如果该元素小于枢轴，我们将该元素放在标记的位置，即将该元素与标记指向的元素交换。要继续存储小于主元值的元素，请在标记后指定一个位置。一次扫描后，标记存储小于第一个元素的所有元素。如果枢轴是一个小元素，它将与标记中的最后一个元素交换枢轴，并将枢轴移动到中心。枢轴左侧的元素较小，右侧的元素较大。 public class QuickSort { public static int[] QuickSort(int[] arr) { return sort(arr, 0, arr.length-1); } public static int[] sort(int[] arr, int left, int right) { //递归结束条件，partial数组的长度为1 if (left=right) { return arr; } //获取中轴元素的位置，即枢轴值int hub=Partition(arr, left, right) ; //剪切，先对左数组递归排序arr=sort(arr, left, hub - 1); //剪切，对右数组递归排序arr=sort(arr, hub + 1, right); return arr; } private static int Partition(int[] arr, int left, int right) { //枢轴选择数组的第一个元素int hub=arr[left]; //标记为第一个选择要删除的第一个元素位于pivot的右侧，存储小于pivot的元素。 mark指向的最后一个元素是int数组中最后一个小于主元的值mark=left + 1; for (int i=mark; i=right; i++) { //扫描到的元素小于主元元素，替换它带有一个标记元素if (arr[i ] hub) { int temp=arr[i] ; arr[i]=arr[mark]; arr[mark]=temp; //一个标记元素向右移动mark + +; } } //交换到最后一个标记，加1并且必须减去；mark -=1; //如果left==mark，则不交换并且意味着没有比枢轴小的值。这个pivot是一个group，直接返回mark if (left mark) { //mark元素与pivot指向的第一个元素交换。即枢轴元素和最后一个小于枢轴的元素交换，并且交换左边的所有元素。枢轴的边比枢轴小arr[left]=arr[mark]; arr[mark]=hub; } return mark; } }我完全基于动画编写了这段代码，以便任何人都可以理解我们将实现看下面的内容就知道了，但是快速排序方法也可以使用双指针方法来实现，所以如果你有兴趣，你可能想尝试自己实现。稳定性分析不稳定。还是3 1 1 2数组分析，第一个分区[2, 1, 1], [3]，第二个分区[1, 1, 2], [3]，这里两个1的位置交换了。

在时间复杂度分析的最佳情况下，每次分割操作都可以将数组分割成两个大小近似相等的较小区间。这由下面所示的递归树表示。第一级为n次，第二级为2次。递归，每次n/2次，共n次操作。第三层有4次递归，每次n/4次，总共n次操作。 …（最后一层）第k 层，k 次递归，每次n/2^(k-1) 次，总共n 次操作。由于递归的终止条件只有一个元素，所以这里**n/2^(k-1)=1* *=**k=logn+1** 即**递归树的深度为logn**。时间复杂度=每层操作次数* 树深度=nlogn，即：O(nlogn)；最坏情况下，数组中的数据已经排序为1、3、5、6、8 等情况。如果每次都选择最后一个元素作为枢轴，则每次划分得到的两个间距将不相等。大约需要执行n次分区操作才能完成整个快速队列过程。快速排序的时间复杂度从O(nlogn) 退化为O(n2)，因为每个分区平均需要扫描大约n/2 个元素。

这篇文章本来想写四种算法，但是没想到这两种算法写了这么多内容，所以暂时就写这两篇文章。下一篇，如有错误，敬请批评指正。任何人都可以关注我的公众号《阿甘的码路》。我是阿甘，小女巫。最好能交个朋友！