网站开发技术合作协议书,word模板免费下载素材,福田汽车官网报价大全,建筑业资质查询网站排序
1、快速排序
快速排序#xff08;Quick Sort#xff09;是一种常用的排序算法#xff0c;其原理基于分治策略。快速排序的基本思想是通过选择一个基准元素#xff08;pivot#xff09;#xff0c;将待排序序列分割成两部分#xff0c;一部分所有元素小于等于基准…排序
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是一种简单直观的排序算法其原理是将待排序序列分为已排序和未排序两部分然后从未排序部分中选择一个元素插入到已排序部分中的正确位置使得已排序部分仍保持有序。
具体步骤如下 从第一个元素开始认为该元素已经被排序。 取出未排序部分的第一个元素在已排序部分中从后向前扫描找到该元素应该插入的位置。 将已排序部分中该位置以后的所有元素后移一位然后将该元素插入到正确的位置。 重复步骤2-3直到所有元素都被插入到已排序部分中。
在插入排序过程中为了将一个元素插入到正确的位置需要比较它和已排序部分中的元素大小。如果已排序部分中的元素比它大则将该元素后移一位否则将该元素插入到该位置。这样每次插入一个元素后已排序部分的长度增加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是一种简单直观的排序算法其原理是每次从待排序序列中选择最小或最大的元素将其放置在已排序部分的末尾或开头直到整个序列有序。
具体步骤如下 在未排序部分中找到最小或最大的元素。 将该最小或最大元素与未排序部分的第一个元素交换位置将其放置在已排序部分的末尾或开头。 扩大已排序部分的范围继续执行步骤1-2直到整个序列有序。
在选择排序的每一次遍历中都会确定一个元素的最终位置。通过多次遍历每次选择未排序部分的最小或最大元素放置到已排序部分的末尾或开头最终得到整个序列有序。
选择排序的时间复杂度为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));
