1.冒泡排序
//原理:依次由数组的第一个和第二个元素进行比较，
//根据大小关系交换位置。然后再将第二个与第三进行比较换位，依次循环下去
//代码实现:
public static void main(String[] args) {
int[] arr = {45,23,32,25,66,64,89,12};
sort(arr);
}
//冒泡排序方法抽取
public static void sort(int[] arr){
//最外层循环决定了循环次数
for(int i = 0; i < arr.length - 1; i++){
for (int j = 0; j < arr.length - i - 1; j++){//内层循环减1,防止数组越界，减i是为了提高效率
if (arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
String str = print(arr);
System.out.println(str);
}
//再写个打印数组的方法
public static String print(int[] arr){
StringBuffer sb = new StringBuffer();
for (int i = 0; i < arr.length; i++){
sb = sb.append(arr[i]).append(" ");
}
String str = new String(sb);
return str;
}
}
2.选择排序
//原理:用一个位置上的元素依次和其它位置上的比较，有大小关系就交换位置，
//那么一次比较完成后，处在最前面的元素(要么最大,要么最小)。接下来排除第一个位置，从第二个元素开始向其它位置进行比较。
//代码实现:
public static void main(String[] args) {
//数组选择排序
int[] arr = {48,34,23,33,55,64,64,63,98,78,88};
selectSort(arr);
print(arr);
}
//抽取选择排序方法
public static void selectSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++){//外层循环决定总共的循环次数
for (int j = i+1; j < arr.length; j++){
if (arr[i] > arr[j]){
//我们一次大循环，就是相当于拿到数组的第一个元素和后面的每个元素相比较，然后换位置
//与本身比较没意义，所以j从i+1开始
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
//抽取打印方法
//如果某个方法只想让本类使用，就可以定义为私有的
private static void print(int[] arr){
for (int i = 0; i < arr.length; i++){
System.out.printf(arr[i] + " ");
}
}
3. 二分查找
//原理:(前提是有序)查找元素对应的索引
//代码实现:
public static void main(String[] args) {
//数组二分查找
//int min = 0;
//int max = arr.length - 1;
//int mid = (min + max)/2;这些都是索引值
int[] arr = {12,14,15,17,35,56,64,78,79,87,98,99,100};
//举例:现在的min对应12，max对应99，mid对应64
//我们要查找17，拿17和mid比较，发现小了，那么我们要改变max就为mid-1,min不变。mid随之改变
//如此循环几次就可以找到17在此数组中的索引
System.out.println(getIndex(arr,35));
System.out.println(getIndex(arr,87));
System.out.println(getIndex(arr,102));
}
//二分查找
public static int getIndex(int[] arr, int value){
int min = 0;
int max = arr.length - 1;
int mid = (min + max)/2;
while(arr[mid] != value){
if (arr[mid] < value){
//要找的数比中间的数更大
min = mid + 1;
}else if(arr[mid] > value){
max = mid - 1;
}
//无论是大于还是小于都需要重新计算mid的值
mid = (min + max)/2;
if (min > max){//说明数组中已经没有这个值了，直接返回-1就好
return -1;
}
}
return mid;
}
4. Arrays类的简单使用
//Arrays类的使用，掌握三个方法]
//1. public static String toString(int[] a):数组转字符串
//2. public static void sort(int[] a):排序->底层用的快速排序法(看着复杂，效率是最高的)
//3. public static int binarySearch(int[] a, int value);二分查找
int[] arr = {45,55,33,24,7,455,332};
String str1 = Arrays.toString(arr);
System.out.println(str1);
//调用排序的方法
Arrays.sort(arr);//默认是从小到大排序
print(arr);
//二分查找
int[] arr2 = {12,14,17,35,67,87,88,95,97};
int result = Arrays.binarySearch(arr2,87 );
System.out.println(result);
System.out.println(Arrays.binarySearch(arr2,13));
//上面这个打印的是-2.这个的意思是您要查找的数不在这个数组中，且它是给我们返回了这个您要
//查找的数，如果要放到这个数组中，实际的位置(index)取反并减1
}
private static void print(int[] arr){
for (int i = 0; i < arr.length; i++){
System.out.println(arr[i] + " ");
}
}
