济南烨铭网站建设,网站开发分为,景点网站建设,域名注册时间查询排序算法是计算机科学中的基本算法#xff0c;它们将一个无序的数组或列表按特定顺序进行排列#xff08;如升序或降序#xff09;。常见的排序算法可以根据其时间复杂度、空间复杂度和适用场景分类。以下是几种常见的排序算法#xff1a;
1. 冒泡排序#xff08;Bubble …排序算法是计算机科学中的基本算法它们将一个无序的数组或列表按特定顺序进行排列如升序或降序。常见的排序算法可以根据其时间复杂度、空间复杂度和适用场景分类。以下是几种常见的排序算法
1. 冒泡排序Bubble Sort
冒泡排序是一种简单的比较排序算法。它通过不断比较相邻元素并根据需要交换它们逐渐将最大或最小的元素“冒泡”到数组的一端。
时间复杂度O(n²)空间复杂度O(1)稳定性稳定适用场景适合小规模数据集但效率较低不适合大数据集。
算法步骤
从数组的开头开始依次比较相邻的元素如果顺序错误则交换它们。每一轮会把当前未排序部分中最大的元素放在最后的位置。重复该过程直到没有元素需要交换。 function bubbleSort(arr) { for (let i 0; i arr.length; i) { for (let j 0; j arr.length - 1 - i; j) { if (arr[j] arr[j 1]) { [arr[j], arr[j 1]] [arr[j 1], arr[j]]; } } } return arr; } 2. 选择排序Selection Sort
选择排序通过在未排序的部分中找到最小或最大的元素并将其与未排序部分的第一个元素交换逐步构建有序序列。
时间复杂度O(n²)空间复杂度O(1)稳定性不稳定适用场景适合数据规模较小简单实现但效率较低。
算法步骤
遍历数组找到未排序部分的最小元素将其与当前未排序部分的第一个元素交换。重复此过程直到整个数组排序完毕。 function selectionSort(arr) { for (let i 0; i arr.length; i) { let minIndex i; for (let j i 1; j arr.length; j) { if (arr[j] arr[minIndex]) { minIndex j; } } [arr[i], arr[minIndex]] [arr[minIndex], arr[i]]; } return arr; } 3. 插入排序Insertion Sort
插入排序通过从头开始逐一将元素插入到已排序部分的正确位置从而逐步形成一个有序序列。
时间复杂度O(n²)空间复杂度O(1)稳定性稳定适用场景适合数据量较小或部分有序的数据集。
算法步骤
从数组的第二个元素开始将其与已排序部分的元素进行比较并插入到正确的位置。对每个元素重复此操作直到整个数组排序完毕。 function insertionSort(arr) { for (let i 1; i arr.length; i) { let key arr[i]; let j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } return arr; } 4. 归并排序Merge Sort
归并排序是基于分治思想的排序算法将数组不断拆分成子数组分别对其排序后再合并。
时间复杂度O(n log n)空间复杂度O(n)稳定性稳定适用场景适合大规模数据集具有较高效率。
算法步骤
递归地将数组分成两个子数组。对每个子数组分别进行排序。合并两个有序子数组为一个完整的有序数组。 function mergeSort(arr) { if (arr.length 1) return arr; const mid Math.floor(arr.length / 2); const left mergeSort(arr.slice(0, mid)); const right mergeSort(arr.slice(mid)); return merge(left, right); }
function merge(left, right) { let result []; while (left.length right.length) { if (left[0] right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } return result.concat(left, right); } 5. 快速排序Quick Sort
快速排序也是基于分治思想。它通过选择一个“基准”元素将数组分为两部分一部分比基准元素小另一部分比基准元素大然后递归地对两部分进行排序。
时间复杂度O(n log n)最坏情况 O(n²)空间复杂度O(log n)递归栈空间稳定性不稳定适用场景在平均情况下非常高效适合大多数数据集。
算法步骤
选择一个基准元素通常为第一个或最后一个。将数组分为两部分一部分比基准小另一部分比基准大。对两部分递归进行快速排序。合并两部分。 function quickSort(arr) { if (arr.length 1) return arr; const pivot arr[arr.length - 1]; let left []; let right []; for (let i 0; i arr.length - 1; i) { if (arr[i] pivot) left.push(arr[i]); else right.push(arr[i]); } return [...quickSort(left), pivot, ...quickSort(right)]; } 6. 堆排序Heap Sort
堆排序是一种基于二叉堆的数据结构的排序算法。通过构建最大堆或最小堆每次将堆顶元素与末尾元素交换然后继续调整堆。
时间复杂度O(n log n)空间复杂度O(1)稳定性不稳定适用场景适合需要在原地排序的数据集。
算法步骤
构建最大堆。每次将堆顶元素与数组末尾元素交换缩小堆的范围后重新调整堆。 function heapify(arr, length, i) { let largest i; let left 2 * i 1; let right 2 * i 2; if (left length arr[left] arr[largest]) { largest left; } if (right length arr[right] arr[largest]) { largest right; } if (largest ! i) { [arr[i], arr[largest]] [arr[largest], arr[i]]; heapify(arr, length, largest); } }
function heapSort(arr) { let length arr.length; // 构建最大堆 for (let i Math.floor(length / 2) - 1; i 0; i--) { heapify(arr, length, i); } // 堆排序 for (let i length - 1; i 0; i--) { [arr[0], arr[i]] [arr[i], arr[0]]; heapify(arr, i, 0); } return arr; } 总结
O(n²) 的算法冒泡排序、选择排序、插入排序——这些算法适合小规模数据集。O(n log n) 的算法归并排序、快速排序、堆排序——适合大规模数据集其中快速排序通常表现最好但最坏情况为 O(n²)。
