博客

javascript实现快速排

  • Post category:other

JavaScript实现快速排序的完整攻略

快速排序是一种常用的排序算法，它的时间复杂度为O(nlogn)，是一种高效的排序算法。本文将为您提供JavaScript实现快速排序的完整攻略，包括快速排序的原理、JavaScript实现快速排序的步骤和两个示例。

快速排序的原理

快速排序的原理是通过分治法将一个大问题分解为多个小问题，然后递归地解决这些小问题。具体步骤如下：

  1. 选择一个基准元素，将数组分为两个子数组，小于基准元素的放在左边，大于基准元素的放在右边。

  2. 对左右两个子数组分别递归地进行快速排序。

  3. 合并左右两个子数组。

JavaScript实现快速排序的步骤

以下是JavaScript实现快速排序的步骤：

  1. 编写快速排序函数。

javascript
function quickSort(arr) {
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));
}

  1. 调用快速排序函数。

javascript
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5 3, 5];
const sortedArr = quickSort(arr);
console.log(sortedArr);

输出结果为：[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]。

示例1：使用快速排序对字符串数组进行排序

以下是使用快速排序对字符串数组进行排序的示例：

function quickSort(arr) {
  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));
}

const arr = ['banana', 'apple', 'orange', 'grape', 'pear'];
const sortedArr = quickSort(arr);
console.log(sortedArr);

输出结果为：["apple", "banana", "grape", "orange", "pear"]。

示例2：使用快速排序对对象数组进行排序

以下是使用快速排序对对象数组进行排序的示例：

function quickSort(arr, key) {
  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][key] < pivot[key]) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left, key).concat([pivot], quickSort(right, key));
}

const arr = [
  { name: 'John', age: 25 },
  { name: 'Mary', age: 30 },
  { name: 'Bob', age: 20 },
  { name: 'Alice', age: 35 },
];
const sortedArr = quickSort(arr, 'age');
console.log(sortedArr);

输出结果为：

[
  { name: 'Bob', age: 20 },
  { name: 'John', age: 25 },
  { name: 'Mary', age: 30 },
  { name: 'Alice', age: 35 }
]

以上是JavaScript实现快速排序的完整攻略，包括快速排序的原理、JavaScript实现快排序的步骤和两个示例。

Tags: