- 算法思路
对于大小为n的数组a,分已排序区域A (a[0, m-1]) 和未排序区域B (a[m, n-1]),其中m为已排序区间元素个数。
用j递增遍历A元素 (遍历范围[1, n-1]) ,每一次遍历用变量value记下a[j],然后使k=j,递减遍历a[k-1] (遍历范围(0, j]) 与value比较,若a[k-1] > value,a[k-1]向后移,否则跳出k循环,赋值a[k]=value (先跳循环再赋值)。 - 算法疑问
- j, k的含义分别是什么?
j指向的是B的首元素;跳出循环的k指向的是要插入的位置。 - 为什么要跳出循环再赋值?
假如k=0,回跳出循环,而0位置就是要插入的位置。跳出再赋值时为了兼容k=0的情况。
- j, k的含义分别是什么?
- 算法分析
- 是否是稳定排序算法
是的。 - 是否是原地排序算法?
是的。 - 空间复杂度
因为时候原地排序算法,所以是O(1)。 - 时间复杂度
设m为插入次序,t(m)为第m次插入的消耗时间,则有 T(n) = t(1) + ... + t(n-1) t(m)max = m t(m)min = C(常数) 则T(n)max = 1 + ... + n - 1 = n(n-1)/2, 即O(n2) T(n)min = n-1(C), 即O(n)
- 是否是稳定排序算法
- 算法实现
public void sort() { for (int j = 1; j < getSize(); j++) { int value = data[j]; int k = j; for (; k > 0; k--) { if (data[k-1] > value) { data[k] = data[k-1]; //已排序元素往后移,给需要插入的元素腾出位置 } else { break; } } data[k] = value; } }
网友评论