@zero1036
2017-04-10T07:43:00.000000Z
字数 2159
阅读 1577
Java-Base
数据结构与算法
插入排序的3中实现:
操作:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置,直到全部插入排序完为止。
例如:
array =[1,3,5,7,9,4,8]
,已排序区块是[1,3,5,7,9]
,待排序元素是4
4
与1
比较,结果不变:[1,3,5,7,9,4]
4
与3
比较,结果不变:[1,3,5,7,9,4]
4
与5
比较,插入到5
位置:[1,3,4,5,7,9]
排序稳定:是。当比较元素相等时,右元素插入到左元素右方,可保持稳定。
二分法插入排序 , 即查找插入点的位置, 可以使用 折半查找 .
这样可以 减少比较 的次数, 移动的次数 不变,
时间复杂度仍为
JDK1.8默认排序方式Timsort,Binary Insertion Sort是Timsort的Run排序方法。Binarysort实现要点:
1、 Binarysort要求首先找出数组(此数组即分区)中从0位开始连续升序区块,及区块下一位元素pivot;
例:
[1,3,5,7,9,4,8]
的起始连续升序区块是[1,3,5,7,9]
,区块长度为5,即runLen;pivot是4
;
2、 通过二分法比较pivot与区分元素的升降序关系,计算pivot在区块中的位置;并插入到该位置,组成新的区块;
例:
4
在区块中[1,3,5,7,9]
,先比较5 > 4
,是降序;再比较3 < 4
,是升序,确认位置,通过native方法System.arraycopy()
插入到区块中;
3、 再计算新区块与新pivot的位置关系,直到完成排序
4、 注意:以上升序的定义是Comparator.compare(右元素, 左元素) >= 0
,反之为降序;非数值上的升降序。
源码:
/**
* 二分法插入排序
* 排序结果为升序,Comparator.compare(右, 左) >= 0
* 例如:假设目标数组a长度为10,数组头3位已经排好升序,所以
* lo = 0
* hi = 9 + 1
* start = 3 (0 1 2位已排序,从第3位开始计算)
* @param a 目标数组
* @param lo 指定排序范围首个元素位置
* @param hi 指定排序范围最后元素位置 + 1
* @param start 从start位置开始计算排序,即lo到start部分不排序
*/
private static <T> void binarySort(T[] a, int lo, int hi, int start,
Comparator<? super T> c) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
// 取出起始计算位置的元素,并记录临时对象
T pivot = a[start];
/*
* 设置插入的边界位置(范围)
* 左边界恒定为首个元素位置
* 右边界根据起始位置递增
* 例 [1,2,3,4,5,6....],执行结果依次为:[1,2,3],[1,2,3,4],[1,2,3,4,5]
*/
int left = lo;
int right = start;
assert left <= right;
/*
* 通过n/2对折方法,找出起始位置start的元素pivot,在[lo, start)范围中的插入位置left,需要满足以下条件
* pivot >= all in [lo, left).
* pivot < all in [right, start).
* 例:[1,3,5,7,9,4],pivot = 4,运算结果left = 2
*/
while (left < right) {
// 二进制右移一位获取中间值,例:1>>>1=0 2>>>1=1 3>>>1=1 4>>>1=2
// 二进制右移方法,比n/2方法处理更简单
int mid = (left + right) >>> 1;
// 右边界起始元素与中间值比较
// 若降序,则右边界为中间值
if (c.compare(pivot, a[mid]) < 0)
right = mid;
// 若升序,则左边界为中间位置 + 1
else
left = mid + 1;
}
assert left == right;
// 取得需要移位元素个数,The number of elements to move
int n = start - left;
// 通过System.arraycopy()置换元素位置
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}
void BInsertSort(std::deque<int>& L) {
for (std::size_t i=2; i<L.size(); ++i) {
L[0] = L[i];
int low = 1, high = i-1;
//查找L[0]的位置
while (low <= high) {
int m = (low + high)/2;
if (L[0] < L[m]) high = m-1;
else low = m+1;
}
//把较大的向前移动
for (int j=i-1; j>=high+1; --j) L[j+1] = L[j];
L[high+1] = L[0];
}
}