JAVA排序

一、排序

1、冒泡排序

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

原理

冒泡排序的原理： 每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。

而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。

//将a进行升序排列
    public static void bubbleSort(int a[]){
        //控制排序趟数
        for (int i = 0; i < a.length-1; i++) {
            //内层循环控制的是每趟排序中前后相邻两个位置的数比较交换的过程
            //j表示的是比较的数的下标位置，且以前面的位置为参照
            for (int j = 0; j < a.length-i-1; j++) {
                //相邻两个位置前面的位置的数如果大于后面的位置则进行交换
                if(a[j]>a[j+1]){
                    //交换相邻位置的数
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
    }

2、二分查找

二分查找：也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

image-20220505111102457

image-20220507114457392

​
public class Demo2 {
​
    public static void main(String[] args) {
        //二分法查找(折半查找)
        int[] nums = {1,3,5,6,7,8,11,13,17};
        int index = binarySearch(nums,11);
        if(index==-1) {
            System.out.println("该数组中，没有要找的数!");
        }else {
            System.out.println("已找到，下标为:"+index);
        }
    }
​
    private static int binarySearch(int[] nums, int searchNum) {
        //声明左右位置
        int left = 0;
        int right = nums.length-1;
        while(right>=left) {
            //找到数组的中间位置
            int mid = (left+right)/2;
            //进行数的比较
            //如果相等，说明找到了，返回下标
            if(nums[mid]==searchNum) {
                return mid;
            }
            //如果中间位置的数大于要查找的数，进入左边范围内再找，所有将右边界向左移动到mid-1的位置。
            if(nums[mid]>searchNum) {
                right = mid - 1;
            }
            //如果中间位置的数小于要查找的数，进入右边范围内再找，所有将左边界向右移动到mid+1的位置。
            if(nums[mid]<searchNum) {
                left = mid + 1;
            }
        }
        //返回-1代表当前数组中没有要查找的数
        return -1;
    }
​
}
​

3、插入排序

插入排序(InsertionSort)，一般也被称为直接插入排序。

对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表

。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

image-20220505111446116

public class Demo3 {
​
    public static void main(String[] args) {
        //插入排序
        //将数组分为两个区域
        //一个排序区，一个待排区
        //每次从待排区拿出第一个数，和排序区每个数，从后往前比较，如果比循环数小，则继续往前
        //直到循环结束，插入到排序区的第一位
        //如果找到比插入数小的，则插入到该数的后面
        //  12,45,7,30,13
        //12                45,7,30,13
        //12,45             7,30,13
        //7,12,45           30,13
        //7,12,30,45        13
        //7,12,13,30,45
        int[] nums = {12,45,7,30,13};
        //外层循环，只循环待排区
        for (int i = 1; i < nums.length; i++) {
            //待排区的第一个数就是要插入排序区的数字
            int key = nums[i];
            //内层循环是从排序区的最后一位循环到第一位
            int j = i-1;
            //1、排序区从后往前循环完了
            //2、待排数字大于排序区某个数
            while(j>=0&&key<nums[j]) {
                nums[j+1] = nums[j];
                j--;
            }
            //将待排数字插入到指定位置
            nums[j+1] = key;
        }
        
        for (int i : nums) {
            System.out.println(i);
        }
    }
​
}
​

二、比较器

1、 比较器介绍

第一个规则：接口是不可以实例化的，即接口不可以创建对象。在JavaSE中比较有名的接口就是比较器。而比较器有两个

  • 内置比较器 ： public interface Comparable<T> {}-> public int compareTo(T o);

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
​
public class Test {
​
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ArrayList<Emp> list = new ArrayList();
        Emp emp1 = new Emp("zs",5000);
        Emp emp2 = new Emp("ls",15000);
        Emp emp3 = new Emp("ww",3500);
        Emp emp4 = new Emp("tq",25000);
        list.add(emp1);
        list.add(emp2);
        list.add(emp3);
        list.add(emp4);
        for (Emp emp : list) {
            System.out.println(emp);
        }
        System.out.println("===================================");
        //要求对员工集合进行工资的升序排序
//      Arrays.sort(a);
        //使用工具类Collections提供的sort方法对ArrayList进行排序
        Collections.sort(list);
        for (Emp emp : list) {
            System.out.println(emp);
        }
        
    }
​
}
//1、如果要将ArrayList中的Emp元素进行，需要Emp类实现Comparable接口
//2、Comparable接口泛型要与当前类的类型一致
//3、Emp类需要重写compareTo(Emp o)方法
//4、在compareTo(Emp o)中写出排序是升序还是降序
//5、用当前对象的某个属性减去参数对象的相同属性，升学，反过来则是降序。
class Emp implements Comparable<Emp>{
    private String name;
    private int salary;
    
    public Emp() {
        super();
    }
    public Emp(String name, int salary) {
        super();
        this.name = name;
        this.salary = salary;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getSalary() {
        return salary;
    }
    public void setSalary(int salary) {
        this.salary = salary;
    }
    @Override
    public String toString() {
        return "Emp [name=" + name + ", salary=" + salary + "]";
    }
    @Override
    public int compareTo(Emp o) {
        // TODO Auto-generated method stub
        return o.getSalary()-this.getSalary();
    }
    
    
    
}

  • 外置比较器 : public interface Comparator<T> {} -> int compare(T o1, T o2);

import java.util.ArrayList;
import java.util.Arrays;
​
public class Test {
    public static void main(String[] args) {
        ArrayList<Emp> list = new ArrayList();
        Emp emp1 = new Emp("zs",5000);
        Emp emp2 = new Emp("ls",15000);
        Emp emp3 = new Emp("ww",3500);
        Emp emp4 = new Emp("tq",25000);
        list.add(emp1);
        list.add(emp2);
        list.add(emp3);
        list.add(emp4);
        Emp[] emps2 = {emp1,emp2,emp3,emp4};
        for (Emp emp : emps2) {
            System.out.println(emp);
        }
        System.out.println("===================================");
        //要求对员工集合进行工资的升序排序
        //使用工具类Collections提供的sort方法对ArrayList进行排序
        Compare2 com = new Compare2();
        Arrays.sort(emps2,com);
        //需要传递两个参数，第一个参数是ArrayList对象，第二个参数是外置比较器对象
        
//      Collections.sort(list,com);
        for (Emp emp : emps2) {
            System.out.println(emp);
        }
    }
}
class Emp{
    private String name;
    private int salary;
    
    public Emp() {
        super();
    }
    public Emp(String name, int salary) {
        super();
        this.name = name;
        this.salary = salary;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getSalary() {
        return salary;
    }
    public void setSalary(int salary) {
        this.salary = salary;
    }
    @Override
    public String toString() {
        return "Emp [name=" + name + ", salary=" + salary + "]";
    }
}
import java.util.Comparator;
//编写一个新的类实现外置比较器接口Comparator
//Comparator<Emp>比较器接口的泛型与集合中泛型类型一致
//重写compare方法，传入两个对象，使用它们相同的属性进行比较
public class Compare implements Comparator<Emp> {
    
    @Override
    public int compare(Emp o1, Emp o2) {
        // TODO Auto-generated method stub
        return o2.getSalary()-o1.getSalary();
    }
​
}
​
import java.util.Comparator;
​
public class Compare2 implements Comparator<Emp> {
​
    @Override
    public int compare(Emp o1, Emp o2) {
        // TODO Auto-generated method stub
        return o1.getSalary()-o2.getSalary();
    }
​
}
​

内置是写在类上的（要排序的类上），而外置比较器是在使用的时候现场提供的。无论用哪一个都可以。外置会灵活些，且如果外置和内置共存，外置会覆盖内置。

2、 内置比较器

内置比较器的弊端：如果要更改排序规则，必须要修改源码。

3、 外置比较器

接口是不可以实例化的，接口中的方法没有方法体，所以无法执行，接口创建对象没有意义。接口的价值是声明行为即指定规范。具体的操作由实现类（实现接口的类叫做实现类）完成。