1. 线性查找法（LinearSearch）
1.1 最简单的实现
public class LinearSearch {//创建私有构造对象，不希望其他对象访问这个类private LinearSearch(){}//加上static不需要创建类也能访问public static int search(int data[] , int target){for (int i = 0; i< data.length ; i++){if (i == target)return i;}return -1;}public static void main(String[] args) {int [] data = {23,32,24,53,67,83,15,3};System.out.println(LinearSearch.search(data,24));System.out.println(LinearSearch.search(data,666));}}
- 在这段代码中注意两点
- 加上static不需要创建类也能访问,否则需要先创建类才能使用search方法
- 创建私有构造对象，不希望其他对象访问这个类
1.2 使用泛型
public class LinearSearch {//创建私有构造对象，不希望其他对象访问这个类private LinearSearch(){}//加上static不需要创建类也能访问public static <E> int search(E data[] , E target){for (int i = 0; i< data.length ; i++){if (data[i].equals(target) )return i;}return -1;}public static void main(String[] args) {Integer [] data = {23,32,24,53,67,83,15,3};System.out.println(LinearSearch.search(data,24));System.out.println(LinearSearch.search(data,666));}}
- 注意：
- 在泛型类中不能使用基本数据类型(int,double,long….)，只能使用对应的Integer,Double,Long….，因此data的定义也要从int->Integer
int : 表示传入的参数是一个泛型，返回的是一个int值
1.3 使用自定义类测试时
注意这里的equals比较的只是两个类的地址，因此需要在类中重写equals方法
比如现在要比较Student类中的内容，重写equals方法时要注意，因为该方法是Object的，因此当检测到传入的参数是Object类时才可以重写
1.4 循环不变量
1.5 复杂度分析
- 什么是算法复杂度
常见的几种算法复杂度
- O(n)
- O(n2)：冒泡算法
O(logn):数字n的二进制位数
O(√n):
- O(2n):求长度为n的二进制数字
- O(n!)：求长度为n的数组的所有排列
- O(1)：判断n是否为偶数
- 大小比较：
2. 基础排序方法(SelectionSort)
2.1 选择排序法
2.1.1 基础实现：
- 简单来说就是，（从小到大派的情况下）每次都选择数组里面最小的一个数，然后交换位置
public class SelectionSort {private SelectionSort(){}public static void sort(int arr[]){for (int i=0 ;i<arr.length;i++){int minIndex = i;for (int j=i; j<arr.length;j++){if (arr[j]<arr[minIndex]){minIndex = j;}}swap(arr,i,minIndex);}}private static void swap(int[] arr, int i, int minIndex) {int t = arr[i];arr[i] = arr[minIndex];arr[minIndex] = t;}public static void main(String[] args) {int arr[] = {34,32,3,4,43,23,15,5};SelectionSort.sort(arr);for (int i : arr) {System.out.print(i+" ");}}}
2.1.2 使用泛型
- 使用泛型要用到比较时，使用
<E extends Compareable>, 然后后面的比较函数使用compareTo(),当返回的值等于0时说明相等，小于0时就是前面比后面小，大于0就是前面比后面大
```java public class SelectionSort {private SelectionSort(){}
public static
void sort(E arr[]){ for (int i=0 ;i<arr.length;i++){int minIndex = i;for (int j=i; j<arr.length;j++){if (arr[j].compareTo(arr[minIndex])<0){minIndex = j;}}swap(arr,i,minIndex);}
}
private static
void swap(E[] arr, int i, int minIndex) { E t = arr[i];arr[i] = arr[minIndex];arr[minIndex] = t;
}
public static void main(String[] args) {
Integer arr[] = {34,32,3,4,43,23,15,5};SelectionSort.sort(arr);for (int i : arr) {System.out.print(i+" ");}
}
}
<a name="IVAOa"></a>### 2.1.3 复杂度分析<br />测试结果：<br />- 当n相差10倍时，时间复杂度却差了100倍，这就是 复杂度=n2的意义<a name="3IVL7"></a>## 2.2 插入排序法<a name="JCmVJ"></a>### 2.2.1 实现一个插入算法- 插入算法的原理- 过程：i的位置一格格移，然后j开始和i的位置一样(j=i)跟前面的数去一个个比较，遇到比他大的那就把他后移,直到遇到一个比他小的数的时候停止(前面已经排好了)```javapublic static <E extends Comparable> void sort(E[] arr){for (int i = 0 ; i < arr.length ; i++){//之所以要j-1，是因 为要保证他前面那个位置是有元素的for (int j = i ; j-1 >=0 ; j--){if (arr[j].compareTo(arr[j-1]) < 0){swap(arr,j,j-1);}else break;}//可以简写成下面这样//for (int j = i ; j-1 >= 0 && arr[j].compareTo(arr[j-1]) < 0; j--){// swap(arr,j,j-1);//}}}
2.2.2 插入排序优化
- 优化图示：
- 过程：先把当前位置的数提出来，然后开始拿这个数和前面的数依次去比较，如果前面的数要大，那就直接把后面的数覆盖掉，直到前面的数比你小；然后i++，再重复上述操作
2.2.3 插入排序法的重要特性
- 对于有序数组，插入排序法复杂度是O(n),但复杂度要看整体，所以还是O(n^2)
- 但是选择排序法永远是O(n^2)
- 因此对于基本上有序的数组，插入排序将成为O(n)的算法
若有收获，就点个赞吧
0 人点赞
