算法notes1

一 位运算

！！！本文重点讲解前移位（前三个）！！！

位运算规则：十进制 —> 二进制

符号位 正数为0，负数为1

1.无符号右移

符号位不变，低位溢出，高位用符号位（第一位都是0，无论正负）填充。没有无符号左移

2.左移（<<）

符号位不变，高位溢出，低位补零（正负都补零）。向左移动一位相当于乘以2

3.右移（>>）

符号位不变，低位溢出，高位用符号位（第一位正数为0，负数为1）填充。向右移动一位相当于除以2

4.位取非（~）

若位数为0，则取反后为1，若为1，取反后为0。

5.位异或（^）

两个数相同位置的进行运算，若两个数均为0或1，则结果为0，否者为1.

6.位或（|）

两个数相同位置的进行运算，若其中一个为1则结果为1，否个结果为0。

7.位与（&）

两个数相同位置的进行运算，若两个位置均为1，那么结果就为1，否者为0。

//上面的结论可以通过下面这个方法来过一遍，加深印象。
public static void print(int num) {
	for (int j = 31; j >= 0; j--) {
		System.out.print((num & (1<<j)) == 0? "0":"1");
	}
}

二 简单排序

1.选择排序

从0_n-1，1n-1，2~n-1 … n-2~n-1,选择最小的依次放入0，1…n-2

对一个数组进行排序，

首先，从0~n-1中选择最小的放在第一个位，

然后，从1~n-1中选择最小的放在第二个位，

…

//选择排序
public static void easy(int[] arr) {
	for (int i = 0; i < arr.length; i++) {
		int minIndex = i;
		for (int j = i+1; j < arr.length; j++) {
			minIndex = arr[minIndex] < arr[j] ? minIndex:j;
		}
		swap(arr,i,minIndex);
	}
}

2.冒泡排序

它重复地走访过要排序的元素列，依次比较两个相邻的元素，

如果顺序错误就把他们交换过来。

走访元素的工作是重复地进行，直到没有相邻元素需要交换。

//冒泡排序一（根据自己所想写的）
public static void bubble(int[] arr) {
	for (int i = 0; i < arr.length-1; i++) {
		for (int j = i+1; j < arr.length; j++) {
			if (arr[i] > arr[j]) {
				swap(arr, i, j);
			}
		}
	}
}


//冒泡排序二
public static void bubble(int[] arr) {
	int N = arr.length;
	for (int i = N-1; i >= 0; i--) {
        // 注释 01  12  23  34 ... (i-1) i
		for (int j = 1; j <= i; j++) {
			if (arr[j] < arr[j-1]) {
				swap(arr, j, j-1);
			}
		}
	}
}

3.插入排序

在一个数组中，将未排序的数与已经排序好的数进行比较，

如果顺序错误就把他们交换过来。其他未排序的执行相同操作。

//插入排序一
public static void insert(int[] arr) {
	for (int i = 1; i < arr.length; i++) {
		int minIndex = i;
		while (minIndex - 1 >= 0 && arr[minIndex - 1] > arr[minIndex]) {
			swap(arr, minIndex-1, minIndex);
			minIndex--;
		}
	}
}

//插入排序二
public static void insert(int[] arr) {
	for (int i = 1; i < arr.length; i++) {
		for (int pre = i - 1; pre >= 0 && arr[pre] > arr[pre+1]; pre--) {
			swap(arr, pre, pre+1);
		}
	}
}

作者是算法小白，此笔记主要是通过看左神算法视频新手入门视频的个人总结，希望此内容能够帮助到大家，同时也欢迎大家评论和指正。如果对你有所帮助的话可以点赞鼓励一下！！！感谢~