排序
冒泡排序
相邻元素两两比较,大的往后放,第一次完毕,最大值出现在了最大索引处。同理,其他的元素就可以排好。
public static void bubbleSort(int[] arr) {
for(int i=0; i<arr.length-1; i++) {
for(int j=0; j<arr.length-1-i; j++) {
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
选择排序
把0索引的元素,和索引1以后的元素都进行比较,第一次完毕,最小值出现在了0索引。同理,其他的元素就可以排好。
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[j] < arr[i]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
查找
基本查找
针对数组无序的情况
public static int getIndei(int[] arr,int value) {
int indei = -1;
for(int i=0; i<arr.length; i++) {
if(arr[i] == value) {
indei = i;
break;
}
}
return indei;
}
二分查找(折半查找)
针对数组有序的情况
千万不要先排序,再查找,因为查找到的索引和原来的索引已经不是同一索引了
//Jdk源码
private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid;
}
return -(low + 1);
}
以上概念总结于传智播客Java基础课程