在數(shù)據(jù)結(jié)構(gòu)中，常見的排序算法有以下幾種：
- 冒泡排序（Bubble Sort）：通過比較相鄰元素并交換它們的位置，每輪將最大（或最?。┑脑孛芭莸侥┪?，重復(fù)執(zhí)行直到排序完成。
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)); // Output: [11, 12, 22, 25, 34, 64, 90]
特點(diǎn)：簡單易懂，但對于大型數(shù)據(jù)集效率較低。
時間復(fù)雜度：
最優(yōu)情況：O(n)（當(dāng)數(shù)組已經(jīng)排序好時）。
平均情況：O(n^2)。
最壞情況：O(n^2)。
- 插入排序（Insertion Sort）：將數(shù)組分為已排序和未排序兩部分，每次從未排序部分選擇一個元素插入到已排序部分的正確位置，重復(fù)執(zhí)行直到排序完成。
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; 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;
}
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(insertionSort(arr)); // Output: [11, 12, 22, 25, 34, 64, 90]
特點(diǎn)：適用于小型數(shù)據(jù)集和部分有序數(shù)組。
時間復(fù)雜度：
最優(yōu)情況：O(n)（當(dāng)數(shù)組已經(jīng)排序好時）。
平均情況：O(n^2)。
最壞情況：O(n^2)。
- 選擇排序（Selection Sort）：每輪從未排序部分選擇最?。ɑ蜃畲螅┑脑?，將其與未排序部分的首元素交換，重復(fù)執(zhí)行直到排序完成。
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
return arr;
}
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(selectionSort(arr)); // Output: [11, 12, 22, 25, 34, 64, 90]
特點(diǎn)：簡單易懂，但對于大型數(shù)據(jù)集效率較低。
時間復(fù)雜度：
最優(yōu)情況：O(n^2)。
平均情況：O(n^2)。
最壞情況：O(n^2)。
- 快速排序（Quick Sort）：通過選取一個基準(zhǔn)元素，將數(shù)組分成比基準(zhǔn)元素小和大的兩部分，然后遞歸地對兩部分進(jìn)行排序。
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort(arr)); // Output: [11, 12, 22, 25, 34, 64, 90]
特點(diǎn)：高效且被廣泛使用的排序算法。
時間復(fù)雜度：
最優(yōu)情況：O(n log n)。
平均情況：O(n log n)。
最壞情況：O(n^2)。
- 歸并排序（Merge Sort）：將數(shù)組不斷分割成較小的子數(shù)組，然后再將子數(shù)組按順序合并，重復(fù)執(zhí)行直到排序完成。
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) {
const mergedArr = [];
let leftIdx = 0;
let rightIdx = 0;
while (leftIdx < left.length && rightIdx < right.length) {
if (left[leftIdx] < right[rightIdx]) {
mergedArr.push(left[leftIdx]);
leftIdx++;
} else {
mergedArr.push(right[rightIdx]);
rightIdx++;
}
}
return [...mergedArr, ...left.slice(leftIdx), ...right.slice(rightIdx)];
}
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(mergeSort(arr)); // Output: [11, 12, 22, 25, 34, 64, 90]
特點(diǎn)：穩(wěn)定的排序算法，適用于大型數(shù)據(jù)集。
時間復(fù)雜度：
最優(yōu)情況：O(n log n)。
平均情況：O(n log n)。
最壞情況：O(n log n)。
- 堆排序（Heap Sort）：利用二叉堆（最大堆或最小堆）的特性進(jìn)行排序，將堆頂元素與最后一個元素交換，然后重建堆，重復(fù)執(zhí)行直到排序完成。
function heapSort(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (let i = n - 1; i >= 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, n, i) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(heapSort(arr)); // Output: [11, 12, 22, 25, 34, 64, 90]
特點(diǎn)：高效的原地排序算法。
時間復(fù)雜度：
最優(yōu)情況：O(n log n)。
平均情況：O(n log n)。
最壞情況：O(n log n)。
- 希爾排序（Shell Sort）：是插入排序的一種改進(jìn)算法，通過分組進(jìn)行插入排序，逐漸縮小分組間隔，直到分組間隔為1。
function shellSort(arr) {
const n = arr.length;
for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < n; i++) {
let temp = arr[i];
let j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
return arr;
}
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(shellSort(arr)); // Output: [11, 12, 22, 25, 34, 64, 90]
特點(diǎn)：插入排序的改進(jìn)版本，適用于中等大小的數(shù)據(jù)集。
時間復(fù)雜度：
最優(yōu)情況：O(n log^2 n)（取決于步長序列）。
平均情況：取決于步長序列。
最壞情況：取決于步長序列。
- 計(jì)數(shù)排序（Counting Sort）：適用于一定范圍內(nèi)的整數(shù)排序，通過統(tǒng)計(jì)每個元素出現(xiàn)的次數(shù)，然后計(jì)算每個元素的位置，重復(fù)執(zhí)行直到排序完成。
function countingSort(arr) {
const n = arr.length;
let max = Math.max(...arr);
let min = Math.min(...arr);
const range = max - min + 1;
const count = Array(range).fill(0);
const output = Array(n);
for (let i = 0; i < n; i++) {
count[arr[i] - min]++;
}
for (let i = 1; i < range; i++) {
count[i] += count[i - 1];
}
for (let i = n - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (let i = 0; i < n; i++) {
arr[i] = output[i];
}
return arr;
}
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(countingSort(arr)); // Output: [11, 12, 22, 25, 34, 64, 90]
特點(diǎn)：適用于小范圍整數(shù)排序。
時間復(fù)雜度：O(n + k)，其中 n 是輸入數(shù)組元素個數(shù)，k 是輸入范圍大小。
- 桶排序（Bucket Sort）：將元素根據(jù)一定規(guī)則放入不同的桶中，每個桶內(nèi)部進(jìn)行排序，然后按順序合并桶內(nèi)的元素，重復(fù)執(zhí)行直到排序完成。
function bucketSort(arr, bucketSize = 5) {
if (arr.length === 0) return arr;
const max = Math.max(...arr);
const min = Math.min(...arr);
const bucketCount = Math.floor((max - min) / bucketSize) + 1;
const buckets = Array(bucketCount).fill().map(() => []);
for (let i = 0; i < arr.length; i++) {
const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
buckets[bucketIndex].push(arr[i]);
}
arr.length = 0;
for (let i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]);
arr.push(...buckets[i]);
}
return arr;
}
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bucketSort(arr)); // Output: [11, 12, 22, 25, 34, 64, 90]
特點(diǎn)：適用于均勻分布的數(shù)據(jù)。
時間復(fù)雜度：O(n + k)，其中 n 是輸入數(shù)組元素個數(shù)，k 是桶的個數(shù)。
- 基數(shù)排序（Radix Sort）：按照位數(shù)將元素分配到不同的桶中，然后按順序合并桶內(nèi)的元素，重復(fù)執(zhí)行直到所有位數(shù)排序完成。
function radixSort(arr) {
const max = Math.max(...arr);
const maxLength = String(max).length;
let bucket = Array.from({ length: 10 }, () => []);
for (let i = 0; i < maxLength; i++) {
for (let j = 0; j < arr.length; j++) {
const digit = Math.floor(arr[j] / 10 ** i) % 10;
bucket[digit].push(arr[j]);
}
arr.length = 0;
for (let k = 0; k < bucket.length; k++) {
arr.push(...bucket[k]);
bucket[k].length = 0;
}
}
return arr;
}
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(radixSort(arr)); // Output: [11, 12, 22, 25, 34, 64, 90]
特點(diǎn)：適用于數(shù)字位數(shù)相同的整數(shù)排序。
時間復(fù)雜度：O(d * (n + k))，其中 d 是最大數(shù)字的位數(shù)，n 是輸入數(shù)組元素個數(shù)，k 是輸入范圍大小。文章來源：http://www.zghlxwxcb.cn/news/detail-615897.html
每種排序算法都有不同的時間復(fù)雜度和適用場景。在實(shí)際應(yīng)用中，根據(jù)數(shù)據(jù)規(guī)模和性能要求選擇合適的排序算法是很重要的。文章來源地址http://www.zghlxwxcb.cn/news/detail-615897.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
