js 实现快速排序函数
时间: 2023-08-31 12:31:12 浏览: 62
### 回答1:
这里是一个快速排序的示例代码:
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (let 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));
}
### 回答2:
快速排序是一种常用的排序算法,通过将一个数组分成两个子数组,再对子数组进行递归排序,最后合并两个子数组得到有序的数组。
下面是用JavaScript语言实现快速排序的函数:
```javascript
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
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));
}
```
这个函数首先判断数组的长度,如果长度小于等于1,则直接返回该数组。
如果数组的长度大于1,则定义一个基准值,这里选择数组中间的值作为基准值,并将基准值从数组中剔除。然后,遍历数组,将比基准值小的数放在左边的子数组中,将比基准值大的数放在右边的子数组中。
最后,通过递归调用quickSort函数对左右两个子数组进行排序,并将排序后的左子数组、基准值和排序后的右子数组合并起来,得到最终的有序数组。
可以使用该函数对任意数组进行快速排序。
### 回答3:
快速排序是一种常用的排序算法,通过分治的思想进行排序。在JavaScript中,可以通过递归实现快速排序函数,下面是一个简单的实现:
```javascript
function quickSort(arr) {
// 递归终止条件:当数组长度小于等于1时,直接返回该数组
if (arr.length <= 1) {
return arr;
}
// 选择一个基准元素(可以是数组中的任意一个元素),并将其从数组中删除
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr.splice(pivotIndex, 1)[0];
// 定义左右两个数组,用于存放比基准元素小和大的元素
const left = [];
const right = [];
// 遍历原数组,比较每个元素与基准元素的大小
for (let 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));
}
```
使用以上的`quickSort`函数,可以快速将数组进行排序,例如:`quickSort([5, 3, 9, 1, 7])`将返回`[1, 3, 5, 7, 9]`。这个函数的时间复杂度为平均情况下的O(nlogn),空间复杂度为O(n)。