js
每轮循环把最小的数放在第一位，第二轮再找剩的最小的数
js
js
js
js
| 排序类型 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | 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) | 稳定 |
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;
}
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;
}
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)];
}
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;
}
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;
}