用js写一个快速排序方法
时间: 2024-03-09 20:30:53 浏览: 13
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr[pivotIndex];
const left = [];
const right = [];
for (let i = 0; i < arr.length; i++) {
if (i === pivotIndex) {
continue;
}
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
const arr = [5, 3, 7, 1, 8, 2, 9, 4, 6];
console.log(quickSort(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
相关问题
用JavaScript写一个快速排序
### 回答1:
好的,以下是JavaScript实现快速排序的代码:
```javascript
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr[pivotIndex];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {
if (i === pivotIndex) {
continue;
}
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}
// 示例
var arr = [3, 0, 2, 5, -1, 4, 1];
console.log(quickSort(arr)); // [-1, 0, 1, 2, 3, 4, 5]
```
该快速排序函数接受一个数组作为参数,返回排序后的新数组。算法的基本思路是以数组中间的元素为基准,将数组分为两部分,左部分小于基准,右部分大于基准,然后再对左右两部分进行递归排序,最后将左部分、基准、右部分合并起来。
需要注意的是,在该实现中使用了递归算法,并且不是原地排序,因此在排序大数组时可能会出现栈溢出等问题。
### 回答2:
快速排序是一种常用的排序算法,其基本思想是通过递归地将待排序的数组划分为较小和较大的两个子数组,然后对子数组进行排序,最终整个数组就能够有序。
以下是用JavaScript编写的快速排序算法:
```javascript
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0]; // 选择中间元素作为基准
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) { // 小于基准的元素放在左边
left.push(arr[i]);
} else { // 大于等于基准的元素放在右边
right.push(arr[i]);
}
}
// 递归地对左右两个子数组进行快速排序,并将排序结果与基准值合并
return quickSort(left).concat(pivot, quickSort(right));
}
// 示例
const arr = [5, 2, 8, 9, 1, 3];
const sortedArr = quickSort(arr);
console.log(sortedArr); // 输出 [1, 2, 3, 5, 8, 9]
```
这个快速排序算法的基本思路是选择一个基准值(一般选择数组的中间元素),然后将比基准值小的元素放在左边,比基准值大的元素放在右边。然后分别对左右两个子数组进行递归排序,最后将排序好的子数组与基准值合并为最终的排序结果。
这个算法的时间复杂度为O(nlogn),其中n表示待排序数组的长度。快速排序是一种高效的排序算法,在大多数情况下都可以很好地处理大规模的数据。
### 回答3:
快速排序(Quick Sort)是一种经典的排序算法,它采用分治的思想来实现排序。下面是使用JavaScript语言编写的快速排序算法:
```
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivotIndex = Math.floor(arr.length / 2);
const pivot = arr[pivotIndex];
const left = [];
const right = [];
for (let i = 0; i < arr.length; i++) {
if (i === pivotIndex) {
continue;
}
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
// 示例用法
const arr = [5, 2, 9, 1, 3, 8, 6, 4, 7];
const sortedArr = quickSort(arr);
console.log(sortedArr); // 输出:[1, 2, 3, 4, 5, 6, 7, 8, 9]
```
以上代码中,函数`quickSort`使用递归的方式实现了快速排序。它首先基于数组的中间元素选择一个基准值(pivot),然后将小于基准值的元素放在左子数组中,将大于基准值的元素放在右子数组中。最后,递归地对左右子数组进行快速排序,并将左子数组、基准值和右子数组合并起来,即得到排序后的数组。
使用该算法对示例数组`[5, 2, 9, 1, 3, 8, 6, 4, 7]`进行排序,可以得到`[1, 2, 3, 4, 5, 6, 7, 8, 9]`。该算法的时间复杂度为O(nlogn),具有较高的效率。
用JAVASCRIPT写一个快速排序
### 回答1:
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(pivot, quickSort(right));
}
const arr = [3, 0, 2, 5, -1, 4, 1];
console.log(quickSort(arr)); // [-1, 0, 1, 2, 3, 4, 5]
### 回答2:
快速排序是一种常见的排序算法,也可以用JavaScript来实现。下面是使用递归方式编写的JS快速排序算法的示例代码:
```javascript
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0]; // 选择数组的第一个元素作为主元
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
```
快速排序算法首先选择一个主元(pivot),然后将比主元小的元素放在一个数组(left)中,将比主元大的元素放在另一个数组(right)中。接着,分别对left和right数组进行递归调用快速排序算法,最后将得到的排序结果与主元合并起来。
这个算法的时间复杂度为O(n log n),其中n为数组的长度。它是一种高效、常用的排序算法,在处理大规模数据集时非常有用。
### 回答3:
快速排序(Quicksort)是一种高效的排序算法,使用分治法的思想来进行排序。以下是使用JavaScript编写的快速排序算法的代码实现:
```javascript
function quickSort(array) {
if (array.length <= 1) {
return array;
}
var pivotIndex = Math.floor(array.length / 2);
var pivot = array[pivotIndex];
var left = [];
var right = [];
for (var i = 0; i < array.length; i++) {
if (i === pivotIndex) {
continue;
}
if (array[i] < pivot) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}
```
该代码首先检查数组的长度是否小于等于1,如果是,则直接返回该数组。然后,选择一个中间的元素作为基准元素(pivot),并创建两个空数组left和right。接下来,遍历数组中的每个元素,将元素与基准元素进行比较,小于基准元素的放入left数组,大于等于基准元素的放入right数组。最后,通过递归调用快速排序函数来对left和right数组进行排序,并将结果与基准元素连接起来。
通过这种分而治之的方法,可以将问题分解为较小的子问题,然后将其解决,并将结果合并起来以得到最终的有序数组。快速排序的时间复杂度为O(nlogn),是一种高效的排序算法。