数据结构(一)

手撕八大排序第一场

1.冒泡排序


/*
冒泡排序:
思路:相邻两个数进行比较,内循环过一遍后,最大的数到了最右边,就像泡泡一样挤过去,然后外循环减1,第二遍内循环就找出第二大的数。
 时间复杂度O(N*N)
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {};
        if (arr == null || arr.length < 2) { return; } for (int end = arr.length - 1; end > 0; end--) {//end是每次循环的最大值
            for (int i = 0; i < end; i++) { if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }
}

2.选择排序

/*
选择排序
思路:从外循环拿出一个数来和内循环所有数进行比较,交换之后使得这个数最小,如此循环
时间复杂度O(N*N)
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {};
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {//使得i是当前最小的值
                if (arr[j] < arr[i]) {
                    int temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }
}

3.插入排序


/*
插入排序:
思路:将前面的数排好然后新的那个数和前面的数比较,如果大的话不动,如果小就交换,然后再和前面的数比较,以此类推。
就像扑克牌抽牌排序一样。
时间复杂度O(N)-O(N*N)
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {2, 34, 5, 43, 2, 2, 6, 7, 1, 43, 0, -1};
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {//让新数和已排序好的旧数进行比较
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }
}

4.递归


/*
可以用Maste公式求出复杂度
T(N) = aT(N/b)+O(N的d次方)
a:子过程运行次数
N/b:子过程的样本量
O(N的d次方):剩余其它过程的时间复杂度
复杂度:
logba > d ----- O(N的logba)
logba = d ----- O(N的d次方*logN)
logba < d ----- O(N的d次方)
 */
public class Recursion {
    public static void main(String[] args) {
        int[] arr = {2,4,32,567,65,757,5};
        if (arr == null || arr.length < 2) { return; } System.out.println(recursion(arr, 0, arr.length - 1)); } public static int recursion(int[] arr, int L, int R) { if (L == R) return arr[L]; int mid = (L + R) / 2; int leftMax = recursion(arr, L, mid); int rightMax = recursion(arr, mid + 1, R); return leftMax > rightMax ? leftMax : rightMax;
    }
}

5.对数器

用处:检查算法是否正确

import java.util.Arrays;
import java.util.Random;

public class CheckNumberDemo {
    public static void main(String[] args) {

        check(300);


    }
    //检查排序
    public static void check(int time){
        int size = 100;
        int value = 100;
        boolean b = true;
        for(int i=0;i< time;i++){
            int arr1[] = RandomArr(size, value);
            int arr2[] = copyArray(arr1);
            bubbleSort(arr1);
            correctMethod(arr2);
            if(!isEqual(arr1,arr2)){
                b = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        if(b){
            System.out.println("No Bug!!");
        }else{
            System.out.println("Fuck!!");
        }
        int[] arr = RandomArr(size, value);
        printArray(arr);
    }
    //冒泡排序
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) { return; } for (int end = arr.length - 1; end > 0; end--) {//end是每次循环的最大值
            for (int i = 0; i < end; i++) { if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
    }
    //java库的快排
    public static void correctMethod(int[] arr) {
        Arrays.sort(arr);
    }
    //产生一个大小为size,范围正负value的数组
    public static int[] RandomArr(int size, int value) {
        Random ran = new Random();
        int n = ran.nextInt(size);
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = ran.nextInt(value) - ran.nextInt(value);
        }
        return arr;
    }

    //复制数组
    public static int[] copyArray(int[] arr) {
        if (arr == null)
            return null;
        int[] arr1 = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr1[i] = arr[i];
        }
        return arr1;
    }

    //对比两数组是否完全相等
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;


    }

    public static void printArray(int[] arr) {
        if (arr == null)
            return;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + ",");
        }
    }
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注