一、算法时间复杂度
1.1、衡量一个程序（算法）执行时间的两种方法
- 事后统计。程序必须执行。需要再同一计算机的相同状态下运行，才能比较哪个算法速度更快
- 事前估算。通过分析某个算法的时间复杂的来判断
1.2、时间频度（Tn）
一个算法花费的时间与算法重语句的执行次数成正比，执行语句越多，花费时间越多。
二、排序算法
2.1、冒泡 排序
基本思想：通过对待排序序列从前往后（下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，像水底的气泡一样逐渐往上冒。时间复杂程度为O(n^2)
public static void encapsulationBubbleSort(int[] arr){
int temp = 0;
boolean flag = false;
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]){
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
if (!flag){
break;
}else {
flag = false;
}
System.out.println("这是第"+i+"次排序");
System.out.println(Arrays.toString(arr));
System.out.println("-----------------------");
}
}
2.2、选择排序
基本思想：每轮排序选出最小值，一次排序
public static void sort(int[] arr){
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
int min = arr[i];
for (int j = i+1; j < arr.length ; j++) {
if (arr[minIndex] > arr[j]){
minIndex = j; //重置minIndex
min = arr[j]; //重置min
}
}
arr[minIndex] = arr[i]; //交换最小值坐标
arr[i] = min;
}
}
2.3、插入排序
思想：将一组数据分成两组，分别将其称为有序组与待插入组。每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。
public static void InsertSort(int[] arr){
// arr[] = {1, 8, 6, -3, 2};
for (int i = 1; i < arr.length ; i++) {
int insertVal = arr[i];
int insertIndex = i - 1;
while (insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
arr[insertIndex+1] = insertVal;
}
}
2.4、希尔排序
思想：进行分组交换，例如
10个数分为（10/2）5组，大小对比交换；再分为（5/2)2组，大小对比交换；
public static void shellSortMove(int[] arr){
for (int gap = arr.length/2; gap >0 ; gap/=2) {
for (int i = gap; i < arr.length ; i++) {
int j = i;
int temp = arr[j];
if (arr[j] <arr[j - gap]){
while (j-gap >=0 &&temp <arr[j-gap]){
arr[j] = arr[j-gap];
j-=gap;
}
arr[j] = temp;
}
}
}
}
2.5、快速排序
思路：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
public static void quickSort2(int[] arr, int left, int right){
if (left >= right)return;
int l = left;
int r = right;
int pivot = arr[left];
while (l < r){
while (l < r && arr[r] >=pivot){
r--;
}
if (l < r){
arr[l] = arr[r];
}
while (l < r && arr[l] <=pivot){
l++;
}
if (l < r){
arr[r] = arr[l];
}
if (l >=r){
arr[l] = pivot;
}
}
System.out.println(Arrays.toString(arr));
quickSort2(arr,left,r-1);
quickSort2(arr,r+1,right);
}
2.6、归并排序
思路：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。类似二叉树
public static int[] mergeSort(int[] nums, int l, int h) {
if (l == h)
return new int[] { nums[l] };
int mid = l + (h - l) / 2;
int[] leftArr = mergeSort(nums, l, mid); //左有序数组
int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
int m = 0, i = 0, j = 0;
while (i < leftArr.length && j < rightArr.length) {
newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
}
while (i < leftArr.length)
newNum[m++] = leftArr[i++];
while (j < rightArr.length)
newNum[m++] = rightArr[j++];
return newNum;
}
public static void main(String[] args) {
int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
int[] newNums = mergeSort(nums, 0, nums.length - 1);
for (int x : newNums) {
System.out.println(x);
}
}
2.7、基数排序
思路：基数排序（桶子法）。通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。空间换时间，数据过大会导致内存溢出。
负数不建议使用基数。
三、查找算法
3.1、二分查找
二分算法需保证算法是有序的。
思路：每次从中间开始对比，依次折中。
public static ArrayList binarySearch(int[] arr,int low,int top,int value){
ArrayList<Integer> resIndex = new ArrayList<>();
while (low < top ){
int mid = (low+top)/2;
if (value<arr[mid]){
top = mid;
}
else if (value > arr[mid]){
low = mid;
}
else if (value == arr[mid]){
// return mid;
int temp = mid-1;
while (true){
if (temp<0||arr[temp]!=value){
break;
}
resIndex.add(temp);
temp--;
}
resIndex.add(mid);
int temp2 = mid+1;
while (true){
if (temp2>arr.length||arr[temp2]!=value){
break;
}
resIndex.add(temp2);
temp2++;
}
return resIndex;
}
if (top-low == 1){
return null;
}
}
return null;
}
3.2、插值查找法（查找算法）
公式：int mid = left +(right-left)*(findVal-arr[left])/(arr[right]-arr[left])
特地：需要数据有序且均匀分布
评论区