java数组笔记和常用方法
1. 数组翻转
public static void reverse(int[] arr){
for (int i = 0; i<arr.length/2; i++){
int temp = arr[i];
arr[i] = arr[arr.length-i-1];
arr[arr.length-i-1] = temp;
}
}
2. 二分法查找有序数组
public static int dichotomy(int[] arr, int search){
int result = 0;
int left = 0;
int right = arr.length-1;
while (left <= right){
int center = (left + right) / 2;
if (arr[center] > search){
right = center - 1;
}else if (arr[center] < search){
left = center + 1;
}else {
result = center;
break;
}
}
if (left > right) {
result = -1;
}
return result;
}
常用排序算法
数组的排序算法很多，实现方式各不相同，
时间复杂度，空间复杂度，稳定性也各不相同：
常见时间复杂度所消耗的时间从小到大排序：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
1. 冒泡排序 （Bubble Sort）
排序思想：
-
比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
-
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
-
针对所有的元素重复以上的步骤，除了最后一个。
-
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较为止。 动态演示：https://visualgo.net/zh/sorting
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++){
int temp = arr[j];
if (arr[j] > arr[j+1]){
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
2. 快速排序
快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一，是迄今为止所有内排序算法中速度最快的一种，快速排序的时间复杂度为O(nlog(n))。
快速排序通常明显比同为O(nlogn)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。
排序思想：
-
从数列中挑出一个元素，称为"基准"（pivot），
-
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
-
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
-
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
动态演示：https://visualgo.net/zh/sorting
public static void quickSort(int[] arr, int start, int end){
if (start > end){
return;
}
int temp = arr[start];
int i = start;
int j = end;
while (i!=j){
while (i<j && arr[j] >= temp){
j--;
}
while (i<j && arr[i] <= temp){
i++;
}
if (j > i){
int ling = arr[i];
arr[i] = arr[j];
arr[j] = ling;
}
}
arr[start] = arr[i];
arr[i] = temp;
quickSort(arr, 0, i-1);
quickSort(arr, i+1, end);
}