排序算法(二)：插入排序

概念

把数组分成两部分&＃xff0c;一部分是有顺序的&＃xff0c;第二部分是没有顺序的&＃xff0c;从没有顺序的数组中拿出来一个&＃xff0c;把他排在有序数组中的相应位置

时间复杂度

最好&＃xff1a;O(n)&＃xff0c;原数组已经是升序的。
最坏&＃xff1a;O(n²)
平均&＃xff1a;O(n²)


代码

// 插入算法function insert_sort(arr) {let leg &＃61; arr.lengthfor (let i &＃61; 1; i < leg; i&＃43;&＃43;) {let value &＃61; arr[i]let j &＃61; i - 1;for (; j >&＃61; 0; j--) {if (arr[j] > value) {arr[j &＃43; 1] &＃61; arr[j]} else {break}}arr[j &＃43; 1] &＃61; value}}var sortArr &＃61; [9, 6, 3, 5, 2, 1, 7, 343, 6, 643, 243, 544, 5, 63, 234, 0, 56, 123]insert_sort(sortArr)console.log(sortArr)// [0, 1, 2, 3, 5, 5, 6, 6, 7, 9, 56, 63, 123, 234, 243, 343, 544, 643]

解释

let value &＃61; arr[i] // 是从没有顺序的数组中取出来的 比较做的数let j &＃61; i-1 // 是有序数组的长度for (; j >&＃61; 0; j--) { //遍历有序数组从大往小遍历// 从大往小&＃xff0c;如果这个值比value大&＃xff0c;当前的位置不是value&＃xff0c;要把他后面的数全部往后移动一位&＃xff0c;如果这个值比value小&＃xff0c;说明当前位置是value的地方&＃xff0c;if (arr[j] > value) {arr[j &＃43; 1] &＃61; arr[j]}arr[j &＃43; 1] &＃61; value // 把当前的位置放上value