Java基础算法

时间：2024-02-21 22:49:52

排序算法

冒泡排序

冒泡排序是一种简单的排序算法，它的工作原理是通过重复遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。这个过程会重复地进行，直到没有再需要交换，也就是该数列已经排好序了

  1. 比较相邻元素：在数列中，从第一个元素开始，依次比较相邻的两个元素。
  2. 交换元素：如果第一个元素比第二个元素大，则交换它们的位置。

代码如下

public class test01 {
    public static void main(String[] args) {
        int[] array = {2,5,6,8,7,9,5,4};
        for(int i = 0,n =array.length;i<n-1;i++){
            boolean isok = true;
            for (int k =0;k<n-1-i;k++){
                if(array[k] >array[k+1]) {
                    // 交換相邻元素
                    array[k] = array[k] ^ array[k + 1];
                    array[k + 1] = array[k] ^ array[k + 1];
                    array[k] = array[k] ^ array[k + 1];
                    isok = false;
                }
            }
            // 冒泡排序优化 如果数组本来就是有序，则可以节省资源
            if (isok){
                break;
            }
        }
    }
}

 乱序算法

 乱序算法就是希望打乱一个基本有序的序列，越乱越好

public class test02 {
    public static void main(String[] args) {
        int[] array = {1,2,3,4,5,6,7,8,9};

        for (int i  =array.length-1;i>0;i--){
            int rodm = (int) (Math.random()*i);
            array[rodm]  = array[rodm] ^ array[i];
            array[i]  = array[rodm] ^ array[i];
            array[rodm]  = array[rodm] ^ array[i];
        }
    }
}

查找算法

线性查找（数组无序）

public class test03 {
    public static void main(String[] args) {
        int[] array = {2,5,6,8,7,9,5,4};
        int target = 6;
        int index = -1;
        for (int i = 0;i<array.length;i++){
            if(array[i]==target){
                index =i;
            }
        }
    }
}

二分查找（有序）

二分查找，也称为折半查找，是一种高效的查找方法。它的基本思想是将目标值与线性表中间的元素进行比较，如果目标值小于中间元素，则在数组的左半部分继续查找，否则在右半部分查找，不断缩小搜索范围，直到找到目标值或确定目标值不存在为止。二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。时间复杂度为O(logn)。

public class test03 {
    public static void main(String[] args) {
        int[] array = {1,2,3,4,5,6,7,8,9};
        int min = 0;
        int target = 5;
        int index = -1;
        int max = array.length-1;
        while (min <=max) {
            int mid = (min + max) >> 1;
        if (array[mid] == target){
            index  = mid;
            break;
        }else if(array[mid] <target){
            min = mid + 1;
        }else if(array[mid] >target){
            max = mid - 1;
        }
        }
        System.out.println(index);
    }
}

旋转查找

分为左旋和右旋

public class test04 {
    public static void main(String[] args) {
        int[] array = {1,2,3,4,5,6,7,8,9};
        //右旋
        for (int j =0;j<3;j++) {
            for (int i = array.length - 1; i > 0; i--) {
                array[i] = array[i] ^ array[i - 1];
                array[i - 1] = array[i] ^ array[i - 1];
                array[i] = array[i] ^ array[i - 1];
            }
        }
        System.out.println(Arrays.toString(array));
        int[] array2 = {1,2,3,4,5,6,7,8,9};
        //左旋
        for(int i = 0;i<array2.length-1;i++){
            array2[i] = array2[i] ^ array2[i+1];
            array2[i+1] = array2[i] ^ array2[i+1];
            array2[i] = array2[i] ^ array2[i+1];
        }
        System.out.println(Arrays.toString(array2));
    }
}

相关文章