大O表示法

在计算机中采用粗略的度量来描述计算机算法的效率，这种方法被称为“大O”表示法

在数据项个数发生改变时，算法的效率也会跟着改变。所以说算法A比算法B快两倍，这样的比较是没有意义的。

因此我们通常使用算法的速度随着数据量的变化会如何变化的方式来表示算法的效率，大O表示法就是方式之一。

符号 名称

O（1） 常数

O（log(n)） 对数

O（n） 线性

O（nlog(n)） 线性和对数乘积

O（n²） 平方

O（2ⁿ） 指数

推导大O表示法的三条规则：

规则一：用常量1取代运行时间中所有的加法常量。

规则二：运算中只保留最高阶项。如n^3 + 3n +1，大O表示法表示为：O（N^3）;

规则三：若最高阶项的常数不为1，可将其省略。如4N²，大O表示法表示为：O（N^2）;

排序算法

这里主要介绍几种简单排序和高级排序：

简单排序：冒泡排序、选择排序、插入排序；

高级排序：希尔排序、快速排序；

function ArrayList() {//属性this.array = []//方法//封装将数据插入到数组中方法ArrayList.prototype.insert = function (item) {this.array.push(item)}//toString方法ArrayList.prototype.toString = function () {return this.array.join('-')}//交换两个位置的数据ArrayList.prototype.swap = function (m, n) {let temp = this.array[m]this.array[m] = this.array[n]this.array[n] = temp}
}

冒泡排序

对未排序的各元素从头到尾依次比较相邻的两个元素大小关系，大的右移，按照这个思路，从最左端重新开始时，只需要走到倒数第二个位置即可；

两层循环：

外层循环控制冒泡趟数：

第一次：j = length - 1，比较到倒数第一个位置 ；

第二次：j = length - 2，比较到倒数第二个位置 ；

内层循环控制每趟比较的次数：

第一次比较： i = 0，比较 0 和 1 位置的两个数据；

最后一次比较：i = length - 2,比较length - 2和 length - 1两个数据；

ArrayList.prototype.bubbleSort = function () {let length = this.array.lengthfor (let i = length - 1; i > 0; i--) {for (let j = 0; j < i; j++) {if (this.array[j] > this.array[j + 1]) {this.swap(j, j + 1)}}}}

冒泡排序的效率：

上面所讲的对于7个数据项，比较次数为：6 + 5 + 4 + 3 + 2 + 1;

对于N个数据项，比较次数为：(N - 1) + (N - 2) + (N - 3) + … + 1 = N * (N - 1) / 2；如果两次比较交换一次，那么交换次数为：N * (N - 1) / 4；

使用大O表示法表示比较次数和交换次数分别为：O（ N * (N - 1) / 2）和O（ N * (N - 1) / 4），根据大O表示法的三条规则都化简为：O（N^2）;

选择排序

选择排序改进了冒泡排序：

将交换次数由O（N^2）减小到O（N）；

但是比较次数依然是O（N^2）；

选择排序的思路：

遍历一遍找到最小的，然后与首个元素替换，以此类推

两层循环：

外层循环控制指定的索引：

第一次：j = 0，指定第一个元素 ；

最后一次：j = length - 1，指定最后一个元素 ；

内层循环负责将指定索引（i）的元素与剩下（i - 1）的元素进行比较；

ArrayList.prototype.selectionSort = function () {let length = this.array.lengthlet minIndexfor (let i = 0; i < length; i++) {minIndex = ifor (let j = i + 1; j < length; j++) {if (this.array[minIndex] > this.array[j]) {minIndex = j //拿到最小的}}this.swap(minIndex, i) //进行替换}}

选择排序的效率：

选择排序的比较次数为：N * (N - 1) / 2，用大O表示法表示为：O（N^2）;

选择排序的交换次数为：(N - 1) / 2，用大O表示法表示为：O（N）;

所以选择排序的效率高于冒泡排序；

插入排序

插入排序是简单排序中效率最高的一种排序。

插入排序的思路：

首先指定一数据X（从第一个数据开始），并将数据X的左边变成局部有序状态；

随后将X右移一位，再次达到局部有序之后，继续右移一位，重复前面的操作直至X移至最后一个元素。

ArrayList.prototype.insertionSort = function () {let length = this.array.length//2.外层循环:从第二个数据开始，向左边的已经局部有序数据进行插入for (let i = 1; i < length; i++) {//3.内层循环：获取i位置的元素，使用while循环(重点)与左边的局部有序数据依次进行比较let temp = this.array[i]let j = iwhile (this.array[j - 1] > temp && j > 0) {this.array[j] = this.array[j - 1]j--}this.array[j] = temp}}

插入排序的效率：

比较次数：第一趟时，需要的最大次数为1；第二次最大为2；以此类推，最后一趟最大为N-1；所以，插入排序的总比较次数为N * (N - 1) / 2；但是，实际上每趟发现插入点之前，平均只有全体数据项的一半需要进行比较，所以比较次数为：N * (N - 1) / 4；

交换次数：指定第一个数据为X时交换0次，指定第二个数据为X最多需要交换1次，以此类推，指定第N个数据为X时最多需要交换N - 1次，所以一共需要交换N * (N - 1) / 2次，平局次数为N * (N - 1) / 2；

虽然用大O表示法表示插入排序的效率也是O（N^2），但是插入排序整体操作次数更少，因此，在简单排序中，插入排序效率最高；

希尔排序

希尔排序是插入排序的一种高效的改进版，效率比插入排序要高。

希尔排序主要通过对数据进行分组实现快速排序；

根据设定的增量（gap）将数据分为gap个组（组数等于gap），再在每个分组中进行局部排序；

ArrayList.prototype.shellSort = function () {let length = this.array.length//初始化增量let gap = Math.floor(length / 2)//第一层循环：while循环(使gap不断减小)while (gap >= 1) {//第二层循环：以gap为增量，进行分组，对分组进行插入排序   //重点为：将index = gap作为选中的第一个数据for (let i = gap; i < length; i++) {let temp = this.array[i]let j = i// 第三层循环:寻找正确的插入位置,j在分组gap范围内变化while (this.array[j - gap] > temp && j > gap - 1) {this.array[j] = this.array[j-gap]j-=gap}this.array[j] = temp}gap = Math.floor(gap/2)}}

这里解释一下上述代码中的三层循环：

• **第一层循环：**while循环，控制gap递减到1；
• **第二层循环：**分别取出根据增量gap分成的gap组数据：将index = gap的数据作为选中的第一个数据，如下图所示，gap=5，则index = gap的数据为3，index = j-gap的数据为8，两个数据为一组。随后gap不断加1右移，直到gap < length，此时实现了将数组分为5组。

• **第三层循环：**对每一组数据进行插入排序；

快速排序

快速排序的介绍：

• 快速排序可以说是目前所有排序算法中，最快的一种排序算法。当然，没有任何一种算法是在任意情况下都是最优的。但是，大多数情况下快速排序是比较好的选择。
• 快速排序其实是冒泡排序的升级版；

快速排序的核心思想是分而治之，先选出一个数据（比如65），将比其小的数据都放在它的左边，将比它大的数据都放在它的右边。这个数据称为枢纽

和冒泡排序的不同：

• 我们选择的一个数可以一次性将它放在最正确的位置，之后就不需要做任何移动；
• 而冒泡排序即使已经找到最大值，也需要继续移动最大值，直到将它移动到最右边；

快速排序的枢纽：

• **第一种方案：**直接选择第一个元素作为枢纽。但是，当第一个元素就是最小值的情况下，效率不高；
• **第二种方案：**使用随机数。随机数本身十分消耗性能，不推荐；
• 优秀的解决方法：取index为头、中、位的三个数据排序后的中位数；如下图所示，按下标值取出的三个数据为：92，31，0，经排序后变为：0，31，92，取其中的中位数31作为枢纽（当（length-1）/2不整除时可向下或向上取整）：

//交换两个位置的数据,需要传入数组
ArrayList.prototype.swap2 = function (arr, m, n) {let temp = arr[m]arr[m] = arr[n]arr[n] = temp
}
ArrayList.prototype.median = function (arr) {//1.取出中间的位置let center = Math.floor(arr.length / 2)let right = arr.length - 1let left = 0//2.判断大小并进行交换if (arr[left] > arr[center]) {this.swap2(arr, left, center)}if (arr[center] > arr[right]) {this.swap2(arr, center, right)}if (arr[left] > arr[right]) {this.swap2(arr, left, right)}//3.返回枢纽return center
}
ArrayList.prototype.quickSort = function (){this.array = this.quick(this.array)
}
ArrayList.prototype.quick = function (arr) {if (arr.length == 0) {return []}let center = this.median(arr)let c = arr.splice(center, 1)let l = []let r = []for (let i = 0; i < arr.length; i++) {if (arr[i] < c) {l.push(arr[i])} else {r.push(arr[i])}}return this.quick(l).concat(c, this.quick(r)) //合并
}

快速排序的效率：

• 快速排序最坏情况下的效率：每次选择的枢纽都是最左边或最右边的数据，此时效率等同于冒泡排序，时间复杂度为O（n²）。可根据不同的枢纽选择避免这一情况；
• 快速排序的平均效率：为O（N*logN），虽然其他算法效率也可达到O（N*logN），但是其中快速排序是最好的。

参考文献：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
大量摘抄自：https://www.cnblogs.com/AhuntSun-blog/p/12529656.html
结合以上进行修改