排序
1、快速排序
快速排序(Quick Sort)是一种常用的排序算法,其原理基于分治策略。快速排序的基本思想是通过选择一个基准元素(pivot),将待排序序列分割成两部分,一部分所有元素小于等于基准元素,另一部分所有元素大于等于基准元素,然后对这两部分分别进行递归排序,最终得到有序序列。
-
分割操作:通过一趟排序,将待排序序列分割成两部分,使得左边的元素都小于等于基准元素,右边的元素都大于等于基准元素。在分割过程中,可以使用两个指针(称为i和j),分别从序列的两端开始,然后向中间移动,直到i遇到大于基准元素的元素,j遇到小于基准元素的元素,然后交换这两个元素,重复这个过程直到i和j相遇。
快速排序的平均时间复杂度为O(nlogn),其中n是待排序序列的长度。它是一种原地排序算法,不需要额外的空间开销。然而,最坏情况下的时间复杂度为O(n^2),即当待排序序列已经有序或近乎有序时。为了改进最坏情况下的性能,可以采用随机选择基准元素或者三数取中法来选择基准元素。
// 快速排序
const quickSort = (nums) => {
// 以中间值作为标准。
if (nums.length <= 1) return nums;
const mid = Math.floor(nums.length / 2), aim = nums.splice(mid, 1)[0];
// console.log(aim, mid);
let left = [], right = [];
for (let i = 0; i < nums.length; i++) {
const ele = nums[i];
if (ele > aim) {
right.push(ele)
} else {
left.push(ele);
}
}
// console.log(left, right, aim);
return quickSort(left).concat([aim], quickSort(right))
}
const arr = [2, 34, 21, 23, 44, 9]
console.log(quickSort(arr));
2、归并排序
归并排序(Merge Sort)是一种基于分治策略的排序算法,其原理是将待排序序列不断地分割成较小的子序列,然后将这些子序列合并成一个有序序列。
在合并操作中,需要创建一个临时数组来存储合并后的有序序列,然后按照顺序从两个子序列中选择较小的元素放入临时数组中,直到一个子序列中的所有元素都被选择完毕,然后将另一个子序列中剩余的元素依次放入临时数组中。
归并排序的时间复杂度是O(nlogn),其中n是待排序序列的长度。它是一种稳定的排序算法,不会改变相等元素的相对顺序。归并排序的缺点是需要额外的空间来存储临时数组,空间复杂度为O(n)。然而,由于归并排序的递归特性,其空间复杂度可以通过优化算法实现降低到O(1)。
// 归并排序
const mergeSort = (nums) => {
// 分割操作:将待排序序列递归地分割成两个子序列,直到每个子序列只包含一个元素或为空。
if (nums.length < 2) return nums;
const mid = Math.floor(nums.length / 2)
const left = nums.slice(0, mid);
const right = nums.slice(mid)
// 合并操作:将分割后的子序列两两合并,通过比较元素的大小,按顺序将它们合并成一个有序序列。重复这个过程,直到所有子序列合并成一个完整的有序序列。
const merge = (leftArr = [], rightArr = []) => {
let arr = [];
while (leftArr.length && rightArr.length) {
arr.push(leftArr[0] < rightArr[0] ?
leftArr.shift()
:
rightArr.shift()
)
}
return arr.concat(leftArr, rightArr);
}
return merge(mergeSort(left), mergeSort(right))
}
const arr = [2, 34, 21, 23, 1, 44, 9]
console.log(mergeSort(arr));
3、插入排序
插入排序(Insertion Sort)是一种简单直观的排序算法,其原理是将待排序序列分为已排序和未排序两部分,然后从未排序部分中选择一个元素,插入到已排序部分中的正确位置,使得已排序部分仍保持有序。
在插入排序过程中,为了将一个元素插入到正确的位置,需要比较它和已排序部分中的元素大小。如果已排序部分中的元素比它大,则将该元素后移一位,否则将该元素插入到该位置。这样,每次插入一个元素后,已排序部分的长度增加1,未排序部分的长度减少1,最终将所有元素按照从小到大的顺序插入到已排序部分中。
插入排序的时间复杂度取决于输入序列的初始状态,最好情况下时间复杂度为O(n),即输入序列已经有序,每个元素只需要比较一次。最坏情况下时间复杂度为O(n^2),即输入序列是逆序的,每个元素需要比较n-1次。平均情况下时间复杂度为O(n^2)。插入排序是一种稳定的排序算法,相等元素的相对顺序不会改变。它的空间复杂度为O(1),不需要额外的空间来存储数据。
// 插入排序。
const insertSort = (nums) => {
const len = nums.length;
for (let i = 1; i < len; i++) {
const ele = nums[i];
let j = i - 1;
while (j >= 0 && nums[j] < ele) {
nums[j + 1] = nums[j]
j--;
}
nums[j + 1] = ele;
}
return nums;
}
const arr = [2, 34, 21, 23, 1, 44, 9]
console.log(insertSort(arr));
4、冒泡排序
冒泡排序(Bubble Sort)是一种简单直观的排序算法,其原理是多次遍历待排序序列,每次比较相邻的两个元素,如果它们的顺序不正确,则交换这两个元素的位置,直到整个序列有序。
-
对除最后一个元素外的所有元素重复上述操作,直到整个序列有序。
在冒泡排序过程中,每次遍历都会将当前未排序部分的最大元素“浮”到未排序部分的最后,因此称为“冒泡”。通过多次遍历,每次将未排序部分的最大元素放置到正确的位置,最终得到整个序列有序。
冒泡排序的时间复杂度为O(n^2),其中n是待排序序列的长度。它是一种稳定的排序算法,相等元素的相对顺序不会改变。冒泡排序的缺点是排序速度较慢,不适合处理大规模数据。
const bubbleSort = (nums) => {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = 0; j < nums.length - 1 - i; j++) {
if (nums[j + 1] < nums[j]) {
const temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
return nums;
}
const arr = [2, 34, 21, 23, 1, 44, 9]
console.log(bubbleSort(arr));
5、选择排序
选择排序(Selection Sort)是一种简单直观的排序算法,其原理是每次从待排序序列中选择最小(或最大)的元素,将其放置在已排序部分的末尾(或开头),直到整个序列有序。
在选择排序的每一次遍历中,都会确定一个元素的最终位置。通过多次遍历,每次选择未排序部分的最小(或最大)元素放置到已排序部分的末尾(或开头),最终得到整个序列有序。
选择排序的时间复杂度为O(n^2),其中n是待排序序列的长度。无论输入序列的初始状态如何,每次遍历都需要找到最小(或最大)元素,因此需要进行n-1次遍历。选择排序是一种不稳定的排序算法,相等元素的相对顺序可能会发生改变。选择排序的优点是简单易实现,不需要额外的空间,只需要进行元素的比较和交换即可。然而,选择排序的缺点是每次遍历都需要找到最小(或最大)元素,效率相对较低,不适合处理大规模数据。
const selectSort = (nums) => {
for (let i = 0; i < nums.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < nums.length - 1; j++) { // 选择最小值的索引
if (nums[minIndex] > nums[j]) {
minIndex = j;
}
}
let temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
return nums;
}
const arr = [2, 34, 21, 23, 1, 44, 9]
console.log(bubbleSort(arr));
原文地址:https://blog.csdn.net/ggbee_/article/details/134750469
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_25826.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!