目录
一. 希尔排序
1.希尔排序的介绍
(1).希尔排序的历史背景
(2).插入排序的问题
(3).希尔排序的做法
(4).选择合适的增量
2.希尔排序的实现
3.希尔排序的效率
(1).希尔排序的效率
(2).Hibbard 增量序列
(3).Sedgewick增量序列
二、快速排序
1.快速排序的介绍
(1).快速排序的重要性
(2).快速排序是什么
(3).快速排序的思想
2.快速排序的枢纽
3.快速排序的实现
4.快速排序的效率
(1).快速排序的最坏情况效率
(2).快速排序的平均效率
希尔排序是插入排序的一种改进版，效率比插入排序要更快。
希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。优先的排序算法首要条件就是速度，在简单排序出现后的很多一段时间内，人们发明了各种各样的算法，但是最终发现算法的时间复杂度都是O(N²)，似乎没法超越了。此时，计算机学术界充斥着"排序算法不可能突破O(N²)"的声音。终于有一天，一位科学家发布超越了O(N²)的新排序算法(后来为了纪念这个里程碑，用Shell来命名了该算法)。
假设一个很小的数据项在很靠近右端的位置上，这里本来应该是较大的数据项的位置。把这个小数据项移动到左边的正确位置，所有的中间数据项都必须向右移动一位。如果每个步骤对数据项都进行N次复制，平均下来是移动N/2，N个元素就是 N*N/2 = N²/2。通常认为插入排序的效率是O(N²)。
比如上面的数字, 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15。
先让间隔为5进行排序. (81, 35, 41), (94, 17, 75), (11, 95, 15), (96, 28), (12, 58)
排序后的新序列, 一定可以让数字离正确位置更近一步。
再让间隔位3进行排序. (35, 28, 75, 58, 95), (17, 12, 15, 81), (11, 41, 96, 94)
排序后的新序列, 一定可以让数字离自己的正确位置又近了一步。
最后，让间隔为1，也就是正确的插入排序。这个时候数字都离自己的正确位置更近，那么需要复制的次数就会减少很多。
在希尔排序的原稿中建议的初始间距是N / 2，简单的把每一回排序分成两半。也就是说，对于N = 100的数组，增量间隔序列为： 50, 25, 12, 6, 3, 1。这个方法的好处是不需要在开始排序前为找合适的增量而进行任何的计算
//希尔排序
ArrayList.prototype.shellSort = function () {
//1.获取数组长度
var length = this.array.length
//2.初始化的增量
var gap = Math.floor(length / 2)
//3.while循环（gap不断的减小）
while (gap >= 1) {
//4.以gap作为间隔，进行分组，对分组进行插入排序
for (var i = 0; i < length; i++) {
var temp = this.array[i]
var j = i
while (this.array[j - gap] > temp && j > gap - 1) {
this.array[j] = this.array[j - gap]
j -= gap
}
//5.将j位置的元素赋值temp
this.array[j] = temp
}
gap = Math.floor(gap / 2)
}
}
希尔排序的效率与增量是有关系的。但是，它的效率证明非常困难，甚至某些增量的效率到目前依然没有被证明出来。但是经过统计，希尔排序使用原始增量，最坏的情况下时间复杂度为O(N²)，通常情况下都要好于O(N²)
增量的算法为2^k - 1，也就是为1 3 5 7...等等。这种增量的最坏复杂度为O(N^3/2), 猜想的平均复杂度为O(N^5/4)，目前尚未被证明。
增量序列为{1, 5, 19, 41, 109, … }，该序列中的项是94^i - 9*2^i + 1或者是4^i - 32^i + 1
这种增量的最坏复杂度为O(N^4/3)，平均复杂度为O(N^7/6)，但是均未被证明.
使用希尔排序大多数情况下效率都高于简单排序, 甚至在合适的增量和N的情况下, 还好于快速排序.
快速排序可以说是排序算法中最常见的，也被列为20世纪十大算法之一。快速排序几乎可以说是目前所有排序算法中最快的一种排序算法。当然, 没有任何一种算法是在任意情况下都是最优的, 比如希尔排序确实在某些情况下可能好于快速排序。但是大多数情况下，快速排序还是比较好的选择。
希尔排序相当于插入排序的升级版，快速排序其实也是冒泡排序的升级版。冒泡排序需要经过很多次交换，才能在一次循环中，将最大值放在正确的位置上。而快速排序可以在一次循环中(其实是递归调用)找出某个元素的正确位置，并且该元素之后不需要任何移动。
快速排序最重要的思想是分而治之。
如上图有这样一些数字需要排序：
第一步: 从其中选出了65。(可以是选出任意的数字)
第二步: 将所有小于65的数字放在65的左边，将所有大于65的数字放在65的右边。
第三步: 递归处理左边的数据，递归的处理右边的数据。
第四步: 排序完成
快速排序中有一个很重要的步骤就是选取枢纽。
选取最合适的枢纽：
一种方案是直接选择第一个元素作为枢纽。但第一个作为枢纽在某些情况下，效率并不是特别高。
另一种方案是使用随机数，随机取 pivot，但是随机函数是一个耗性能的操作。
另一种比较优秀的解决方案是：取头、中、尾的中位数。例如 8、12、3的中位数就是8。
枢纽选择的代码实现:
//1.选择枢纽
ArrayList.prototype.median = function (left, right) {
//1.取出中间的位置
var center = Math.floor((left + right) / 2)
//2.判断大小，并进行交换
if (this.array[left] > this.array[center]) {
this.swap(left, center)
}
if (this.array[left] > this.array[right]) {
this.swap(left, right)
}
if (this.array[center] > this.array[right]) {
this.swap(center, right)
}
//3.将center换到right-1的位置
this.swap(center, right - 1)
return this.array[right - 1]
}
//2.代码实现
ArrayList.prototype.quickSort = function(){
this.quick(0,this.array.length-1)
}
ArrayList.prototype.quick = function (left, right) {
//1.结束条件
if (left >= right) return
//2.获取枢纽
var pivot = this.median(left, right)
//3.定义变量
var i = left
var j = right - 1
//4.开始进行交换
while (i!=j) {
while (this.array[++i] < pivot) { }
while (this.array[--j] > pivot) { }
if (i < j) {
this.swap(i, j)
} else {
break
}
}
//5.将枢纽放到正确的位置，i的位置
this.swap(i, right - 1)
//6.分而治之
this.quick(left, i - 1)
this.quick(i + 1, right)
}
快速排序最坏的效率就是每次选择的枢纽都是最左边或者最后边的。那么效率等同于冒泡排序。
快速排序的平均效率是O(N * logN).