算法（第四版）（持续更新）

排序的复杂度

1.比较次数
2.交换次数
排序算法的三大实际意义
1.对排序算法的分析有助于全面理解本书中比较算法的性能的方法。
2.类似的技术也能有效地解决其他问题的第一步。
3.排序算法常常是我们解决其他问题的第一步。

1.选择排序

1.原理

选择排序的内循环只是在比较当前元素与已知元素的最小元素以及是否越界，交换元素的代码写在内循环之外因此交换的总次数为N次。所以效率取决于比较的次数。
选择排序需要大约N^2/2(n(n-1)/2)次比较和N次交换。

2.特点

数据移动是最少的，每次交换都会改变两个数组的值，因此选择排序用了N次交换，交换次数和数组的大小是线性关系。大部分的增长数量级都是线性对数或是平方级别。
外层交换是N次，内层交换取决于数据的多少以及排列方式。

时间复杂度

1
2
3

平均时间:O(n^2)
最好时间:O(n^2)
最长时间:O(n^2)

空间复杂度

1	O(1)，因为需要一个临时变量交换元素位置

示例

let arr=[10,6,4,3,8,1,2,5,7,9];
for(let i=0;i<arr.length;i++){
    for(let j=i+1;j<arr.length;j++){
        if(arr[j]<arr[i]){
            let temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
    }
}

2.插入排序

1.原理

将一个待排序的记录，按照其关键字的大小将其插入到前边已经排好序的子序列的适当位置，直到全部插入完毕。

2.特点

对于随机排列的长度为N且主检不重复的情况下，平均情况插入排序需要N^2/4次比对，需要N^2/4次交换。最坏的情况是N^2次比较和N^2次交换，最好是需要N-1次比较和0次交换

let arr=[10,6,4,3,8,1,2,5,7,9];
for(let i=1;i<arr.length;i++){
    for(let j=i;j>0;j--){
        if(arr[j]>arr[j-1]){
            break;
        }
        let temp=arr[j];
        arr[j]=arr[j-1];
        arr[j-1]=temp;
    }
}

时间复杂度

1
2
3

平均时间:O(n^2)
最好时间:O(n)
最长时间:O(n^2)

空间复杂度

1	O(1),因为需要一个临时变量交换元素位置

插入排序和选择排序比较

可视化比较图

1.为什么插入排序最差也要比选择排序要快

1.首先选择排序的比较次数是固定的 n(n-1)/2
2.插入排序平均下来是 n(n-1)/4 因为比较比他小的时候就可以不用再比较了。
3.选择排序的比较开销是固定的而插入排序比较开销是动态可变的，节约比较开销就是插入排序比选择排序要快的原因所在。

3.希尔排序（一种插入排序的快速排序方法）

1.特点

希尔排序是基于插入排序的一个快速排序方法，对于大规模的乱序数组插入排序很慢。如果最小的数字在最后面就需要N-1次移动。
交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。一个h有序数组就是h个互相独立的有序数组编织再一起组成的一个数组。
希尔排序的更高效的原因是它权衡了子数组的规模和有序性
希尔排序的核心就是通过不同的增量了对分组进行分组然后插入排序

2.复杂度

时间复杂度
1
平均时间:O(n^1.25)

空间复杂度

1	O(1),因为需要一个临时变量交换元素位置

3.示例

例子

let arr=[11,10,9,8,7,6,5,4,3,2,1]
let h=Math.floor(arr.length/2);

while(h>=1){
    for(let i=h;i<arr.length;i++){
        for(let j=i;j>=h&&(arr[j-h]>arr[j]);j-=h){
            let temp=arr[j];
            arr[j]=arr[j-h];
            arr[j-h]=temp
        }
    }
    h=Math.floor(h/2)
}
// 当增量为2的时候的值为

[ 9, 10, 11, 8, 7, 6, 5, 4, 3, 2, 1 ] 第一次交换是[9,11]
[ 9, 8, 11, 10, 7, 6, 5, 4, 3, 2, 1 ] 第二次交换是[8,10]
[ 9, 8, 7, 10, 11, 6, 5, 4, 3, 2, 1 ] 第三次交换式[7,11]
[ 7, 8, 9, 10, 11, 6, 5, 4, 3, 2, 1 ] 第四次交换是[7,9]
备注第三次和第四次外层循环为一层循环 后面的一次类推
[ 7, 8, 9, 6, 11, 10, 5, 4, 3, 2, 1 ]
[ 7, 6, 9, 8, 11, 10, 5, 4, 3, 2, 1 ]
[ 7, 6, 9, 8, 5, 10, 11, 4, 3, 2, 1 ]
[ 7, 6, 5, 8, 9, 10, 11, 4, 3, 2, 1 ]
[ 5, 6, 7, 8, 9, 10, 11, 4, 3, 2, 1 ]
[ 5, 6, 7, 8, 9, 4, 11, 10, 3, 2, 1 ]
[ 5, 6, 7, 4, 9, 8, 11, 10, 3, 2, 1 ]
[ 5, 4, 7, 6, 9, 8, 11, 10, 3, 2, 1 ]
[ 5, 4, 7, 6, 9, 8, 3, 10, 11, 2, 1 ]
[ 5, 4, 7, 6, 3, 8, 9, 10, 11, 2, 1 ]
[ 5, 4, 3, 6, 7, 8, 9, 10, 11, 2, 1 ]
[ 3, 4, 5, 6, 7, 8, 9, 10, 11, 2, 1 ]
[ 3, 4, 5, 6, 7, 8, 9, 2, 11, 10, 1 ]
[ 3, 4, 5, 6, 7, 2, 9, 8, 11, 10, 1 ]
[ 3, 4, 5, 2, 7, 6, 9, 8, 11, 10, 1 ]
[ 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 1 ]
[ 3, 2, 5, 4, 7, 6, 9, 8, 1, 10, 11 ]
[ 3, 2, 5, 4, 7, 6, 1, 8, 9, 10, 11 ]
[ 3, 2, 5, 4, 1, 6, 7, 8, 9, 10, 11 ]
[ 3, 2, 1, 4, 5, 6, 7, 8, 9, 10, 11 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]

2.希尔排序与插入排序的区别

1.插入排序是两两比较如果最小值在最后面就需要比较以及交换n-1次才能到最前面
2.希尔排序通过增量来实现分组排序相同间隔为h的数组进行排序
3.希尔排序有时候比较适用于大量数组，因为和其他排序比较他的运行时间可以接受以及代码量比较小

4.归并排序

将两个有序的数组归并成一个更大的有序数组。是
一种简单的递归排序，归并排序。
要将一个数组排序，可以先递归将它分成两半分别排序，然后结果归并起来。

1.优点

能够保证将任意长度为N的数组排序所需时间和NlogN成正比，排序后，相同值之间的相对位置顺序不被改变

2.缺点

它所需的额外空间和N成正比。

3.方法

1.递归法

1.申请空间，使其大小为两个已经排列序列之和，该空间用来存放合并的序列。
2.设定两个指针，最初的位置分别为两个已经排列序列的起始位置。
3.比较两个指针所指向的元素，选择相对较小的元素放入到合并空间，并移动指针到下一个位置
4.重复步骤3直到某一指针到达序列尾。
5.将另一序列剩下的所有元素直接复制到合并序列尾。

2.迭代法

1.将序列每相邻两个数字进行归并操作，形成ceil(n/2)，排序后每个包含两/一个元素
2.若此时序列不是一个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
3.重复步骤2，直到所有元素排列完毕，即序列书为1

4.复杂度

时间复杂度

平均时间:O(nlogn)
最好时间:O(nlogn)
最长时间:O(nlogn)

总时间=分解时间+解决问题时间+合并时间。分解时间就是把一个待排序序列分解成两序列，时间为一常数，时间复杂度o(1).解决问题时间是两个递归式，把一个规模为n的问题分成两个规模分别为n/2的子问题，时间为2T(n/2).合并时间复杂度为o（n）。总时间T(n)=2T(n/2)+o(n).这个递归式可以用递归树来解，其解是o(nlogn)。

空间复杂度

O(1),因为需要一个临时变量交换元素位置
````


## 4.递归法代码示例

let arr=[11,10,9,8,7,6,5,4,3,2,1];
const mergeSort=(arr)=>{
const merge=(left,right)=>{

  let final=[];
  while(left.length>0&&right.length>0){
      if(left[0]<right[0]){
          final.push(left.shift());
      }else{
          final.push(right.shift());
      }
  }
  return final.concat(left).concat(right)

}
let len=arr.length;
if(len<2){

  return arr;

}
let mid=Math.floor(len/2);
return merge(mergeSort(arr.slice(0,mid)),mergeSort(arr.slice(mid)))
}
console.log(mergeSort(arr))


- 递归算法的个人理解

<img src='https://dpq123456-1256164122.cos.ap-beijing.myqcloud.com/%E6%95%B0%E6%8D%AE%E7%AE%97%E6%B3%95/%E5%BD%92%E5%B9%B6%E7%AE%97%E6%B3%95%E9%80%92%E5%BD%92%E7%90%86%E8%A7%A3%E5%9B%BE.png' width=200/>

<img src='https://dpq123456-1256164122.cos.ap-beijing.myqcloud.com/%E6%95%B0%E6%8D%AE%E7%AE%97%E6%B3%95/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E9%80%92%E5%BD%92%E5%AE%9E%E7%8E%B0%20%E7%94%BB%E5%9B%BE.jpg' width=400/>

<img src='https://dpq123456-1256164122.cos.ap-beijing.myqcloud.com/%E6%95%B0%E6%8D%AE%E7%AE%97%E6%B3%95/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F%E7%A4%BA%E4%BE%8B%E5%9B%BE.gif' width=200/>

# 5.快速排序

- 应用最广泛的一种排序算法，主要特点是实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快很多。也是用分治法，与归并排序呈互补关系。

## 1.特点
- 原地排序（只需要一个很小的辅助栈）

## 2.复杂度
- 时间复杂度

平均时间：O(nlogn)
最好时间：O(nlogn)
最坏时间：O(n^2)

1
2


- 空间复杂度

logn，因为递归调用了。




## 3.示例

<img src='https://dpq123456-1256164122.cos.ap-beijing.myqcloud.com/%E6%95%B0%E6%8D%AE%E7%AE%97%E6%B3%95/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%A4%BA%E4%BE%8B%E5%9B%BE.png' height=400/>


- 递归代码示例

const quickSort=(arr)=>{
let len=arr.length;
if(len<2){

  return arr;

}
let left=[];
let right=[];
let basic=arr[0];
for(let i=1;i<len;i++){

  if(arr[i]<basic){
      left.push(arr[i]);
  }else{
      right.push(arr[i])
  }

}
return quickSort(left).concat(basic,quickSort(right))
}

如有侵权行为，请点击这里联系我删除

如发现疑问或者错误点击反馈

Shayne Wang

About

算法（第四版）整理

算法（第四版）（持续更新）

排序的复杂度

排序算法的三大实际意义

1.选择排序

1.原理

2.特点

2.插入排序

1.原理

2.特点

插入排序和选择排序比较

1.为什么插入排序最差也要比选择排序要快

3.希尔排序（一种插入排序的快速排序方法）

1.特点

2.复杂度

3.示例

2.希尔排序与插入排序的区别

4.归并排序

1.优点

2.缺点

3.方法

1.递归法

2.迭代法

4.复杂度

备注