用来描述计算机算法的效率，
数据项个数发生变化时，算法的效率也会跟着发生改变
| 符号 | 名称 |
|---|---|
| o(1) | 常数的 |
| o(log(n)) | 对数的 |
| o(n) | 线性的 |
| o(nlog(n)) | 线性和对数乘积 |
| o($n^2$) | 平方 |
| o($2^n$) | 指数的 |
当我们写一个算法的时候，其运行过程，并不是完全跟上面例子相同，它可能是个多项式，我们可以通过一些推导得出它们的大o表示法
1、用常量1取代运行时间中所有的加法常量
2、在修改后的运行次数函数中，只保留最高阶项
3、如果最高存在且不为1，则去除与这个项相乘的常数
举例
1、如果得出的是一个常量，可以直接用上面第一条比如：76 用大o表示就是o(1)
2、如果得出的是多项式，比如：2n$^2$ + 3n + 1，根据上面第二条就等于 2n$^2$再根据第三条就等于o(n$^2$)
注意: 如果你在面试中不知道写什么排序算法好，尽可能写快速排序算法，在大部分情况下，快速排序是效率最高的
排序算法有很多例如：冒泡、选择、插入、归并、计数、基数、希尔、堆、桶。
用三个简单排序和两个高级排序进行实例。
1、对未排序的的各个元素从头到尾依次比较相邻的两个元素大小关系
2、如果左边比右边的高，则两者交换位置
3、向右移动一个位置，比较后面两个
4、当走到最右边的时候，最高的一定被放在了最右边
5、按照这个思路，从左端重新开始，这次走到倒数第二个位置即可
6、依次类推就可以将数据排序完成
我要评论// 封装arraylist
function arraylist() {
this.array = []
arraylist.prototype.insert = function (item) {
this.array.push(item)
}
arraylist.prototype.tostring = function () {
return this.array.join()
}
}
// 交换位置函数
arraylist.prototype.swap = function (m, n) {
var temp = this.array[m]
this.array[m] = this.array[n]
this.array[n] = temp
}
arraylist.prototype.bubblesort = function () {
// 1.获取数组的长度
var length = this.array.length
// 2.反向循环, 因此次数越来越少
for (var i = length - 1; i >= 0; i--) {
// 3.根据i的次数, 比较循环到i位置
for (var j = 0; j < i; j++) {
// 4.如果j位置比j+1位置的数据大, 那么就交换
if (this.array[j] > this.array[j+1]) {
// 交换
this.swap(j, j+1)
}
}
}
}
是（n-1）+（n-2）+（n-3）+…+1 = n*(n-1)/2
推导成大o表示法n*(n-1)/2 = n$^2$/2-n/2，根据规则二变成n$^2$/2再根据规则三变成n$^2$
因此冒泡排序的比较次数大o表示法是o(n$^2$)
是n*(n-1)/2（比较次数）／2结果是交换的次数，为什么除以2是因为如果有两次比较才需要交换一次（不可能每次比较都需要交换一次），那么就需要在比较次数的基础上再除以2，由于常量不包含在大o表示法中，因此我们可以认为交换次数的大o表示法也是o(n$^2$)
选择排序改进了冒泡排序，将交换次数由o(n$^2$)减少到了o(n)
但是比较次数依然是o(n$^2$)
1、选定第一个索引位置，然后和后面的元素依次比较
2、如果后面的项，小于第一个索引位置的项，则与第一个交换位置
3、经过第一轮的比较后，可以确定第一个位置的项是最小的
4、然后用同样的方式把剩下的项逐个比较
5、选择排序，第一轮会选出第一小的值，第二轮会选出第二小的值，直到最后
arraylist.prototype.selectionsort = function () {
// 1.获取数组的长度
var length = this.array.length
// 2.外层循环: 从0位置开始取出数据, 直到length-2位置
for (var i = 0; i < length - 1; i++) {
// 3.内层循环: 从i+1位置开始, 和后面的内容比较
var min = i
for (var j = min + 1; j < length; j++) {
// 4.如果i位置的数据大于j位置的数据, 记录最小的位置
if (this.array[min] > this.array[j]) {
min = j
}
}
this.swap(min, i)
}
}
和冒泡排序的相同都是n*(n-1)/2
因此选择排序的比较次数大o表示法也是o(n$^2$)
选择排序每次进行选择的时候，最多需要交换一次，一共遍历了n-1次
所以选择排序的交换次数用大o表示法是o(n)，所以选择排序在效率上通常是被认为高于冒泡排序的
插入排序是简单排序中效率最好的
1、插入排序的核心思想是局部有序
2、局部有序就好比一个队列中，我们选了一个作为标记的成员
3、被标记的左边成员已经是局部有序的
4、这意味着，有一部分人是按照顺序排列好的，有一部分人还是没有顺序
1、从第一个元素开始，该元素可以被认为已经被排序
2、取出下一个元素，在已经排序的队列中从后向前扫描
3、如果该元素（已排序）的大于新元素，将该元素移到下一个位置
4、重复第三步骤，直到已经找到已排序的元素小于或者等于新元素的位置
5、将新元素插入到该位置后，再重复上列步骤
arraylist.prototype.insertionsort = function () {
//获取数据长度
var length = this.arr.length;
// 第一次循环直接从第二项开始，第一项默认为已排序，结尾是长度-1项
for(var i = 1;i<length;i++){
// 因为不断访问要插入的项，所以把它保存起来，方便逐个和已排序对比
var temp = this.arr[i];
// 由于要从i-1项不断往前找，先把i备份成j，通过操作j来不断向前
var j = i;
// 第一次获取到前面一项做对比，如果前面的小于要插入的，j不能为0，不然会访问到-1项
while(this.arr[j-1]>temp && j>0){
// 如果大于，就让当前项等于数组前一个项
// 当前项不会丢失，已经保存在temp
this.arr[j] = this.arr[j-1]
// 再将j递减，这样可以在已排序数组中把位置向前移动
j--
}
// 小于要插入的，直接重新赋值到当前项
this.arr[j] = temp
}
}
1、第一趟时需要的最多次数是1，第二趟时需要的是2，依次类推最后一趟是n-1次
2、因此插入排序的最多次是：1+2+3+...+n-1 = n *(n-1)/2
3、然而每趟发现插入点的之前，平均只有全体数据项的一半需要进行比较
4、我们可以再除以2得到 n *(n-1)/4，所以相对于选择排序，其比较次数是少了一半的
1、第一趟时，需要的最多复制次数是1，第二趟最多的复制次数是2，依次类推，最后一趟是n-1次
2、因此复制次数最多是1+2+3+...+n-1=n *(n-1)/2
3、平均次数n *(n-1)/4
希尔排序是插入排序的一种改进版，速度更快了，他主要采用了一种分组的方式
希尔排序的核心就是将数据进行分组，但不是按顺序等量分组，而是
1、设置一个间隔数，例如间隔数是3那么,[n,n+3]是一组，[n+1,n+3+1]是一组
2、将所有数据都分好组后，让他们组内进行排序
3、排好序后，数值肯定离自己正确位置很近了，然后不断缩短间隔数，
4、直到间隔数为1，就是插入排序所执行的逻辑了
上面的间隔数值是我们举例的，那么到底选择多少合适呢？
1、选择合适的增量
2、hibbard增量排序
3、sedgewick增量排序
这里我们使用上面的第一种
arraylist.prototype.shellsort = function () {
// 1、获取数组长度
var length = this.array.length
// 2、获取初次间隔值，防止小数出现，使用floor
var gap = math.floor(length / 2)
// 3、如果间隔值小于1了就停止，
// 最后一次等于1的时候就跟插入排序执行的一样了
while (gap >=1) {
// 4、实现插入排序，起始点是间隔的位置，比如是5，就是数组中下标为5的
for (var i = gap; i < length; i++) {
// 保存间隔的位置数
var j = i
// 保存间隔位置的值
var temp = this.array[i]
// 5、寻找合适位置
// 第一个判断语句是防止溢出左侧，
// 第二个判断语句是左侧的上一个间隔位置的值，需要大于当前的
while (j > gap - 1 && this.array[j - gap] > temp) {
// 如果大于，就让左侧上一个间隔位置的值移动到当前位置
this.array[j] = this.array[j - gap]
// 就让j值等于原来左侧上一个间隔位置的值
j -= gap
}
// 如果不大于还是保存在原来的位置
// 6、最后将间隔的位置值插入到j，也就是属于他的合适位置
this.array[j] = temp
}
// 7、缩小间隔值，直到等于1
gap = math.floor(gap / 2)
}
}
1、希尔排序的效率跟增量是有关系的
2、它的效率证明非常困难
3、但是经过统计，最坏的情况下时间复杂度为o(n$^2$)，通常情况下都是要好于o(n$^2$)
4、在合适的增量和某些数量n的情况下，还要好于快速排序。
快速排序几乎可以说是所有排序中速度最快的，它可以在一次循环中(其实是递归调用)，找出某个元素的正确位置，并且该元素之后不需要任何移动
1、但是，没有一种算法是在任意情况下都是最优的
2、希尔排序在特定情况下要快于快速排序
3、但是快速排序在大多数情况下都是要快于希尔排序的
比如我们有这样一组数据[13，81，92，43，65，34，57，26，75，6]
1、我们从其中选出了65，(也可以是其他任意数字)
2、通过算法，将所有小于65的放到65左边，大于65的放到65的右边
3、再递归处理左边的数据，(比如从左边选了31来处理左侧)，递归处理右边的数据(比如选了75来处理,但是选81可能最合适，因为就不用再往右边放了）
4、就这样通过不断的递归处理，完成排序
上面选择的65，31，75或者81就是枢纽
怎么样才能选择合适的枢纽呢
我们可以取数组的头，中，尾的中位数
7，4，5，8，9选出来的就是7，5，9，排好序就是5，7，9中位数就是7
// 位置交换函数
arraylist.prototype.swap = function (m, n) {
var temp = this.array[m]
this.array[m] = this.array[n]
this.array[n] = temp
}
// 选择枢纽
arraylist.prototype.median = function (left, right) {
// 1.求出中间的位置，以防有小数点，所以使用floor
var center = math.floor((left + right) / 2)
// 2.判断并且进行交换
if (this.array[left] > this.array[center]) {
this.swap(left, center)
}
if (this.array[center] > this.array[right]) {
this.swap(center, right)
}
if (this.array[left] > this.array[right]) {
this.swap(left, right)
}
// 3.巧妙的操作: 将center移动到right - 1的位置.
// 这样方便我们循环只对左侧数据进行操作
this.swap(center, right - 1)
// 4.返回枢纽
return this.array[right - 1]
}
// 快速排序实现
arraylist.prototype.quicksort = function () {
this.quicksortrec(0, this.array.length - 1)
}
arraylist.prototype.quicksortrec = function (left, right) {
// 0.递归结束条件，对比的值超出了边界值，比如下标为length或者下标为-1了
if (left >= right) return
// 1.获取枢纽
var pivot = this.median(left, right)
// 2.开始进行交换,保存两个对比的下标值
var i = left
var j = right - 1
while (true) {
// 不断改变i的值
while (this.array[++i] < pivot) { }
// 不断改变j的值
while (this.array[--j] > pivot) { }
// i和j表示的是下标值
if (i < j) {
this.swap(i, j)
} else {
// 如果i>=j了表示已经溢出了，所以直接break
break
}
}
// 3.将枢纽放在正确的位置
this.swap(i, right - 1)
// 4.递归调用左边
this.quicksortrec(left, i - 1)
// 5.递归调用右边
this.quicksortrec(i + 1, right)
}
1、如果每次选择的枢纽都是最左边或者最右边的时候效率最差
2、那么效率等同于冒泡排序
3、而我们的例子中不会有最坏情况，因为我们选的是三个值的中位值
1、快速排序的平均效率是o(n*logn)
2、虽然其他某些算法的效率也可以达到o(n*logn)，但是快速排序是最好的
注释是本人加的，可能并不是那么通俗易懂，如果有产生误导，可删除注释自行调试代码，如有问题，欢迎评论或者使用邮件与我联系
如对本文有疑问， 点击进行留言回复！！
vue源码实战render.js与$nextTick的异步调用
网友评论