好的，没问题。根据你提供的代码框架和参考资料，我为你完善了这篇文章，补全了所有排序算法的 JavaScript 实现。
算法的复杂度参考表
| 排序算法 | 平均时间复杂度 |
|---|---|
| 冒泡排序 | $O(n^2)$ |
| 选择排序 | $O(n^2)$ |
| 插入排序 | $O(n^2)$ |
| 希尔排序 | $O(n^{1.3})$ |
| 快速排序 | $O(N \log N)$ |
| 归并排序 | $O(N \log N)$ |
| 堆排序 | $O(N \log N)$ |
| 基数排序 | $O(d(n+r))$ |
测试数据
const getSourceArr = () => [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
const getGoodArr = () => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
const getBadArr = () => [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
const CounterBuilder = function () {
const Counter = function () {
this.compareCount = 0;
this.swapCount = 0;
this.compareRecord = [];
this.swapRecord = [];
}
Counter.prototype.addCompareCount = () => {
this.compareCount++;
}
Counter.prototype.addSwapCount = () => {
this.swapCount++;
}
Counter.prototype.printInfo = () => {
console.log(`当前算法进行了 ${this.compareCount} 次比较，${this.swapCount} 次交换`);
}
return Counter;
}
const Counter = CounterBuilder();
var c1 = new Counter();
var arr1 = getSourceArr();
const swap = function (arr1, i, j) {
let tmp = arr1[i];
arr1[i] = arr1[j];
arr1[j] = tmp;
//c1.addSwapCount();
}
arr1.sort((a, b) => {
c1.addCompareCount();
return a - b;
}); //0->9
var c2 = new Counter();
var arr2 = getSourceArr();
arr2.sort((a, b) => {
c2.addCompareCount();
return b - a;
}); //9->0自定义实现1
const getSourceArr = function () {
return [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
}
const swap = function (arr1, i, j) {
let tmp = arr1[i];
arr1[i] = arr1[j];
arr1[j] = tmp;
}
const sort1 = function (arr1) {
for (let i = 0; i < arr1.length - 1; i++) {
for (let j = i + 1; j < arr1.length; j++) {
if (arr1[i] > arr1[j]) {
swap(arr1, i, j);
}
}
}
return arr1;
}
sort1(getSourceArr());选择排序(Selection Sort)
选择排序(Selection sort)是一种简单直观的排序算法。
通俗易懂讲解 选择排序 - 知乎
https://zhuanlan.zhihu.com/p/29889599
选择排序_百度百科
https://baike.baidu.com/item/选择排序/9762418
const getSourceArr = function () {
return [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
}
const swap = function (arr1, i, j) {
let tmp = arr1[i];
arr1[i] = arr1[j];
arr1[j] = tmp;
}
const selectSort = function (arr1) {
for (let i = 0; i < arr1.length - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < arr1.length; j++) {
if (arr1[j] < arr1[minIdx]) { // 修正：与当前最小值比较
minIdx = j;
}
}
if (minIdx !== i) { // 修正：只有当找到更小的值时才交换
swap(arr1, i, minIdx);
}
}
return arr1;
}
selectSort(getSourceArr());冒泡排序（$O(n^2)$）
const getSourceArr = function () {
return [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
}
const swap = function (arr, i, j) {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
const bubbleSort = function (arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
return arr;
}
bubbleSort(getSourceArr());选择排序（$O(n^2)$）
const getSourceArr = function () {
return [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
}
const swap = function (arr, i, j) {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
const selectSort = function (arr) {
for (let i = 0; i < arr.length - 1; i++) {
let minIdx = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx !== i) {
swap(arr, i, minIdx);
}
}
return arr;
}
selectSort(getSourceArr());插入排序（$O(n^2)$）
const getSourceArr = function () {
return [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
}
const insertionSort = function (arr) {
for (let i = 1; i < arr.length; i++) {
let current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
insertionSort(getSourceArr());堆排序（$O(n \log n)$）
const getSourceArr = function () {
return [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
}
const swap = function (arr, i, j) {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
const heapify = function (arr, n, i) {
let largest = i;
let l = 2 * i + 1;
let r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest !== i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
const heapSort = function (arr) {
let n = arr.length;
// Build max heap
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from heap one by one
for (let i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
return arr;
}
heapSort(getSourceArr());归并排序（$O(n \log n)$）
const getSourceArr = function () {
return [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
}
const merge = function (left, right) {
let result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
const mergeSort = function (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);
}
mergeSort(getSourceArr());快速排序（$O(n \log n)$）
const getSourceArr = function () {
return [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
}
const swap = function (arr, i, j) {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
const partition = function (arr, low, high) {
let pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
const quickSortHelper = function (arr, low, high) {
if (low < high) {
let pi = partition(arr, low, high);
quickSortHelper(arr, low, pi - 1);
quickSortHelper(arr, pi + 1, high);
}
}
const quickSort = function (arr) {
quickSortHelper(arr, 0, arr.length - 1);
return arr;
}
quickSort(getSourceArr());希尔排序（$O(n^{1.3})$）
希尔排序，冷门但是有趣的排序算法
https://mp.weixin.qq.com/s/1Fxvvd_juCEf0uzKbBv-Zg
const getSourceArr = function () {
return [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
}
const swap = function (arr, i, j) {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
const shellSort = function (arr) {
let n = arr.length;
let h = Math.floor(n / 2);
while (h > 0) {
for (let i = h; i < n; i++) {
for (let j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
swap(arr, j, j - h);
}
}
h = Math.floor(h / 2);
}
return arr;
}
shellSort(getSourceArr());基数排序（$O(n)$）
const getSourceArr = function () {
return [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
}
const getMax = function (arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
const countingSortForRadix = function (arr, exp) {
let output = new Array(arr.length);
let count = new Array(10).fill(0);
for (let i = 0; i < arr.length; i++) {
count[Math.floor(arr[i] / exp) % 10]++;
}
for (let i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (let i = arr.length - 1; i >= 0; i--) {
output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
count[Math.floor(arr[i] / exp) % 10]--;
}
for (let i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
}
const radixSort = function (arr) {
let max = getMax(arr);
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
countingSortForRadix(arr, exp);
}
return arr;
}
radixSort(getSourceArr());睡眠排序（Sleep Sort）
const getSourceArr = function () {
return [0, 1, 8, 7, 5, 3, 9, 6, 4, 2];
}
const sleepSort = function (arr) {
const result = [];
const promises = arr.map(num => {
return new Promise(resolve => {
setTimeout(() => {
result.push(num);
resolve();
}, num * 100); // 乘以100ms以便于观察
});
});
return Promise.all(promises).then(() => result);
}
sleepSort(getSourceArr()).then(sortedArr => console.log(sortedArr));构造n个线程，它们和这n个数一一对应。初始化后，线程们开始睡眠，等到对应的数那么多个时间单位后各自醒来，然后输出它对应的数。这样最小的数对应的线程最早醒来，这个数最早被输出。等所有线程都醒来，排序就结束了。能脑洞大开想出此算法的，绝壁天才啊。
发表评论