排序演化（一）：希尔

忘尘
351 阅读17分钟

人脑排序

给一个数组排序

全文默认是升序

[11,2,33,4]

image-20190725121332083

按照人的正常思维，我们会看一遍，选择最大的，然后放在最后面，然后在剩余的数里面不断重复。

脑海里的思考就是，

  1. 33 移到最后
  2. 11 移到 33 前面
  3. 4 移到 11前面
  4. 2 在正确位置了
  5. 好了

当然，你思考的可能是

  1. 2 移到最前
  2. 4 移到 2后面
  3. 11 移到 4后面
  4. 33 在正确位置了
  5. 好了

后面我们都基于上面的 从小到大的移法

如果灰色背景是一个存放蓝色长方形的平面，蓝色长方形是一个实体，我们没有空余的位置直接把 2 移到最前面，那只能与该位置上的元素进行交换了。

于是就有

swap(2,11)

image-20190725121806335

swap(4,11)

image-20190725121838657

swap(11,33)

image-20190725121908291

在上面的排序过程中，我们似乎只是进行了交换操作。

但实际上，我们的大脑是进行了比较的，只是上面的数字少差异又大，立马就知道比较后的结果

如果数字很多的话？

image-20190725115808501

假设你还按前面所说的思路（从小到大找）：

此时，你想着是谁移到第一个位置呢？

这个谁的意思就是全部数中的最小值。

谨慎的你，就会先在纸上写 21，假设为最小值

然后和后面的数字不断的比较，来确认21是不是最小的

交换函数

为了使代码简洁，这里使用下面这种方式作为交换函数

let a = '11'
let b = '22'; // 这里要加分好 不然语法错误
[a, b] = [b, a]
console.log(`a=${a}`); // a=22
console.log(`b=${b}`);// b=11

上面的过程我们就可以写成

注意，此时我们都是用下标来表示一个数

let arr = [21, 22, 30, 25, 28, 26, 29, 25, 26, 24, 22, 21, 21, 29, 25, 26, 24, 22, 21]
// 类似上述中 纸上的的最小值，先假设是数组的第一个为最小值
let minIndex = 0
for (let i = minIndex + 1; i < arr.length; i++) {
  // 不断与后面的数进行比较，如果找到比现在数还小的，就划掉原来的数，填上找到数
  if (arr[i] < arr[minIndex]) minIndex = i
}
// 下面这段代码其实就是swap()交换函数
// 最小的元素和第一个元素交换
[arr[minIndex], arr[0]] = [arr[0], arr[minIndex]]

通过上面的代码，我们就能比较找到最小的值，然后和第一个位置的元素进行交换。

当我们完成了第一步时，数组中的第一个数已经就是有序的了

image-20190725123951959

此时，我们把除去第一个数的数组作为新的数组的话（即红框里的数组），重复以上操作。

+for (let i = 0; i < arr.length; i++) {
- let minIndex = 0
+	let minIndex = i
	for (let i = minIndex + 1; i < arr.length; i++) {
  	if (arr[i] < arr[minIndex]) minIndex = i
	}
- [arr[minIndex], arr[0]] = [arr[0], arr[minIndex]]
+	[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]
+}

i是每次红框缩减后的第一个值，这样当红框缩减为1时，即i此时等于arr.length - 1，回看整个数组，就是有序的了。

选择排序

上面的代码写成函数就有

let arr = [21, 22, 30, 25, 28, 26, 29, 25, 26, 24, 22, 21, 21, 29, 25, 26, 24, 22, 21]

function selectionSort(arr) {
  for (let j = 0; j < arr.length; j++) {
    let minIndex = j
    for (let i = minIndex + 1; i < arr.length; i++) {
      if (arr[i] < arr[minIndex]) minIndex = i
    }
    [arr[minIndex], arr[j]] = [arr[j], arr[minIndex]]
  }
  return arr
}
console.log(selectionSort(arr));
// [ 21, 21, 21, 21, 22, 22, 22, 24, 24, 25, 25, 25, 26, 26, 26, 28, 29, 29, 30 ]

这种排序，有个专有的名字：选择排序

效率分析

我们来思考一下效率的问题。

在排序的过程中，我们一般只有两种操作

  • 比较
  • 交换

比较

image-20190725142638236

把全部加起来

（n-1）+（n-2）+…+2+1 = \frac{((n-1)+1)(n-1)}{2} = \frac{n(n-1)}{2}=\frac{1}{2}(n^2-n)

如果我们只是想看个大概，即看最明显的，忽略细节，

比如系数\frac{1}{2}这种常数直接忽略掉，

或者两着相差过的数，如n^2和 n两者，我们就留最大者

因为当数很大的时候，n对于n^2来说就可以忽略不计。

我们称这种表达法为大O表示法，那此时的比较规模就为 n^2

后面如果没说真实次数，就默认是大O表示法，比如说约一约

image-20190725145117851

总的来说就是

  • 真实比较次数：\frac{1}{2}(n^2-n)
  • 大O表示： n^2

交换

交换的次数就比较玄了，如果整个数组是有升序的，整个数字都不用交换，如果是降序的，那就交换n次

取平均的话也就\frac{1}{2}n，约一约，就是n

总结

  • 运行时间和输入无关。不管我们输入的数组是否有序，比较的次数永远是n^2
  • 数据移动是最少的。每次比较过后的移动，即交换，都是精准的，不会有额外的移动。

插入排序

上面的排序，有个特别致命的缺点，就是如果数组已经是有序的，比较的次数还是那么多。

我们思考一个情景。

课外活动，看电影，每个同学搬椅子排成一列纵队，身高由低到高

image-20190725151418991

队伍已经排好了，此时，4号同学迟到了，现在要插入到这个队伍中

image-20190725151451035

这个4号同学会怎么插入到队伍中呢？

他会先把椅子放在7号同学后面

image-20190725151812696

然后和7号同学说：同学，你比我高，我看不到电影，你往后做一个位置呗，等等我坐那个空位置

image-20190725152119182

然后4号同学发现，6号还是比他高呀！绝望！就和6号说，你也往后坐个位置呗，前面空出的位置给我。

还没坐下，4号发现，5号还是比他高，所以又和5号说，你往后坐一个位置呗。

这个时候，4号对比了下他和3号的身高，发现，嗯终于有人比我矮了，那此时4号就直接坐下来了。

image-20190725152345998

在这个过程中，4号同学，并没有3号前面的同学比较就找到了正确的位置，那是因为原本的队伍是有序的，当前面的同学比你矮时，那更前面的同学一定更矮，我们就没必要比较了。很显而易见呀！

let arr = [1, 2, 3, 5, 6, 7, 4]
// j表示最后一个位置
let j = arr.length - 1
// temp此时指4号同学
let temp = arr[j]
while (temp < arr[j - 1] & j > 0) { // 如果前面没位置了 就不用比了呀 所以 j一定要大于0
  // arr[j - 1] 表示前面的同学
  // 下面的操作表示 前面的同学往后做
  arr[j] = arr[j - 1]
  j--
}
// 最后4号同学在空出来的位置上坐下
arr[j] = temp
console.log(arr);
// [ 1, 2, 3, 4, 5, 6, 7 ]

那我们能不能把这种思想来解决选择排序里面比较次数过多的问题呢？

我们遇到的第一个障碍是，上面的操作是把一元素插入到一有序队列中。

此时我们思考，如果班上只有一个人，不管此人身高如何，他怎么站，他一定是有序的。

假设我们从零开始整理队伍。

首先，让某一同学搬好椅子，在学校规划区域中的最前面，坐好。

那一个有序队列就出先了。

后面只要，不断添加同学，让他先把椅子放在该队列的末端，然后比较前面与自己两者的身高，重复上述4号同学的动作。

记得，不能超过最前面的同学的位置，如果可以随便坐前面，没有规矩，那大家直接坐到屏幕前吧。

同理，我们可以把数组中的第一个元素作为有序数组，那我们在后面一次往该数组插入，这样就能保持前面的数组是有序的。

function insertionSort(arr) {
  // 从1开始排，因为0做为有序队列
  for (let i = 1; i < arr.length; i++) {
    let j = i
    let temp = arr[j]
    while (temp < arr[j - 1] && j > 0) {
      arr[j] = arr[j - 1]
      j--
    }
    arr[j] = temp
  }
  return arr
}
console.log(insertionSort([11, 2, 33, 4, 55]));
// [ 2, 4, 11, 33, 55 ]

效率分析

比较

很明显，比较次数是比选择排序少的，所以我们按最多的情况来数。

第一次插入时，最多比较1次

第二次插入时，最多比较2次

….

最后一次插入时，最多比较n-1次

总数是n，第一个默认有序，所以不用比较，所以最后一次插入，前面共有n-1个人，比较n-1次

1+2+...+（n-2）+（n-1） = \frac{((n-1)+1)(n-1)}{2} = \frac{n(n-1)}{2}=\frac{1}{2}(n^2-n)

这是最坏的情况，而原本的选择排序是每次都是这种情况。

如果抛却最坏情况，比如数组中大部分是正确有序的，我们只要比较少部分即可。

所以在针对以下情景时

  • 数组中每个元素距离它的最终位置都不远
  • 一个有序的大数组接一个小数组
  • 数组中只有几个元素的位置不正确

插入排序效率会特别高。或者可以说，当倒置的数量很少时，插入排序基本是最快的。

但是奈不住，取平均下来，简单的除以2，把这个数约一约，会发现最后的效率还是n^2

交换

更有意思的是，交换次数相对选择排序，高了很多，但是这么说也不公平，选择排序是全部排序共交换次数中最少的，唯一的线性增长的。

插入的交换次数是和上面的比较次数同理，因为每比较一次就交换一下，即

1+2+...+（n-2）+（n-1） = \frac{((n-1)+1)(n-1)}{2} = \frac{n(n-1)}{2}=\frac{1}{2}(n^2-n)

约一约就是n^2

总结

抛却选择排序是最少交换次数的排序而言，插入排序把比较次数降低了许多，尤其是在数组大部分有序的情况下，性能特别好。

但是因为存在如果排序的元素开始排序时，距离它正确的位置很远时，效率极低，比如

在一个1000人的升序队伍，一个小矮人也要来插入的话，他一个人就要影响这个有序队伍全部人往后移动。

希尔排序

针对选择排序固定的比较次数，我们使用了往局部有序数组里插入数据的插入排序。

但是插入排序在逆序这种极端条件下表现效果特别差，我们思考下能不能优化下？

灵感1

还是拿小矮人的情况举例。

身高1.1米的小矮人要插入队伍了

他让最后一位2.1米同学站起来，两者比下身高，发现自己矮，要往前

然后再比倒数第2位1.9米高的同学，再问倒数第3位1.88米高的同学

连续问到倒数第五个1.8米高的同学，他实在受不了了

他说：你就不能有点逼数吗？往前点问，别一个一个问，这一块（已经指大概五六个人的范围）的人都比你高，你走远点再问。

这给了我们一个灵感，我们可以把比较的步伐扩大一点，然后慢慢的把步伐变成最小。当然如果是小矮人这种情况，先过十个问，再过五个问，最后一个一个问，看起来好像挺好的。

但是怎么判断步伐的改变，还有涉及错过的问题？就会让简单的排序格外复杂。

那我们要怎么运用这个增大步伐的灵感呢？

灵感2

我们在思考下我们的快速排序的痛点是什么？

存在如果排序的元素开始排序时，距离它正确的位置很远时，效率极低

我们还是举一个例子：

还是班级按身高排序

在开学的时候，班主任让班上的人到门口，按身高排序，这个时候大家刚报道都不是很熟，你会很热情的找到某位同学背对背比身高吗？当然不会？

那我们是怎么做的呢？

我们一般是凭感觉和某几个身高相仿的人在一起，整个队伍此时虽然不是准确的有序，但是一眼望过去，不会说参差不齐。

此时，老师就会让第2个同学开始使用插入排序来排身高了。

插入排序就要背对背咯，因为是老师命令的，就不会显得很突兀啦

大家很快就排好了队伍，因为原本所在的位置和最终的位置距离很近，还有些可能都不用移动。

灵感1+灵感2

如果使用灵感1增大步伐，如果要实现准确排序的话，我们就会涉及到步伐如果调节和错过的问题。主要是错过的问题，让我们很难办

通过灵感2，我们发现，如果整个队伍原本是大致有序的，最后再来插入排序效率会很快。

结合两者，很容易想到，通过大步伐来让队伍大致有序，这样就可以避免错过正确位置的问题，因为错过就错过了呀，我们只要大致有序。

image-20190725185244768

image-20190725181040841

let arr = [11, 2, 33, 4, 55, 6, 77, 8, 99, 10, 1, 12]

这里我们先简单的使用步伐为3进行插入排序

红色组：11 --> 4 --> 77 --> 10

蓝色组：2 --> 55 --> 8 --> 1

绿色组：33 --> 6 --> 99 --> 12

let arr = [11, 2, 33, 4, 55, 6, 77, 8, 99, 10, 1, 12]

let gap = 3
for (let i = gap; i < arr.length; i++) {
  let j = i
  let temp = arr[j]
  while (temp < arr[j - gap] && j > 0) {
    arr[j] = arr[j - gap]
    j -= gap
  }
  arr[j] = temp
}
console.log(arr);
// [ 4, 1, 6, 10, 2, 12, 11, 8, 33, 77, 55, 99 ]
/*
4 -- > 10 -- > 11  -- > 77
1 -- > 2 -- > 8 -- > 55
6 -- > 12 -- > 33 -- > 99
*/

image-20190725183612912

如果上面看的懂，就不用看下面的解释

我们拿个插入排序对比下

+ let gap = 3
function insertionSort(arr) {
+ for (let i = gap; i < arr.length; i++) {
-	for (let i = 1; i < arr.length; i++) {
		let j = i
		let temp = arr[j]
+   while (temp < arr[j - gap] && j > 0) {
-		while (temp < arr[j - 1] && j > 0) {
+			arr[j] = arr[j - gap]
-			arr[j] = arr[j - 1]
+ 		j -= gap
-			j--
		}
		arr[j] = temp
	}
	return arr
}

  1. gap = 3

    多了一个步伐的设置

  2. for (let i = gap; i < arr.length; i++) {

    此时i的初始值，由原来的1变成了gap

    当初设为1时，是表示从arr[1]开始 ，因为前面arr[0]是有序的

    此时我们分为了三组

    4 -- > 10 -- > 11 -- > 77 1 -- > 2 -- > 8 -- > 55 6 -- > 12 -- > 33 -- > 99

    那对于每组的第一个，同样假设为有序，应该从后面的数开始，这里特指10，2，12

    image-20190725194536461

    箭头所指的数就为要开始插入的数，即i = gap

    但是值得注意的是，这里的i的增长步伐还是1，仔细想象就觉得理所当然了，因为外循环的作用就是遍历每个元素，如果不为1，如果遍历整个数组，而前面i为gap，只是表示从哪开始

    执行的顺序是三组轮流执行插入排序，先让4在红色组中排在正确的位置，然后是55在蓝色组中排在正确的位置，接着才是6在绿色组中排到正确的位置，依次下去。

  3. 从这个while (temp < arr[j - gap] && j > 0) {开始 才是最重要的变化

    很明显，每次应该是和自己组的比较，即原本数组里间隔gap的数temp < arr[j - gap]

  4. arr[j] = arr[j - gap]同上

  5. j -= gap同上

image-20190725185445564

对比两张图，我们就可以看到现在这个队列是大致有序的了

现在我们再把步伐降低为2

image-20190725184309474

4 -- > 6 -- > 2 -- > 11 -- > 33 -- > 55
1 -- > 10 -- > 12 -- > 8 -- > 77 -- > 99

let arr = [4, 1, 6, 10, 2, 12, 11, 8, 33, 77, 55, 99]
let gap = 2
for (let i = gap; i < arr.length; i++) {
  let j = i
  let temp = arr[j]
  while (temp < arr[j - gap] && j > 0) {
    arr[j] = arr[j - gap]
    j -= gap
  }
  arr[j] = temp
}
console.log(arr);
// [ 2, 1, 4, 8, 6, 10, 11, 12, 33, 77, 55, 99 ]

我们对这两组数组排序

2 -- > 4 -- > 6 -- > 11 -- > 33 -- > 55
1 -- > 8 -- > 10 -- > 12 -- > 77 -- > 99

image-20190725185410694

我们发现此时此时步伐3到步伐2变化已经不是很明显了，这说明了两个问题

  1. 步伐之差尽量大一点
  2. 元素离正确位置已经很近了

此时我们再来补最后一笔，

let arr = [2, 1, 4, 8, 6, 10, 11, 12, 33, 77, 55, 99]

let gap = 1
for (let i = gap; i < arr.length; i++) {
  let j = i
  let temp = arr[j]
  while (temp < arr[j - gap]) {
    arr[j] = arr[j - gap]
    j -= gap
  }
  arr[j] = temp
}
console.log(arr);
//[ 1, 2, 4, 6, 8, 10, 11, 12, 33, 55, 77, 99 ]

整个数字就完美有序了。

很明显的，上面的操作可以合成一个函数

function shellSort(arr) {
  let gap = 3
  while (gap >= 1) {
    for (let i = gap; i < arr.length; i++) {
      let j = i
      let temp = arr[i]
      while (temp < arr[j - gap] && j > 0) {
        arr[j] = arr[j - gap]
        j -= gap
      }
      arr[j] = temp
    }
    gap--
  }
  return arr
}

我们称这种排序为希尔排序。

间隔选择

我们在上面中说过，当间隔从3变为2时，变化已经不是很大了，这暗示我们一个道理，这个间隔的选择是有门道的。

如果选择这个间隔就影响到了算法的效率。

但是这个间隔贼难选，太难证明了。

当然，是不会像上面不管这个数组多长都选为3还每次减1，这个间隔一定是视数组长度决定，所以我们可以简单初始值和递减程度都这样

let gap = Math.floor(length / 2)

当然，数学家给了比较好的

function shellSort(arr) {
  let gap = 1
  while (gap < arr.length / 3) gap = 3 * gap + 1
  while (gap >= 1) {
    for (let i = gap; i < arr.length; i++) {
      let j = i
      let temp = arr[i]
      while (temp < arr[j - gap] && j > 0) {
        arr[j] = arr[j - gap]
        j -= gap
      }
      arr[j] = temp
    }
    gap = Math.floor(gap / 3)
  }
  return arr
}
console.log(shellSort([11, 2, 33, 4, 55, 6, 77]));

gap = 3 * gap + 1是一个递增数列，1，4，13，40，121，364。。。。

还有一个更快的，这里就不列了，有兴趣自己去查，平时用上面这个就够了。

效率

这个效率问题，就不像前面那么好证明了，很难。

可以知道的就是，按上面``gap = 3 * gap + 1`这种步伐的希尔排序，在最坏的情况下，比较次数和n^\frac{3}{2}成正比。

这里说的是最话的，但是此时我们已经比原来的n^2少了很多了。

而且这种排序算法的优势，体现在数组的长度上，数组越长，优势越大。

用图说话

image-20190725235940175

总结

我们为了解决插入排序存在如果排序的元素开始排序时，距离它正确的位置很远时，效率极低的痛点，通过增大步伐的灵感来解决，从而写出来希尔排序。

是不是以后就不用插入排序了呢？

答案是否定的，对于部分有序和小规模的数组我们还是应该使用插入排序的。

avatar
文章
阅读
粉丝