冒泡排序
jsfunction 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; }
选择排序
每轮循环把最小的数放在第一位,第二轮再找剩的最小的数
jsfunction 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; }
快速排序
jsfunction 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)]; }
插入排序
jsfunction 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; }
希尔排序
jsfunction 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) | 稳定 |