java数组详解(包括数据的初始化、比较、排序、重要方法）(三)
[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。
[java]
public class Study {
public static void main(String[] args) {
int[] a = { 5, 4, 2, 4, 9, 1 };
halfInsert(a);
for (int i : a) {
System.out.println(i);
}
}
public static int[] halfInsert(int[] R) {
for (int i = 1; i < R.length; i++) {// 从第二个元素开始，需要做n-1趟插入排序，第一个元素自成有序区
int temp = R[i];// 暂存
int low = 0;// 定义从第一个元素开始为有序区
int high = i - 1;// 有序区的元素从一个开始逐渐增加
// low和high分别指向有序区中的第一个和最后一个元素
while (low <= high) {// 寻找在有序区中插入的位置，最后使high
// 为high+1；也是low的位置
int m = (low + high) / 2;// 有序区的中间元素
if (temp < R[m]) {// 如果比中间的元素小，则插入位置在低半区
high = m - 1;
} else
// 否则，插入位置在高半区
low = m + 1;
}
for (int j = i; j > low; j--) {// 把从low开始以后或high+1以后的元素向后移动，插入
R[j] = R[j - 1];// 移动元素
}
R[low] = temp;// 插入在合适的位置
}
return R;
}
}
二分查找：
二分查找原理很容易懂，想象为二叉查找树就明白了。
[java]
int binarySearch(int[] a, int value){
int low = 0;
int high = a.length-1;
while(low <= high){
mid = (low+high)/2; //**
if (a[mid] == value)
return mid;
else if (a[mid] > value)
high = mid-1;
else
low = mid +1;
}
return -1;
}
5、快速排序算法
通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。
[java]
void quickSort(int[] a, int low, int high) {
p = get(a, low, high);
quickSort(a, low, p-1);
quickSort(a, p+1, high);
}
int get(int[] a, int low, int high){
compare = a[low];
while(low < high){ //无论如何置换, 被置换的都包含compare的值
while(low=compare)
high--;
//在 low
temp = a[low];
a[low] = a[high];
a[high] = temp;
while(low
low++;
//在 lowcompare并置换
temp = a[low];
a[low] = a[high];
a[high] = temp;
}
return low; //while(low==hight)停止循环, 并返回枢轴位置
}
数组重要方法
一、填充数组：Arrays.fill()方法
缺点：填充的数据单一。
用法1：接受2个参数
Arrays.fill（ a1, value ）;
注：a1是一个数组变量，value是一个a1中元素数据类型的值，作用：填充a1数组中的每个元素都是value
例如：
[java]
public class Study {
public static void main(String[] args) {
int[] a = new int[5];
Arrays.fill(a, 1);
for (int i : a) {
System.out.println(i);
}
}
}
输出结果为：
[java]
1
用法2：接受4个参数
第一个参数指操作的数组，第二个和第三个指在该数组的某个区域插入第四个参数，第二个参数指起始元素下标（包含该下标），第三个参数指结束下标（不包含该下标），注意：java的数组下标从0开始
例如：
[java]
public class Study {
public static void main(String[] args) {
int[] a = new int[5];
Arrays.fill(a, 1);
Arrays.fill(a, 1, 3, 2);
for (int i : a) {
System.out.println(i);
}
}
}
结果：
[java]
1
二、复制数组：clone()方法
clone（）方法，限制：全部复制，无法部分的复制。
[java]
public class Study {
public static void main(String[] args) {
int[] a = new int[5];
int[] b;
Arrays.fill(a, 1);
b = a.clone();
for (int i : b) {