数据结构基础（笔记）

查找一个元素是否存在在数组中

输入：数组、目标元素

输出：目标元素所在的索引，若不存在返回-1

public class xianXingChaZhao {
    private xianXingChaZhao(){}         
    //将构造函数私有化，其他类访问这个类时就不能new一个对象，用户就无法创造这个类的对象
    public static int search(int[] data,int muBiao){ 
        for(int i=0;i< data.length;i++){
            if(data[i]==muBiao)
                return i;
        }
        return -1;
    }//静态方法 不需要new一个对象，直接用 类名.方法名即可调用
    public static void main(String[] args){
        int data[]={24,18,12,9,16,66,32,4};
        int muBiao=16;
        xianXingChaZhao xxcz=new xianXingChaZhao();     
        //虽然将构造函数私有化了，但这个main函数是这个类里的，所以还能访问private
        int res = xianXingChaZhao.search(data,muBiao);  
        //静态方法 直接用类名调用（用普通方法new一个对象也可）
        System.out.println(res);
        int result=xianXingChaZhao.search(data,25);
        System.out.println(result);

    }

}

使用泛型修改

public class xxczfx {
    private  xxczfx(){}
    public static  int search(E[] data,E target){    //泛型参数也是泛型E
        for(int i=0;i< data.length;i++){    //循环不变量  data[0,i)中没有找到目标
            //data[i]是类对象，target也是类对象，判断他俩相等不能用==，得用equals
            if(data[i].equals(target))
                return i;
        }//循环体：维持循环不变量（证明算法正确性）
        return -1;
    }
}

自己定义一个测试类Student

public class Student {
    private String name;
    public Student(String name){
        this.name=name;
    }
    @Override
    public boolean equals(Object student){    //覆盖Object父类中的equals方法
       //看调用equals函数的那个对象和参数里的那个对象是否是一个对象，如果是，直接返回true 相等
        if(this == student)     
            return true;
       //看参数传来的对象是否是空对象，如果是，他肯定和调用equals函数的对象不相等，直接返回false
        if(student == null)         
            return false;
       //如果调用equals方法的对象和参数传来的对象不属于同一个类，直接返回false
        if(this.getClass() != student.getClass())      
            return false;
        Student another = (Student) student;  //将student强制转换成Student类型（可能会有bug）
        return this.name.toLowerCase().equals(another.name.toLowerCase());
    }
}

自己定义一个测试数组类

public class ArrayGenerator {
    public static void main(String[] args) {
    }
    //生成一个0到n的测试数组
    public static Integer[] generatorOrderedArray(int n){
        Integer[] array = new Integer[n];
        for(int a=0;a 
main函数测试
 
public class Main{
     public static void main(String[] args) {
        //测试1
        Integer[] data={24,18,12,9,16,66,32,4};     //泛型传入的参数必须是包装类Integar
        int res=xxczfx.search(data,16);  //16是个数，java可以自己把他变成包装类（类型推断）
        System.out.println(res);

        //测试2
        Student[] students={new Student("Alice"),
                            new Student("Bobo"),
                            new Student("Charles")};
        Student Bobo = new Student("bobo");
        int res3 = xxczfx.search(students,Bobo);
        System.out.println(res3);

        //测试3
        int[] datasize ={1000000,10000000};
        for(int n:datasize){
            Integer[] arr1 = ArrayGenerator.generatorOrderedArray(n);   //声明一个测试数组
            int res4=0;
            long startTime = System.nanoTime();  //出现一个时间窗，可以用来计时
            for(int k=0;k<100;k++)                  //测试运行100次这个句子需要多少时间
                 res4 = xxczfx.search(arr1,n);
            System.out.println(res4);
            long endTime = System.nanoTime();   //计时
            double time = (endTime-startTime)/1000000000.0;
            System.out.println("n=" + n +",100 runs:" + time + "s");  //打印时间
        }
    }
}
 
时间复杂度：O(n)
 
二、选择排序法 
非原地排序：每次将还未处理的元素中最小的元素选出来，放在另一个数组最前面。
 
原地排序：遍历数组，将最小的元素取出来，与i交换，i++，继续遍历剩下的未排序元素，重复之前的操作
 
 
 
 
public static >void select(E[] arr){   //实现可比较的泛型E
        //arr[0....i)是有序的，arr[i...n)是无序的
        for(int i = 0;i< arr.length;i++){
            int position=i;
            for(int j=i;j 0 ) {  
                //.compareTo()方法，如果前者大于后者，返回正数,其他类似
                    position = j;
                }
            }
            swap(arr,position,i);
        }

    }
public static void swap(E[] arr,int i,int j){
        E t=arr[i];
        arr[i]=arr[j];
        arr[j]=t;
    }
 
创建一个Student类进行测试
 
public class Student implements Comparable {  //实现Comparable接口
    private String name;
    private int score;
    public Student(String name,int score){
        this.name = name;
        this.score = score;
    }
    @Override
    public int compareTo(Student another){
//       if(this.score> another.score)
//           return 1;
//       else if(this.score
 
创建一个生成数组的类来进行测试
 
public class ArrayGenerator {
    private ArrayGenerator(){}

    
    public static Integer[] generatorOrderedArray(int n){
        Integer[] arr = new Integer[n];
        for(int i = 0; i < n; i++){
            arr[i] = i;
        }
        return arr;
    }

    
    public static Integer[] generatorRandomArray(int n, int bound){
        Integer[] arr1 = new Integer[n];
        Random rnd = new Random();
        for(int i = 0; i < n; i++){
            arr1[i] = rnd.nextInt(bound);
        }
        return arr1;
    }

}
 
创建一个SortingHelper类，用来检查是否排序好和进行运行时间统计
 
public class SortingHelper {
    private SortingHelper(){}

    
    public static > boolean isSorted(E[] arr){
        for(int i = 1; i < arr.length; i++){
            if(arr[i-1].compareTo(arr[i]) > 0)
                return false;
        }
        return true;
    }

    
    public static > void sortTest(String sortName, E[] arr){
        long startTime = System.nanoTime();   //起始时间
        if(sortName.equals("SelectYd"))
            SelectYd.select(arr);
        else if(sortName.equals("SelectedSort"))
            SelectedSort.select(arr);
        else if(sortName.equals("InsertSort"))
            InsertSort.sort(arr);
        else if(sortName.equals("InsertSort2"))
            InsertSort.sort2(arr);
        else if(sortName.equals("InsertSort3"))
            InsertSort.sort3(arr);
        long endTime = System.nanoTime();     //结束时间
        double time = (endTime - startTime)/1000000000.0;

        // 看数组是否已经排序，如果没排序好，抛出一个运行时异常
        if(!SortingHelper.isSorted(arr)){
            throw new RuntimeException(sortName + " failed");
        }
        System.out.println(sortName+", n= "+arr.length+" : "+time + "s");
    }

}
 
main函数进行测试
 
    public static void main(String[] args) {

        //测试用例1（int）
        Integer arr[] = {12,12,34,52,13,42,31,52,68,94};
        SelectYd.select(arr);
        for(int i =0;i< arr.length;i++){
            System.out.print(arr[i] + " ");

        }
        if(!SortingHelper.isSorted(arr)){
            throw new RuntimeException("SelectYd failed");
        }
        System.out.println();

        //测试用例2（student)
        Student[] students = {new Student("Alice",98),
                              new Student("BobO",88),
                              new Student("Charles",100)};
        SelectYd.select(students);
        for(Student student:students){  //为students数组中的每个student循环
            System.out.println(student+"");
        }

        //测试用例3（生成一个随机数组进行排序）
        int[] datasize = {10000,100000};

        for(int n:datasize) {
            Integer[] arr3 = ArrayGenerator.generatorRandomArray(n, n);
            SortingHelper.sortTest("SelectYd",arr3);
        }


    }
 
时间复杂度：O(n^2)
 
三、插入排序法
 
每次处理一个元素，将这个元素插入到前面已经排好序的元素中（处理一个元素时，如果它小于它前面的元素，就与他交换位置，直到插入到合适的位置）
 
  
public static > void sort(E[] arr){
        for(int i = 1; i < arr.length; i++){
//            for(int j = i; j >= 1; j--){    //从i开始和i-1比较
//                if(arr[j].compareTo(arr[j-1]) < 0)
//                    swap(arr,j-1,j);
//                else
//                    break;
//            }
            for(int j = i; j>=1 && arr[j].compareTo(arr[j-1]) < 0; j--){   //因为arr[j].compareTo(arr[j-1]) < 0也是判断循环终止的条件
                swap(arr,j-1,j);
            }
        }
    }

 public static  void swap(E[] arr, int i, int j){
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
插入排序小优化：将要插入的值暂存到一个变量中，j向数组前面遍历，然后用它和j在的元素作比较，如果他小于j所在的元素，arr[j]就赋值给arr[j+1]（第一个[j+1]其实就是要处理的元素位置），遍历完后，将要插入的值放入空出来的位置中
 
 
 public static > void sort2(E[] arr){
        for(int i = 1; i < arr.length; i++){
            E temp = arr[i];
            int j;
            for( j = i; j >= 1; j--){
                if(arr[j-1].compareTo(temp) > 0)
                    arr[j] = arr[j-1];
                else
//                    arr[j] = temp;    //为什么不能放这里，因为如果要在第一个元素插入temp值的话，这里循环条件是j>=1,当j=0时没办法进循环，就没办法赋值
                break;
            }
            arr[j] = temp;
        }

    }
 
时间复杂度：对于有序数组，时间复杂度为O(n),整体复杂度还是O(n^2).