快速排序javescript
时间: 2023-04-05 17:00:40 浏览: 57
快速排序是一种常见的排序算法,它的基本思想是通过分治的方式将一个大问题分解成若干个小问题,然后逐步解决这些小问题,最终得到整个问题的解。在 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,如果是,则直接返回该数组。否则,选择一个基准元素(pivot),将数组中小于基准元素的元素放到左边,大于基准元素的元素放到右边,然后递归地对左右两个子数组进行排序,最后将左子数组、基准元素、右子数组拼接起来,得到排序后的数组。
相关问题
快速排序JavaScript
快速排序是一种常用的排序算法,它由C. A. R. Hoare在1960年提出。该算法的时间复杂度为O(nlogn),但在大多数情况下,快速排序的效率更高,因此得到了广泛的应用。
快速排序的工作原理如下:
1. 选择一个基准元素(通常选择第一个元素)。
2. 将数组分成两部分,一部分包含所有小于基准元素的数,另一部分包含所有大于基准元素的数。
3. 递归地对这两部分进行快速排序。
具体的JavaScript实现可以参考以下代码:
```
var swap = (arr, i, j) => {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
var partition = (arr, low, high) => {
let pivot = arr[low];
let i = low;
let j = high + 1;
while (true) {
while (arr[++i] < pivot) {
if (i === high) break;
}
while (arr[--j] > pivot) {
if (j === low) break;
}
if (i >= j) break;
swap(arr, i, j);
}
swap(arr, low, j);
return j;
}
var quickSort = (arr, low, high) => {
if (low < high) {
let pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
return arr;
}
var sortArray = (arr) => {
return quickSort(arr, 0, arr.length - 1);
}
```
快速排序 javascript
以下是 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));
}
```
这个实现使用了递归来对左右子数组进行快速排序,然后将它们与主元素(即 pivot)连接起来。主元素选择的是第一个元素,但是也可以选择随机元素或者数组的中间元素等等。