大O表示法：
常见的大O表示形式
| 符号 | 名称 |
|---|---|
| O（1） | 常数 |
| O（log(n)） | 对数 |
| O（n） | 线性 |
| O（nlog(n)） | 线性和对数乘积 |
| O（n2） | 平方 |
| O（2^n^） | 指数 |
不同大O形式的时间复杂度：
可以看到效率从大到小分别是：O（1）> O（logn）> O（n）> O（nlog(n)）> O（n2）> O（2^n^）
推导大O表示法的三条规则：
这里主要介绍几种简单排序和高级排序：
此处创建一个列表类ArrayList并添加一些属性和方法，用于存放这些排序方法：
//创建列表类
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
}冒泡排序的思路：
实现思路：
两层循环：
详细过程如下图所示：
动态过程：
代码实现：
//冒泡排序
ArrayList.prototype.bubblesor = function(){
//1.获取数组的长度
let length = this.array.length
//外层循环控制冒泡趟数
for(let j = length - 1; j >= 0; j--){
//内层循环控制每趟比较的次数
for(let i = 0; i < j; i++){
if (this.array[i] > this.array[i+1]) {
//交换两个数据
let temp = this.array[i]
this.array[i] = this.array[i+1]
this.array[i+1] = temp
}
}
}
}测试代码：
//测试类
let list = new ArrayList()
//插入元素
list.insert(66)
list.insert(88)
list.insert(12)
list.insert(87)
list.insert(100)
list.insert(5)
list.insert(566)
list.insert(23)
//验证冒泡排序
list.bubblesor()
console.log(list);测试结果：
冒泡排序的效率：
选择排序改进了冒泡排序：
选择排序的思路：
实现思路：
两层循环：
动态过程：
代码实现：
//选择排序
ArrayList.prototype.selectionSort = function(){
//1.获取数组的长度
let length = this.array.length
//2.外层循环：从0开始获取元素
for(let j = 0; j < length - 1; j++){
let min = j
//内层循环：从i+1位置开始，和后面的元素进行比较
for(let i = min + 1; i < length; i++){
if (this.array[min] > this.array[i]) {
min = i
}
}
this.swap(min, j)
}
}测试代码：
//测试类
let list = new ArrayList()
//插入元素
list.insert(66)
list.insert(88)
list.insert(12)
list.insert(87)
list.insert(100)
list.insert(5)
list.insert(566)
list.insert(23)
//验证选择排序
list.selectionSort()
console.log(list);测试结果：
选择排序的效率：
插入排序是简单排序中效率最高的一种排序。
插入排序的思路：
插入排序的详细过程：
动态过程：
代码实现：
//插入排序
ArrayList.prototype.insertionSort = function(){
//1.获取数组的长度
let length = this.array.length
//2.外层循环:从第二个数据开始，向左边的已经局部有序数据进行插入
for(let i = 1; i < length; i++){
//3.内层循环：获取i位置的元素，使用while循环(重点)与左边的局部有序数据依次进行比较
let temp = this.array[i]
let j = i
while(this.array[j - 1] > temp && j > 0){
this.array[j] = this.array[j - 1]//大的数据右移
j--
}
//4.while循环结束后，index = j左边的数据变为局部有序且array[j]最大。此时将array[j]重置为排序前的数据array[i]，方便下一次for循环
this.array[j] = temp
}
}测试代码：
//测试类
let list = new ArrayList()
//插入元素
list.insert(66)
list.insert(88)
list.insert(12)
list.insert(87)
list.insert(100)
list.insert(5)
list.insert(566)
list.insert(23)
// console.log(list);
//验证插入排序
list.insertionSort()
console.log(list);测试结果：
插入排序的效率：
比较次数：第一趟时，需要的最大次数为1；第二次最大为2；以此类推，最后一趟最大为N-1；所以，插入排序的总比较次数为N * (N - 1) / 2；但是，实际上每趟发现插入点之前，平均只有全体数据项的一半需要进行比较，所以比较次数为：N * (N - 1) / 4；
虽然用大O表示法表示插入排序的效率也是O（N^2），但是插入排序整体操作次数更少，因此，在简单排序中，插入排序效率最高；
希尔排序是插入排序的一种高效的改进版，效率比插入排序要高。
希尔排序的历史背景：
的意义，用Shell来命名该算法；
插入排序的问题：
希尔排序的实现思路：
假如有数组有10个数据，第1个数据为黑色，增量为5。那么第二个为黑色的数据index=5，第3个数据为黑色的数据index = 10（不存在）。所以黑色的数据每组只有2个，10 / 2 = 5一共可分5组，即组数等于增量gap。
具体过程如下：
动态过程：
图中d表示增量gap。
增量的选择：
以下代码实现中采用希尔排序原稿中建议的增量即N / 2 。
代码实现：
//希尔排序
ArrayList.prototype.shellSort = function(){
//1.获取数组的长度
let length = this.array.length
//2.初始化增量
let gap = Math.floor(length / 2)
//3.第一层循环：while循环(使gap不断减小)
while(gap >= 1 ){
//4.第二层循环：以gap为增量，进行分组，对分组进行插入排序
//重点为：将index = gap作为选中的第一个数据
for(let i = gap; i < length; i++){
let temp = this.array[i]
let j = i
//5.第三层循环:寻找正确的插入位置
while(this.array[j - gap] > temp && j > gap - 1){
this.array[j] = this.array[j - gap]
j -= gap
}
//6.将j位置的元素设置为temp
this.array[j] = temp
}
gap = Math.floor(gap / 2)
}
}这里解释一下上述代码中的三层循环：
测试代码：
//测试类
let list = new ArrayList()
//插入元素
list.insert(66)
list.insert(88)
list.insert(12)
list.insert(87)
list.insert(100)
list.insert(5)
list.insert(566)
list.insert(23)
// console.log(list);
//验证希尔排序
list.shellSort()
console.log(list);测试结果：
希尔排序的效率：
快速排序的介绍：
快速排序可以说是目前所有排序算法中，最快的一种排序算法。当然，没有任何一种算法是在任意情况下都是最优的。但是，大多数情况下快速排序是比较好的选择。
快速排序其实是冒泡排序的升级版；
快速排序的核心思想是分而治之，先选出一个数据（比如65），将比其小的数据都放在它的左边，将比它大的数据都放在它的右边。这个数据称为枢纽
和冒泡排序的不同：
快速排序的枢纽：
实现枢纽选择：
//交换两个位置的数据
let swap = function(arr, m, n){
let temp = arr[m]
arr[m] = arr[n]
arr[n] = temp
}
//快速排序
//1.选择枢纽
let median = function(arr){
//1.取出中间的位置
let center = Math.floor(arr.length / 2)
let right = arr.length - 1
let left = 0
//2.判断大小并进行交换
if (arr[left] > arr[center]) {
swap(arr, left, center)
}
if (arr[center] > arr[right]){
swap(arr, center, right)
}
if (arr[left] > arr[right]) {
swap(arr, left, right)
}
//3.返回枢纽
return center
}数组经过获取枢纽函数操作之后，选出的3个下标值对应的数据位置变为：
动态过程：
快速排序代码实现：
//2.快速排序
let QuickSort = function(arr){
if (arr.length == 0) {
return []
}
let center = 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 QuickSort(l).concat(c, QuickSort(r))
}算法的巧妙之处在于通过:
QuickSort(l).concat(c, QuickSort(r))递归调用QuickSort函数实现了枢纽Center左边数据l和右边数据r的排序；
测试代码：
let arr = [0, 13, 81, 43, 31, 27, 56, 92]
console.log(QuickSort(arr));测试结果
快速排序的效率：
参考资料：JavaScript数据结构与算法
原文：https://www.cnblogs.com/AhuntSun-blog/p/12529656.html