二分查找：
public static boolean search(int[] arr,int key){
insertSort1(arr); //查找前先要排序
int left = 0,right = arr.length-1;
boolean flag = false;
if(key < arr[left] || key > arr[right])
flag = false;
while(left <= right){
int mid = (left+right)/2;
if(arr[mid] == key)
flag = true;
if(key > arr[mid]){
left = mid+1;
}else {
right = mid-1;
}
}
return flag;
}
快速排序：
public static void quickSort(int[] arr,int leftIndex,int rightIndex){
int left = leftIndex,right = rightIndex;
if(leftIndex < rightIndex){ //leftIndex==rightIndex时会不断执行递归造成栈溢出
int pos = arr[left]; //定义一个标志位，放在if后面因为在右递归时有+1操作防止越界
while(left < right){
while(left < right && arr[right] >= pos){ //找到一个比标志位小的数arr[right]
right--;
}
while(left < right && arr[left] <= pos){ //找一个比标志位大的数arr[left]
left++;
}
swap(arr, left, right);//交换arr[right]和arr[right]
}
swap(arr,leftIndex,left); //让标志位归位
System.out.println("标志位："+pos);
quickSort(arr, leftIndex, left);
quickSort(arr, left+1, rightIndex);
}
}
例如：对数组int[] arr = {6,3,1,5,2,9,7,8,12,11}排序，输出如下
折半插入排序：
public static void insertSort1(int[] arr){ //折半插入排序
for(int i = 0;i < arr.length-1;i++){
int low = 0,high = i;
int temp = arr[i+1];
while(low <= high){ //折半查找插入点
int mid = (low+high)/2;
if(temp > arr[mid])
low = mid+1;
else
high = mid-1;
}
for(int j = i;j > high;j--){ //移动数组，为插入准备
arr[j+1] = arr[j];
}
arr[high+1] = temp; //插入
}
}
直接插入排序：
public static void insertSort2(int[] arr){ //直接插入排序
for(int i = 0;i < arr.length-1;i++){
for(int j = i;j >= 0;j--){
if(arr[j+1] < arr[j]){
swap(arr, j,j+1);
}
}
}
}
交换函数：
public static void swap(int[] arr, int i,int j) {
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
生成随机数组：
public static int[] creatArray(int count,int maxNum){
int [] arr = new int[count];
for(int i=0;i< count;i++){
arr[i] = new java.util.Random().nextInt(maxNum); //生成[0～maxNum)的随机数
}
return arr;
}