快速排序算法JS封装
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
</head>
<body>
<script>
/
/快速排序"的思想很简单，整个排序过程只需要三步：
//（1）在数据集之中，选择⼀个元素作为"基准"（pivot）。
//（2）所有⼩于"基准"的元素，都移到"基准"的左边；所有⼤于"基准"的元素，都移到"基准"的右边。
//（3）对"基准"左边和右边的两个⼦集，不断重复第⼀步和第⼆步，直到所有⼦集只剩下⼀个元素为⽌。
//举例来说，现在有⼀个数据集{85, 24, 63, 45, 17, 31, 96, 50}，怎么对其排序呢？
// 1.第⼀步，选择中间的元素45作为"基准"。（基准值可以任意选择，但是选择中间的值⽐较容易理解。）//2.第⼆步，按照顺序，将每个元素与"基准"进⾏⽐较，形成两个⼦集，⼀个"⼩于45"，另⼀个"⼤于等于45"。
//3.第三步，对两个⼦集不断重复第⼀步和第⼆步，直到所有⼦集只剩下⼀个元素为⽌。
//快速排序，算法封装开始
var quickSort = function (arr) {
/
/选择"基准"（pivot），并将其与原数组分离，再定义两个空数组，⽤来存放⼀左⼀右的两个⼦集。
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
js获取子元素var right = [];
//开始遍历数组，⼩于"基准"的元素放⼊左边的⼦集，⼤于基准的元素放⼊右边的⼦集。
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
//使⽤递归不断重复这个过程，就可以得到排序后的数组
return quickSort(left).concat([pivot], quickSort(right))
};
//快速排序，算法封装结束
var a = [85, 24, 63, 45, 17, 31, 96, 50];
//调⽤
quickSort(a);
alert(quickSort(a))
</script>
</body>
</html>

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。