- Notifications
You must be signed in to change notification settings - Fork24
Open
Description
插入排序顾名思义,对于未排序的数据,在已排序的序列中从后往前扫描,找到相应的位置进行插入,保持已排序序列中元素一直有序。
从 i 等于 1 开始遍历,拿到当前元素 curr,与前面的元素进行比较。
如果前面的元素大于当前元素,就把前面的元素和当前元素进行交换,不断循环直到未排序序列中元素为空,排序完成。
constinsertSort=function(arr){constlen=arr.lengthletcurr,prevfor(leti=1;i<len;i++){curr=arr[i]prev=i-1while(prev>=0&&arr[prev]>curr){arr[prev+1]=arr[prev]prev--}arr[prev+1]=curr}returnarr}
- 时间复杂度: O(n^2)
- 空间复杂度: O(1)
- 稳定
Metadata
Metadata
Assignees
Labels
No labels