uni_shiki

算法与数据结构_1_选择排序、冒泡排序、异或运算、插入排序、二分法

  • 2023-03-17
  • 作者 uni_shiki
  • ~3.61K 字

 

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void selectionSort(int[] arr)
{
	if (arr == null || arr.length < 2)
	{
		return;
	}
	for (int i = 0; i < arr.length - 1; i++) // i ~ N-1
	{
		int minIndex = i;
		for (int j = i + 1; j < arr.length; j++) // i ~ N-1 上找最小值的下标
		{
			minIndex = arr[j] < arr[minIndex] ? j : minIndex;
		}
		swap(arr, i, minIndex); // 每轮找出最小的放前面
	}
}

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


冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void bubbleSort(int[] arr)
{
	if (arr == null || arr.length < 2)
	{
		return;
	}
	for (int e = arr.length - 1; e > 0; e--) // 0 ~ e
	{
		for (int i = 0; i < e; i++)
		{
			if (arr[i] > arr[i + 1])
				{
					swap(arr, i, i + 1); // 每轮把最大的放到最后
				}
		}
	}
}

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

异或运算(^)

  • 相同为0，不同为1
  • 还可以理解成：无进位相加
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    a^b = 1
    0^1 = 1
    1^0 = 1
    0^0 = 0
    1^1 = 0

    a: 10110
    b: 00111
    a^b:
       10001
    性质：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    1.
    0^N = N : 0跟任何数N异或，都是N
    N^N = 0 : 任何数跟自己异或，都得0

    2.
    满足交换律、结合律
    a^b = b^a
    (a^b)^c = a^(b^c)

    3.同一批数异或运算，谁先谁后的顺序不影响结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void swap(int[] arr, int i, int j)
{
	arr[i] = arr[i] ^ arr[j];
	arr[j] = arr[i] ^ arr[j];
	arr[i] = arr[i] ^ arr[j];
}


解释：
交换两个数的值：
int a = 17;
int b = 23;

a = a^b;
b = a^b;
a = a^b;

假设
int a = 甲;
int b = 乙;

a = a^b; // a = 甲^乙 , b = 乙
b = a^b; // a = 甲^乙 , b = 甲^乙^乙 = 甲^0 = 甲
a = a^b; // a = 甲^乙^甲 = 0^乙 = 乙, b = 甲

前提：a和b在内存里是两块独立的区域，a的值可以等于b的值，但它们指向的内存需是两块东西

面试题：

  • 在一个整形数组int[] arr中，
    1）已知只有一种数出现了奇数次，其他的所有数都出现了偶数次
    怎么找到出现了奇数次的数
    2）已知有两种数出现了奇数次，其他的所有数都出现了偶数次
    怎么找到这两种数
    要求：时间复杂度O(N),额外空间复杂度O(1)

key:

1) 

1
2
3
4
5
6
7
int eor = 0;
将数组各个数与eor异或
假设数组[a,b,c]
eor = eor ^ a;
eor = eor ^ b;
eor = eor ^ c;
最后eor就等于出现了奇数次的这个数

2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int eor = 0;
同样将数组各个数与eor异或
假设[    ]数组中只有a和b出现了奇数次，其他都出现了偶数次
先让eor从头异或到尾
结束时 eor = a^b ,
eor != 0
eor 的某一位是 1
假设它的第八位是 1
说明a的第八位和b的第八位不同

这时可以把整个数组分为两类
一类是第八位为 1
一类是第八位为 0
a和b只会分别在一类中

再找一个变量eor2
eor2只去异或第八位是 1 的数
eor2就得到了a或b
eor2 再与eor异或，得到另一个数


代码实现：
int eor = 0;
for (int curNum : arr)
{
	eor ^= curNum;
}
// eor = a ^ b
// eor != 0
// eor必然有一个位置上是1
int rightOne = eor & (~eor + 1); // 提取出最右的1

// eor              : 1010111100
// ~eor             : 0101000011 取反
// ~eor + 1         : 0101000100 取反+1
// eor & (~eor + 1) : 0000000100 与运算，提取出最右侧的1
// **这是一个常规操作**

int onlyOne = 0; // eor2
for (int cur : arr)
{
	if ((cur & rightOne) == 0)
	{
		onlyOne ^= cur;
	}
}
System.out.printf(onlyOne + " " + (eor ^ onlyOne));

插入排序

  • 时间复杂度O(N^2),额外空间复杂度O(1)
  • 插入排序在某些数据状况下并不是严格的O(N^2)，会优于选择/冒泡排序
  • 时间复杂度
    O是按算法最差情况下的时间复杂度，
    θ是平均状况下的时间复杂度，
    Ω是最好情况下的时间复杂度，
    后两个指标实际用处不大，可以不记，只用记O
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void insertionSort(int[] arr)
{
	if (arr == null || arr.length < 2)
	{
		return;
	}
	// 0~0 有序的
	// 0~i 想有序
	for (int i = 1; i < arr.length; i++) // 0~i 做到有序
	{
		for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--)
		{
			swap(arr, j, j+1); // 每轮将 j~j+1 按升序排列
		}
	}
}

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

二分法

  1. 在一个有序数组中，找某个数是否存在
  • 遍历找一个数的方法，时间复杂度O(N)
  • 二分法找，先找数组最中间的数，因为有序，所以可以砍掉一半，继续二分，时间复杂度O(log2^N)，默认都写成log(N)
  • 8个 4个 2个 1个 log2^8 = 砍3次
  1. 在一个有序数组中，找>=某个数最左侧的位置
  • 做记号，二分到结束为止
  1. 局部最小值问题
  • 数组无序，相邻数一定不相等
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2024-03-26