常用排序算法

    0

冒泡排序

js
function bubbleSort(dataSource) { for (let i = 0; i < dataSource.length; i++) { for (let j = 0; j < dataSource.length - i - 1; j++) { if (dataSource[j] > dataSource[j + 1]) { [dataSource[j], dataSource[j + 1]] = [dataSource[j + 1], dataSource[j]]; } } } return dataSource; }

选择排序

每轮循环把最小的数放在第一位,第二轮再找剩的最小的数

js
function selectSort(dataSource) { const data = dataSource.slice(); const length = data.length; for (let i = 0; i < length; i++) { let min = i; for (let j = i + 1; j < length; j++) { if (data[j] < data[min]) { min = j; } } if (min !== i) { [data[i], data[min]] = [data[min], data[i]]; } } return data; }

快速排序

js
function quickSort(dataSource) { if (dataSource.length <= 1) { return dataSource; } const pivot = dataSource[0]; const left = []; const right = []; for (let i = 1; i < dataSource.length; i++) { if (dataSource[i] < pivot) { left.push(dataSource[i]); } else { right.push(dataSource[i]); } } return [...quickSort(left), pivot, ...quickSort(right)]; }

插入排序

js
function insertSort(dataSource) { const data = dataSource.slice(); const length = data.length; for (let i = 1; i < length; i++) { const current = data[i]; let j = i - 1; while (j >= 0 && data[j] > current) { data[j + 1] = data[j]; j--; } data[j + 1] = current; } return data; }

希尔排序

js
function shellSort(dataSource) { const data = dataSource.slice(); const n = data.length; let gap = n / 2; while (gap > 0) { for (let i = gap; i < n; i += 1) { const temp = data[i]; let j = i; while (j >= gap && data[j - gap] > temp) { data[j] = data[j - gap]; j -= gap; } data[j] = temp; } gap = Math.floor(gap / 2); } return data; }

归并排序

堆排序

总结

排序类型平均情况最好情况最坏情况辅助空间稳定性
插入排序O(n²)O(n)O(n²)O(1)稳定
希尔排序O(n^1.3)O(nlogn)O(n²)O(1)不稳定
选择排序O(n²)O(n²)O(n²)O(1)不稳定
堆排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(1)不稳定
冒泡排序O(n²)O(n)O(n²)O(1)稳定
快速排序O(nlog₂n)O(nlog₂n)O(n²)O(nlog₂n)不稳定
归并排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(n)稳定
基数排序O(d(n+k))O(d(n+k))O(d(n+kd))O(n+kd)稳定
评论区

共有评论 0

暂无评论