学习目标：
- 掌握快速排序
学习内容：
- 基本思想
- 动画演示
- 代码
- 时间复杂度
基本思想：
- 从数列中挑出一个元素，称为”基准“。
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面。
- 重复上一步，直到所有元素均排序完毕。
- 分区
动画演示:
<iframe allowfullscreen="true" data-mediaembed="csdn" frameborder="0" id="wKptnyyY-1718032705574" src="https://live.csdn.net/v/embed/397758"></iframe>快速排序
代码:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>快速排序</title>
</head>
<body>
<script>
function quick(arr) {
//4.结束递归（当arr中小于等于一项，则不用处理）
if (arr.length <= 1) {
return arr
}
//1.找到数组的中间项，在原有的数组中把它移除
let middleIndex = Math.floor(arr.length / 2)
let middleValue = arr.splice(middleIndex, 1)[0]
//2.准备左右两个数组，循环剩下数组中的每一项，比当前项小的放到左边数组中，反之，放到右边数组中
let arrLeft = [],
arrRight = []
for (let i = 0; i < arr.length; i++) {
let item = arr[i]
item < middleValue ? arrLeft.push(item) : arrRight.push(item)
}
//3.递归方式让左右两边的数组持续这样处理，一直到左右两边都排好序为止（最后让左边+中间+右边拼接成为最后的结果）
return quick(arrLeft).concat(middleValue, quick(arrRight))
}
let arr = [4, 7, 6, 5, 3, 2, 8, 1]
arr = quick(arr)
console.log(arr)
/*
// 递归：函数执行的时候自己调用自己
function fn() {
fn()//这种死递归会导致栈溢出
}
fn()
*/
/*
function fn(){
setTimeout(fn,0)//这种看似像死递归的方法不会导致栈溢出错误
}
fn()
*/
/*
//获取1-10的和
let tatal = null
for (let i = 1; i <= 10; i++) {
tatal += i
}
console.log(tatal)
*/
/*
function sum(n) {
if (n > 10) {
return 0
}
return n + sum(n + 1)
//return 1+sum(2)
// return 1+2+sum(3)
// ...
// return 1+2+3+4+5+6+7+8+9+10+sum(11)
// return 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 0
}
let tatal = sum(1)
console.log(tatal)
*/
</script>
</body>
</html>