[js] 第243天 写一个方法实现“选择排序算法”，并解释下时间复杂度和空间复杂度

[haizhilin2013]

第243天 写一个方法实现“选择排序算法”，并解释下时间复杂度和空间复杂度

我也要出题

[ljluestc]

function selectionSort(arr) { const n = arr.length;

for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < n; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }

    if (minIndex !== i) {
        // Swap arr[i] and arr[minIndex]
        const temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

return arr;

}

// 示例用法 const unsortedArray = [64, 34, 25, 12, 22, 11, 90]; const sortedArray = selectionSort(unsortedArray); console.log(sortedArray); // 输出已排序数组

当然可以！以下是一个用JavaScript编写的选择排序算法的示例代码：

function selectionSort(arr) {
    const n = arr.length;

    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;

        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        if (minIndex !== i) {
            // Swap arr[i] and arr[minIndex]
            const temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    return arr;
}

// 示例用法
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = selectionSort(unsortedArray);
console.log(sortedArray); // 输出已排序数组

关于时间复杂度和空间复杂度的解释：

1. 时间复杂度：

   • 选择排序的时间复杂度是O(n^2)，其中n是数组的长度。这是因为在每次外循环中，它需要查找未排序部分中的最小元素，并将其放在已排序部分的末尾。这个查找最小元素的过程需要O(n)的时间，并且需要执行n-1次。
   • 因此，总体时间复杂度是O(n^2)。

2. 空间复杂度：

   • 选择排序的空间复杂度是O(1)，即它在排序过程中只需要常数级别的额外空间来存储一些临时变量，而不会随着输入数组的大小而增加。