新手入门篇-位运算、选择排序、冒泡排序、插入排序-灵析社区

打印一个int类型数对应的32位二进制码

int类型占用4个字节，共占32位。int数值范围：-2^31 ~ 2^31 - 1

Integer.MIN_VALUE = -2147483648 对应的二进制为：10000000000000000000000000000000
Integer.MAX_VALUE = 2147483647  对应的二进制为：01111111111111111111111111111111

最高位来标识正负数，1代表负数，0代表整数

举例说明：

5对应的二进制位 00000000000000000000000000000101

101 = 1 * 2^2 + 1 * 2^0 = 4 + 1 = 5

正整数对应的负整数怎么算？正数取反 + 1

比如正数5，对应的负数为-5。

00000000000000000000000000000101 5对应的二进制
11111111111111111111111111111010 取反
11111111111111111111111111111011 加一

-5 对应的二进制码为：11111111111111111111111111111011

代码如下：

    private static void print(int num) {
        for (int i = 31; i >= 0; i--) {
            System.out.print((num & (1 << i)) == 0 ? "0" : "1");
        }
        System.out.println();
    }

选择排序

思路：选择排序就是选择最小数，依次放到指定的位置上。

0 ~ N-1 从第0位到N-1位，选择一个最小数，放到第0位置上。

1 ~ N-1 从第1位到N-1位，选择一个最小数，放到第1位置上。

2 ~ N-1 从第2位到N-1位，选择一个最小数，放到第2位置上。

public class Code03_SelectSort {

    /**
     * 0 ~ N-1 从第0位到N-1位选择一个最小数，放到第0位上
     * 1 ~ N-1 从第1位到N-1位选择一个最小数，放到第1位上
     * 2 ~ N-1 从第2位到N-1位选择一个最小数，放到第2位上
      */
    public static void selectSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        // 外层循环控制循环次数
        for (int i = 0; i < N; i++) {
            // 假设每次循环第一个数为最小
            int mixValueIndex = i;
            // 找最小数
            for (int j = i + 1; j < N; j++) {
                mixValueIndex = arr[j] < arr[mixValueIndex] ? j : mixValueIndex;
            }
            // 交换位置
            swap(arr, i, mixValueIndex);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

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

    public static void main(String[] args) {
        int[] arr = {10, 5, 8, 2, 1, 4, 9, 3, 2, 0};
        print(arr);
        selectSort(arr);
        print(arr);
    }
}

冒泡排序

思路：

每次比较相邻的两个数的大小，两两交换，第一趟下来，最大数在数组的最右边，依次类推。

0 ~ N-1

0 ~ N-2

0 ~ N-3

0 ~ end

public class Code04_BubbleSort {

    /**
     * 相邻两位，两两互换
     * 0 ~ n-1
     * 0 ~ n-2
     * 0 ~ n-3
     * 0 ~ end
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        // 外层循环控制循环多少次
        for (int end = N - 1; end >= 0; end--) {
            // 内存循环控制两两交换
            // 0 1  1 2  2 3 ...
            for (int second = 1; second <= end; second++) {
                if (arr[second - 1] > arr[second]) {
                    swap(arr, second - 1, second);
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

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

    public static void main(String[] args) {
        int[] arr = {10, 5, 8, 2, 1, 4, 9, 3, 2, 0};
        print(arr);
        bubbleSort(arr);
        print(arr);
    }
}

插入排序

思路：类似玩扑克牌，左边已经排好序，每次来一张牌，从右向左进行比较，比较完后，从左到右都是已经排好序了。

0 ~ 0 已经排好序了（第一张牌就是有序的）

0 ~ 1 排好序

0 ~ 2 排好序

0 ~ 3 排好序

0 ~ N 排好序

public class Code04_InsertSort {

    /**
     * 插入排序类似玩扑克牌，每次来的牌插入之前已经排好序的牌中，类似插入一样。
     */
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        for (int end = 1; end < N; end++) {
            int newNumIndex = end;
            while ((newNumIndex - 1) >= 0 && arr[newNumIndex - 1] > arr[newNumIndex]) {
                swap(arr, newNumIndex - 1, newNumIndex);
                newNumIndex--;
            }
        }
    }
    
    public static void insertSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        for (int end = 1; end < N; end++) {
            for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
                swap(arr, pre, pre + 1);
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

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

    public static void main(String[] args) {
        int[] arr = {10, 5, 8, 2, 1, 4, 9, 3, 2, 0};
        print(arr);
        insertSort(arr);
        print(arr);
    }
}