用JAVASCRIPT写一个快速排序
时间: 2023-08-31 14:32:29 浏览: 60
### 回答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),是一种高效的排序算法。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)