## 【java集合框架源码剖析系列】java源码剖析之java集合中的折半插入排序算法 转

htq

``````#include<iostream>
using namespace std;
const int len=7;

void binaryInsertSort(int * array,int len)
{
for(int i=1;i<len;i++)//与普通的排序一样，外层for循环用来控制排序趟数
{
int x=array[i];
int low=0,high=i-1;//low与high的初始化很重要，因为i从1开始，所以low=0，high=i-1，这样就能保证数组中的每一个
//元素参与排序，教材上的low=1是错误的，因为教材上将数组中的第0位作为监视哨而未参与排序。
while(low<=high)//寻找待插入的位置
{
int mid=(low+high)/2;
if(x<array[mid])
high=mid-1;
else
low=mid+1;
}
for(int j=i-1;j>=low;j--)//将记录向后移动
{
array[j+1]=array[j];
}
array[low]=x;//插入记录
}
}
int main()
{
int a[len]={7,0,4,5,1,2,3};
binaryInsertSort(a,len);
for(int i=0;i<len;i++)
cout<<a[i]<<' ';
cout<<endl;
}``````

``````static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;

int nRemaining  = hi - lo;
if (nRemaining < 2)
return;  // Arrays of size 0 and 1 are always sorted

// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}``````

``````/**
* Sorts the specified portion of the specified array using a binary
* insertion sort.  This is the best method for sorting small numbers
* of elements.  It requires O(n log n) compares, but O(n^2) data
* movement (worst case).
*
* If the initial part of the specified range is already sorted,
* this method can take advantage of it: the method assumes that the
* elements from index {@code lo}, inclusive, to {@code start},
*
* @param a the array in which a range is to be sorted
* @param lo the index of the first element in the range to be sorted
* @param hi the index after the last element in the range to be sorted
* @param start the index of the first element in the range that is
*        not already known to be sorted ({@code lo <= start <= hi})
* @param c comparator to used for the sort
*/
@SuppressWarnings("fallthrough")
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];

// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
/*
* Invariants:
*   pivot >= all in [lo, left).
*   pivot <  all in [right, start).
*/
while (left < right) {
int mid = (left + right) >>> 1;
if (c.compare(pivot, a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;

/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left.  Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that's why this sort is stable.
* Slide elements over to make room for pivot.
*/
int n = start - left;  // The number of elements to move
// Switch is just an optimization for arraycopy in default case
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;
}
}``````

``````/**
* Sorts the specified portion of the specified array using a binary
* insertion sort.  This is the best method for sorting small numbers
* of elements.  It requires O(n log n) compares, but O(n^2) data
* movement (worst case).

/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left.  Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that's why this sort is stable.
* Slide elements over to make room for pivot.
*/``````

1折半插入排序是最好的算法对于排序小数量的元素This is the best method for sorting small numbers of elements.

2它只需要O(nlogn)的比较次数，但是其移动次数仍然为 O(n^2)。It requires O(n log n) compares, but O(n^2) data movement (worst case).

3它是稳定的排序算法。that's why this sort is stable.而快速排序不是稳定的排序。

### htq

Android--面试中遇到的问题总结（三）

《Android 开发工程师面试指南 LearningNotes 》，作者是陶程，由梁观全贡献部分。大家可以去知乎关注这两位用心的少年。这份指南包含了大部分Android开发的基础、进阶知识，不仅可以帮助准备...

sealin
2017/02/22
0
0

JavaKotlinAndroidLearn 这是一份关于 Java 、Kotlin 、Android 的学习笔记，既包含对基础知识点的介绍，也包含对一些重要知识点的源码解析，笔记的大纲如下所示： Java 重拾Java（0）-基础知...

08/08
0
0
JVM系列第8讲：JVM 垃圾回收机制

11/21
0
0

10/11
0
0

08/13
0
0

16分钟前
2
0
Elasticsearch安装与配置

23分钟前
1
0

23分钟前
0
0

https://infura.io/dashboard 注册一个帐号 添加一个project 可选择主网或者其他网络，然后复制地址放进pom.xml中 复制智能合约地址复制到pom.xml中 复制任意一个帐号的private key到pom.xml...

30分钟前
3
0
vue+koa2+token 登录验证

https://segmentfault.com/a/1190000017379244?utm_source=weekly&utm_medium=email&utm_campaign=email_weekly...

Js_Mei
33分钟前
3
0