快速排序(QuickSort)是一种常用的排序算法,它通过将待排序的序列分割成较小和较大的两个子序列,然后递归地对子序列进行排序,最终将整个序列排序完成。
下面是使用 JavaScript 实现快速排序算法的比较计数器的代码:
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[Math.floor(arr.length / 2)];
const left = [];
const right = [];
let count = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
count++;
} else if (arr[i] > pivot) {
right.push(arr[i]);
count++;
}
}
return quickSort(left).concat([pivot], quickSort(right));
}
const arr = [5, 2, 9, 1, 7, 6, 3, 8, 4];
const sortedArr = quickSort(arr);
console.log(sortedArr);
console.log("比较计数器:" + (arr.length - 1));
在上述代码中,我们首先定义了一个 quickSort
函数,它接受一个待排序的数组作为参数。如果数组长度小于等于 1,直接返回该数组。
接下来,我们选择数组中间的元素作为基准值(pivot),然后遍历数组,将小于基准值的元素放入 left
数组中,将大于基准值的元素放入 right
数组中,并且每次比较都增加计数器的值。
然后,我们通过递归调用 quickSort
函数对 left
和 right
数组进行排序,并使用 concat
方法将排序后的结果与基准值连接起来,最终得到排序完成的数组。
最后,我们使用一个示例数组 [5, 2, 9, 1, 7, 6, 3, 8, 4]
进行测试,并输出排序后的结果和比较计数器的值。
快速排序算法的时间复杂度为 O(nlogn),是一种高效的排序算法。它在处理大规模数据时表现出色,适用于各种排序场景。
腾讯云提供了多种云计算相关产品,例如云服务器、云数据库、云存储等。你可以通过访问腾讯云官方网站(https://cloud.tencent.com/)了解更多关于这些产品的详细信息。
领取专属 10元无门槛券
手把手带您无忧上云