c网站开发教程,小程序前后端开发,做个网站页面多钱,做搜狗pc网站快速插入排序实现思路#xff1a;将一个新的数#xff0c;和前面的比较#xff0c;只要当前数小于前一个则和前一个交换位置#xff0c;否则终止#xff1b;「时间复杂度#xff1a;O(N^2)#xff1b;」「空间复杂度#xff1a;O(1)」 一、标准方式
function insertSort(a… 插入排序实现思路将一个新的数和前面的比较只要当前数小于前一个则和前一个交换位置否则终止「时间复杂度O(N^2)」「空间复杂度O(1)」 一、标准方式
function insertSort(arr) {// 检查输入是否为数组且不为空if (!Array.isArray(arr) || arr.length 0) {return [];}// 定义交换函数const swap (arr, i, j) {const temp arr[i];arr[i] arr[j];arr[j] temp;};// 插入排序for (let i 1; i arr.length; i) {for (let j i - 1; j 0 arr[j] arr[j 1]; j--) {swap(arr, j, j 1);}}return arr;
}
插入排序的实现原理是将一个数组分为已排序区间和未排序区间每次从未排序区间中取出一个元素将其插入到已排序区间中的合适位置直到未排序区间为空。具体实现过程如下
从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5
插入排序的优点是实现简单代码量小适用于小规模数据的排序。缺点是时间复杂度为O(n^2)不适用于大规模数据的排序。 二、另一种实现方式
function insertSort(arr) {for (let i 1; i arr.length; i) { // 从第二个元素开始遍历let j i - 1; // 定义一个指针指向当前元素的前一个元素const temp arr[i]; // 将当前元素存储到temp中while (j 0 arr[j] temp) { // 如果指针没有越界并且前一个元素大于当前元素arr[j 1] arr[j]; // 将前一个元素向右移动一位j--; // 指针向左移动一位}arr[j 1] temp; // 将当前元素插入到正确的位置}return arr; // 返回排序后的数组
}
第一段代码是标准的插入排序实现它使用一个指针j来指向当前元素的前一个元素然后将当前元素插入到正确的位置。具体来说它从第二个元素开始遍历将当前元素存储到temp中然后将指针j向左移动直到指针越界或者前一个元素小于等于当前元素然后将当前元素插入到j1的位置。
第二段代码也是插入排序的实现但是它使用了交换函数来交换元素的位置。具体来说它从第二个元素开始遍历然后将当前元素与前一个元素比较如果前一个元素大于当前元素就交换它们的位置直到当前元素插入到正确的位置。
总的来说这两段代码的实现思路是一样的都是将当前元素插入到已经排好序的部分中。但是第一段代码使用了一个指针来指向当前元素的前一个元素然后将当前元素插入到正确的位置而第二段代码使用了交换函数来交换元素的位置。 三、测试用例
const arr1 [3, 0, 2, 5, -1, 4, 1];
console.log(insertSort(arr1)); // [-1, 0, 1, 2, 3, 4, 5]const arr2 [1, 2, 3, 4, 5];
console.log(insertSort(arr2)); // [1, 2, 3, 4, 5]const arr3 [5, 4, 3, 2, 1];
console.log(insertSort(arr3)); // [1, 2, 3, 4, 5]
